Елементи інформаційних технологій в математичному програмуванні
Розв'язання завдання графічним способом. Зображення розв'язку системи нерівностей, визначення досягнення максимуму та мінімуму функції. Розв'язання транспортної задачі методом потенціалів та симплекс-методом, формування оціночної матриці з елементів.
| Рубрика | Математика |
| Вид | задача |
| Язык | украинский |
| Дата добавления | 31.05.2010 |
| Размер файла | 134,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
6
Завдання 1
Розв'язати графічним способом при умовах:
Розв'язування
Зобразимо розв'язок системи нерівностей та вектор F (1;2):
Максимум функції досягається в точці А:
Мінімум функції досягається в точці В:
Завдання 2
Розв'язати транспортну задачу методом потенціалів.
Розв'язування
Спочатку перевіримо задачу на замкненість:
.
Задача є замкненою.
Вихідна таблиця:
|
А/В |
10 |
20 |
25 |
40 |
|||||
|
25 |
4 |
7 |
2 |
5 |
|||||
|
15 |
9 |
3 |
4 |
6 |
|||||
|
35 |
8 |
5 |
9 |
3 |
|||||
|
20 |
2 |
1 |
7 |
4 |
|||||
Складемо початковий план методом мінімального елементу:
|
А/В |
10 |
20 |
25 |
40 |
|||||
|
25 |
4 |
7 |
2 |
5 |
|||||
|
25 |
|||||||||
|
15 |
9 |
3 |
4 |
6 |
|||||
|
10 |
5 |
||||||||
|
35 |
8 |
5 |
9 |
3 |
|||||
|
35 |
|||||||||
|
20 |
2 |
1 |
7 |
4 |
|||||
|
20 |
Опорний план є виродженим, адже число зайнятих клітинок менше ніж m+n-1=8. Зробимо його невиродженим, розміщуючи базисні нулі в клітину з координатами (i,j)=(1,1) та (4,1). Вирішимо задачу методом потенціалів:
|
А/В |
10 |
20 |
25 |
40 |
U |
|||||
|
25 |
4 |
7 |
2 |
5 |
0 |
|||||
|
0 |
25 |
|||||||||
|
15 |
9 |
- |
3 |
+ |
4 |
6 |
5 |
|||
|
10 |
5 |
|||||||||
|
35 |
8 |
5 |
9 |
3 |
2 |
|||||
|
35 |
||||||||||
|
20 |
2 |
+ |
1 |
- |
7 |
4 |
-2 |
|||
|
0 |
20 |
|||||||||
|
4 |
3 |
2 |
1 |
295 |
||||||
Сформуємо оціночну матрицю з елементів :
|
Оціночна матриця |
||||
|
0 |
4 |
0 |
4 |
|
|
0 |
-5 |
-3 |
0 |
|
|
2 |
0 |
5 |
0 |
|
|
0 |
0 |
7 |
5 |
План не є оптимальним, адже є від'ємні елементи.
Переміщуємо по циклу вантаж величиною 10 одиниць, додаючи цю величину у клітинах зі знаком «+», та віднімаючи її від клітин зі знаком «- ».
Маємо,
|
А/В |
10 |
20 |
25 |
40 |
U |
|||||
|
25 |
4 |
- |
7 |
2 |
5 |
+ |
0 |
|||
|
0 |
25 |
|||||||||
|
15 |
9 |
3 |
+ |
4 |
6 |
- |
0 |
|||
|
10 |
5 |
|||||||||
|
35 |
8 |
5 |
9 |
3 |
-3 |
|||||
|
35 |
||||||||||
|
20 |
2 |
+ |
1 |
- |
7 |
4 |
-2 |
|||
|
10 |
10 |
|||||||||
|
V |
4 |
3 |
2 |
6 |
245 |
|||||
|
Оціночна матриця |
||||
|
0 |
4 |
0 |
-1 |
|
|
5 |
0 |
2 |
0 |
|
|
7 |
5 |
10 |
0 |
|
|
0 |
0 |
7 |
0 |
План не є оптимальним, адже є від'ємні елементи.
Переміщуємо по циклу вантаж величиною 0 одиниць, додаючи цю величину у клітинах зі знаком «+», та віднімаючи її від клітин зі знаком «- ».
Отримаємо,
|
А/В |
10 |
20 |
25 |
40 |
U |
|||||
|
25 |
4 |
7 |
2 |
5 |
0 |
|||||
|
25 |
0 |
|||||||||
|
15 |
9 |
3 |
4 |
6 |
1 |
|||||
|
10 |
5 |
|||||||||
|
35 |
8 |
5 |
9 |
3 |
-2 |
|||||
|
35 |
||||||||||
|
20 |
2 |
1 |
7 |
4 |
-1 |
|||||
|
10 |
10 |
|||||||||
|
V |
3 |
2 |
2 |
5 |
245 |
|||||
|
Оціночна матриця |
||||||||||
|
1 |
5 |
0 |
0 |
|||||||
|
5 |
0 |
1 |
0 |
|||||||
|
7 |
5 |
9 |
0 |
|||||||
|
0 |
0 |
6 |
0 |
Як бачимо усі . Адже отриманий план є оптимальним.
При цьому загальна вартість перевезень складає 245 і є мінімальною.
Завдання 3
Розв'язати задачу ЛП симплекс-методом:
Розв'язування
Запишемо в канонічному виді:
Вирішимо задачу симплекс методом.
|
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
|
x4 |
6 |
1 |
3 |
-3 |
1 |
0 |
|
|
x5 |
4 |
-2 |
1 |
1 |
0 |
1 |
|
|
ИС |
0 |
3 |
-2 |
-1 |
0 |
0 |
|
|
Обрано ключовий елемент (1,2) |
|||||||
|
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
|
x2 |
2 |
1/3 |
1 |
-1 |
1/3 |
0 |
|
|
x5 |
2 |
-7/3 |
0 |
2 |
-1/3 |
1 |
|
|
ИС |
4 |
11/3 |
0 |
-3 |
2/3 |
0 |
|
|
Обрано ключовий елемент (2,3) |
|||||||
|
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
|
x2 |
3 |
-5/6 |
1 |
0 |
1/6 |
1/2 |
|
|
x3 |
1 |
-7/6 |
0 |
1 |
-1/6 |
1/2 |
|
|
ИС |
7 |
1/6 |
0 |
0 |
1/6 |
3/2 |
Отримано оптимальний план x* = (0, 3, 1). За нього fmin = (x*) = -7.
Список використаних джерел
1. Бурий В.В., Шевченко І.В. Математичне програмування. -- К.: НАУ, 2007. -- 168с.
2. Єгоршин О.О., Малярець Л.М. Математичне програмування. -- Х.: ВД "ІНЖЕК", 2006. -- 383с.
3. Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). -- К.: МАУП, 2006. -- 184с.
4. Зеленський К.Х. Математичне програмування. -- К.: Університет "Україна", 2007. -- 241c.
5. Івченко І.Ю. Математичне програмування. -- К.: Центр учбової літератури, 2007. -- 232с.
6. Лебідь М.Т., Синявіна Ю.В. Математичне програмування. -- Х., 2007. -- 72с.
Подобные документы
Розв'язання графічним методом математичної моделі задачі з організації випуску продукції. Розв'язання транспортної задачі методом потенціалів. Знаходження умовних екстремумів функцій методом множників Лагранжа. Розв'язання задач симплекс-методом.
контрольная работа [48,5 K], добавлен 16.07.2010Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
практическая работа [42,3 K], добавлен 09.11.2009Запис системи рівнянь та їх розв'язання за допомогою методів оберненої матриці та Гауса. Поняття вектора-стовпця з невідомих та вільних членів. Пошук оберненої матриці до даної. Послідовне виключення невідомих за допомогою елементарних перетворень.
контрольная работа [115,2 K], добавлен 16.07.2010Розв’язання систем лінійних рівнянь методом Жордана-Гауса. Еквівалентні перетворення системи, їх виконання як елемент методів розв’язування системи рівнянь. Базисні та вільні змінні. Лінійна та фундаментальна комбінації розв’язків, таблиці коефіцієнтів.
контрольная работа [170,2 K], добавлен 16.05.2010Прийоми розв’язання задач в першому і другому степені на Далекому Сході та Греції. Досягнення арабських математиків в області алгебраїчних рівнянь. Розв'язання похідного кубічного рівняння. Найвидатніші теореми про радикали вищих степенів, їх розв’язання.
курсовая работа [536,1 K], добавлен 23.02.2014Поняття та значення симплекс-методу як особливого методу розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального рішення. Розв'язання задачі з використанням програми Simplex Win.
лабораторная работа [264,1 K], добавлен 30.03.2015Послідовність графічного розв'язання задачі лінійного програмування. Сумісна система лінійних нерівностей, умови невід'ємності, визначення півплощини з граничними прямими. Графічний метод для визначення оптимального плану задачі лінійного програмування.
задача [320,6 K], добавлен 31.05.2010Визначення системи лінійних рівнянь та її розв’язання. Поняття рангу матриці, правило Крамера та види перетворень з матрицею. Способи знайдення оберненої матриці А–1 до невиродженої матриці А. Контрольні запитання та приклади розв’язування задач.
задача [73,5 K], добавлен 25.03.2011Розв’язання системи рівнянь методом Крамера, методом оберненої матриці та методом Гаусса. Розрахунок довжини ребра, кута між ребрами, рівняння висоти, рівняння площини грані і кута між ребром та гранню. Дослідження функції та побудува її графіку.
контрольная работа [397,0 K], добавлен 30.10.2011Загальні відомості про раціональні нерівності, теореми про рівносильність нерівностей. Методи розв'язування раціональних нерівностей вищих степенів узвгальненим методом інтервалів, методом заміни змінної. Розв'язування дробово-раціональних нерівностей.
курсовая работа [774,9 K], добавлен 01.04.2010
