Розв'язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплекс-методом
Розв'язання графічним методом математичної моделі задачі з організації випуску продукції. Розв'язання транспортної задачі методом потенціалів. Знаходження умовних екстремумів функцій методом множників Лагранжа. Розв'язання задач симплекс-методом.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 16.07.2010 |
| Размер файла | 48,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Контрольна робота
З дисциплiни: Математичне програмування
Варіант№5
Київ 2009 рiк.
Завдання 1. Скласти математичну модель задачі та розв'язати її графічним методом
На виробництво двох видів продукції використовується три групи устаткування. Необхідна кількість устаткування для випуску одиниці продукції та прибуток від реалізації одиниці продукції (у тис. грн.) зазначено в таблиці. Потрібно організувати випуск продукції так, щоб прибуток від її реалізації був найбільшим.
|
Група виробничого устаткування |
Кількість устаткування для випуску одиниці продукції |
Кількість устаткування в групі |
||
|
Продукція І |
Продукція ІІ |
|||
|
А |
2 |
3 |
12 |
|
|
В |
1 |
2 |
8 |
|
|
С |
4 |
0 |
16 |
|
|
Прибуток, тис. грн. |
1 |
3 |
Рішення:
Позначимо через x1 і x2 кількість продукції І і ІІ. Тоді умови для необхідного устаткування будуть описуватися наступними нерівностями:
2x1 + 3x2 ? 12
1x1 + 2x2 ? 8
4x1 + 0x2 ? 16
x1, x2 ? 0
А умова найбільшого прибутку:
f = 1x1 + 3x2 > max
Для розв'язання задачі графічним методом замість нерівностей системи обмежень беремо відповідні рівняння граничних прямих і будуємо їх графіки:
Звертаючи увагу на півплощини, в яких виконуються відповідні нерівності, знаходимо спільну область, помічену сірим кольором. Стрілкою вказуємо вектор зростання цільової функції f, компоненти якого (1; 3) дорівнюють коефіцієнтам при x1 і x2 у виразі цієї функції.
Бачимо, що максимального значення функція f набуває в точці М, на перетині прямої 2x1 + 3x2 = 12 і вісі x2. Підставляючи x1 = 0 в це рівняння, отримуємо:
2*0 + 3x2 = 12
x2 = 4
М = (x1; x2) = (0; 4)
Значення функції f в точці М:
fmax = 1*0+3*4 = 12
Відповідь:
Найбільший прибуток у розмірі 12 тис. грн. буде від реалізації 4 одиниць продукції ІІ без випуску продукції І.
Завдання 2. Для заданої ЗЛП побудувати двоїсту, розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язком знайти розв'язок іншої задачі
F = x1 + x2 > max
|
x1 - x2 ? -6 |
|
|
3x1 + 4x2 ? 26 |
|
|
2x1 - x2 ? 10 |
x1 ? 0, x2 ? 0
Рішення.
Перепишемо ЗЛП, помноживши першу нерівність на -1:
F = x1 + x2 > max
-x1 + x2 ? 6
3x1 + 4x2 ? 26
2x1 - x2 ? 10
x1 ? 0, x2 ? 0
Двоїста задача записується у вигляді:
F* = 6y1 + 26y2 + 10y3 > min
-1y1 + 3y2 + 2y3 ? 1
1y1 + 4y2 - 1y3 ? 1
y1 ? 0, y2 ? 0, y3 ? 0
Зведемо вихідну задачу до канонічної форми [5, с. 14]. Для цього добавимо невід'ємні величини x3, x4, x5, щоб нерівності перетворити в рівняння:
F - x1 - x2 > max
-x1 + x2 + x3 = 6
3x1 + 4x2 + x4 = 26
2x1 - x2 + x5 = 10
x1 ? 0, x2 ? 0, x3 ? 0, x4 ? 0, x5 ? 0
Розв'яжемо дану задачу симплекс-методом [5, с. 18]. Заповнюємо симплекс-таблицю початковими значеннями, вибираємо стовпець (x1) з першим від'ємним значенням (-1) в останньому рядку, вибираємо рядок (x5) з найменшим значенням bi/xi (5) і виділяємо розв'язувальний елемент (2):
|
xб |
b |
x1 |
x2 |
x3 |
x4 |
x5 |
bi/xi |
|
|
x3 |
6 |
-1 |
1 |
1 |
0 |
0 |
-- |
|
|
x4 |
26 |
3 |
4 |
0 |
1 |
0 |
26/3 |
|
|
x5 |
10 |
2 |
-1 |
0 |
0 |
1 |
5 (min) |
|
|
Д |
0 |
-1 |
-1 |
0 |
0 |
0 |
Вводимо в базис x1 замість x5 і перераховуємо таблицю. Вибираємо стовпець (x2) з єдиним від'ємним значенням (-3/2) в останньому рядку, вибираємо рядок (x4) з найменшим значенням bi/xi (2) і виділяємо розв'язувальний елемент (11/2):
|
xб |
b |
x1 |
x2 |
x3 |
x4 |
x5 |
bi/xi |
|
|
x3 |
11 |
0 |
1/2 |
1 |
0 |
1/2 |
22 |
|
|
x4 |
11 |
0 |
11/2 |
0 |
1 |
-3/2 |
2 (min) |
|
|
x1 |
5 |
1 |
-1/2 |
0 |
0 |
1/2 |
-- |
|
|
Д |
5 |
0 |
-3/2 |
0 |
0 |
1/2 |
Вводимо в базис x2 замість x4 і перераховуємо таблицю:
|
xб |
b |
x1 |
x2 |
x3 |
x4 |
x5 |
bi/xi |
|
|
x3 |
10 |
0 |
0 |
1 |
-1/11 |
7/11 |
-- |
|
|
x2 |
2 |
0 |
1 |
0 |
2/11 |
-3/11 |
-- |
|
|
x1 |
6 |
1 |
0 |
0 |
1/11 |
4/11 |
-- |
|
|
Д |
8 |
0 |
0 |
0 |
3/11 |
1/11 |
В останньому рядку не залишилося від'ємних величин, тому стовбець b містить рішення вихідної задачі -- максимум функції F:
x1 = 6
x2 = 2
Fmax = 8
Запишемо рішення двоїстої задачі з останнього рядка останньої симплекс-таблиці:
y1 = 0
y2 = 3/11
y3 = 1/11
F*min = 8
Відповідь:
Вихідна задача: Fmax = F(6; 2) = 8
Двоїста задача: F*min = F*(0; 3/11; 1/11) = 8
Завдання 3. Розв'язати методом потенціалів транспортну задачу
|
ai \ bj |
90 |
50 |
60 |
80 |
|
|
120 |
5 |
4 |
3 |
4 |
|
|
100 |
3 |
2 |
5 |
5 |
|
|
60 |
1 |
6 |
3 |
1 |
Рішення.
Підраховуємо загальні запаси постачальників: 120 + 100 + 60 = 280
Підраховуємо загальні потреби споживачів: 90 + 50 + 60 + 80 = 280
Дана модель закрита [5, с. 55], тому що загальні потреби споживачів дорівнюють загальним запасам постачальників.
Запишемо умову задачі у вигляді наступної таблиці:
|
В1 |
В2 |
В3 |
В4 |
Запаси |
||
|
А1 |
5 |
4 |
3 |
4 |
120 |
|
|
А2 |
3 |
2 |
5 |
5 |
100 |
|
|
А3 |
1 |
6 |
3 |
1 |
60 |
|
|
Потреби |
90 |
50 |
60 |
80 |
Для визначення опорного плану транспортної задачі застосуємо спочатку метод мінімального елемента [5, с. 50]. Для цього будемо послідовно вибирати клітинки з мінімальним тарифом і робити спробу максимально задовольнити вимоги споживачів і постачальників.
Перший мінімальний елемент (1) знаходяться в клітинці А-3В-1, тому записуємо в неї запас постачальника А-3 (60) і коректуємо колонки запасів та потреб:
|
В1 |
В2 |
В3 |
В4 |
Запаси |
||
|
А1 |
120 |
|||||
|
А2 |
100 |
|||||
|
А3 |
60 |
-- |
-- |
-- |
0 |
|
|
Потреби |
30 |
50 |
60 |
80 |
Наступні мінімальні елементи (2 та 3) знаходяться в клітинках А2В2, А1В3 та А2В1, тому записуємо в них потреби споживачів В2 (50), В3 (60) та В1 (30) і коректуємо колонки запасів та потреб:
|
В1 |
В2 |
В3 |
В4 |
Запаси |
||
|
А1 |
-- |
-- |
60 |
60 |
||
|
А2 |
30 |
50 |
-- |
20 |
||
|
А3 |
60 |
-- |
-- |
-- |
0 |
|
|
Потреби |
0 |
0 |
0 |
80 |
Залишилися вільні клітинки А1В4 та А2В4, тому записуємо в них запаси постачальників А1 (60) та А2 (20) і коректуємо колонки запасів та потреб:
|
В1 |
В2 |
В3 |
В4 |
Запаси |
||
|
А1 |
-- |
-- |
60 |
60 |
0 |
|
|
А2 |
30 |
50 |
-- |
20 |
0 |
|
|
А3 |
60 |
-- |
-- |
-- |
0 |
|
|
Потреби |
0 |
0 |
0 |
0 |
Підрахуємо вартість перевезення для отриманого опорного плану:
60*3 + 60*4 + 30*3 + 50*2 + 20*5 + 60*1 = 770
Для визначення оптимальності отриманого опорного плану застосуємо метод потенціалів [5, с. 51]. Для цього задамо нульовий потенціал першому рядку, а решту потенціалів визначимо враховуючи отримані клітинки:
|
В1 |
В2 |
В3 |
В4 |
потенц. |
||
|
А1 |
3 |
4 |
0 |
|||
|
А2 |
3 |
2 |
5 |
1 |
||
|
А3 |
1 |
1 |
||||
|
потенц. |
2 |
1 |
3 |
4 |
Визначаємо оцінки для вільних клітинок, знаходимо максимальну додатну оцінку (4) в клітинці А-3В-4 і позначаємо для неї цикл [5, с. 51]:
|
В1 |
В2 |
В3 |
В4 |
потенц. |
||
|
А1 |
-3 |
-3 |
0 |
|||
|
А2 |
(+) |
-1 |
(-) |
1 |
||
|
А3 |
(-) |
-4 |
1 |
4(+) |
1 |
|
|
потенц. |
2 |
1 |
3 |
4 |
В вершинах циклу зі знаком (-) вибираємо мінімальне значення (20) у клітинці А-2В-4 опорного плану. Додаємо його до вершин циклу зі знаком (+) і віднімаємо його від вершин циклу зі знаком (-):
|
В1 |
В2 |
В3 |
В4 |
Запаси |
||
|
А1 |
60 |
60 |
0 |
|||
|
А2 |
50 |
50 |
0 |
|||
|
А3 |
40 |
20 |
0 |
|||
|
Потреби |
0 |
0 |
0 |
0 |
При цьому вартість перевезення для цього поліпшеного опорного плану:
60*3 + 60*4 + 50*3 + 50*2 + 40*1 + 20*1 = 730
Для визначення оптимальності поліпшеного опорного плану знову застосуємо метод потенціалів -- задамо нульовий потенціал першому рядку, а решту потенціалів визначимо враховуючи отримані клітинки:
|
В1 |
В2 |
В3 |
В4 |
потенц. |
||
|
А1 |
3 |
4 |
0 |
|||
|
А2 |
3 |
2 |
-1 |
|||
|
А3 |
1 |
1 |
-3 |
|||
|
потенц. |
4 |
3 |
3 |
4 |
Визначаємо оцінки для вільних клітинок:
|
В1 |
В2 |
В3 |
В4 |
потенц. |
||
|
А1 |
-1 |
-1 |
0 |
|||
|
А2 |
-3 |
-2 |
-1 |
|||
|
А3 |
-6 |
-3 |
-3 |
|||
|
потенц. |
4 |
3 |
3 |
4 |
Оскільки всі отримані оцінки не більші нуля, то останній опорний план є оптимальним [5, с. 51]. Отримуємо оптимальний план перевезення:
|
Маршрут |
Кількість |
Вартість |
|
|
А-1 -- В3 |
60 |
180 |
|
|
А-1 -- В-4 |
60 |
240 |
|
|
А-2 -- В-1 |
50 |
150 |
|
|
А-2 -- В-2 |
50 |
100 |
|
|
А-3 -- В-1 |
40 |
40 |
|
|
А-3 -- В-4 |
20 |
20 |
|
|
Всього |
730 |
Відповідь:
Вартість оптимального плану транспортної задачі дорівнює 730.
Завдання 4. Методом множників Лагранжа знайти умовні екстремуми функцій
f = x12 + x1x2 + x22 - 3x1 - 6x2 за умови x1 + x2 = 3.
Рішення.
Перепишемо умову у вигляді c(x1, x2) = 0:
x1 + x2 - 3 = 0
Тоді функція Лагранжа [5, с. 153]:
L(x1, x2, л) = f(x1, x2) + л c(x1, x2)
L(x1, x2, л) = x12 + x1x2 + x22 - 3x1 - 6x2 + л(x1 + x2 - 3)
У точці екстремуму частинні похідні функції Лагранжа дорівнюють нулю [5, с. 154]:
?L(x1, x2, л) / ?x1 = 2x1 + x2 - 3 + л
?L(x1, x2, л) / ?x2 = x1 + 2x2 - 6 + л
Отримуємо наступну систему:
2x1 + x2 - 3 + л = 0
x1 + 2x2 - 6 + л = 0
x1 + x2 - 3 = 0
Віднімаємо друге рівняння системи від першого і визначаємо x2:
x1 - x2 + 3 = 0
x2 = x1 + 3
Підставляємо отримане x2 в третє рівняння системи:
x1 = 0
x2 = x1 + 3 = 3
Отже точка (0; 3) -- умовний екстремум функції f, який дорівнює:
f(0; 3) = 32 - 6*3 = -9
Розглянемо іншу довільну точку (3; 0), для якої виконується умова задачі. Значення функції для цієї точки:
f(3; 0) = 32 - 3*3 = 0
Оскільки f(0; 3) < f(3; 0), то знайдений умовний екстремум -- це умовний мінімум.
Відповідь: Умовний мінімум функції f досягається в точці (0; 3) і дорівнює -9.
Список використаної літератури
1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навчально-методичний посібник для самостійного вивчення дисципліни. -- К.: КНЕУ, 2001. -- 248 с.
2. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы: Учебное пособие для студентов. -- М.: Просвещение, 1991. -- 176 с.
3. Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С. Математичне програмування (методичний посібник для студентів економічних спеціальностей). -- Чернівці: Рута, 1998. -- 168 с.
4. Наконечний С.І., Савіна С.С. Математичне програмування: Навчальний посібник. -- К.: КНЕУ, 2003. -- 452 с.
5. Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації. -- К.: КНУ, 2003. -- 215 с.
Подобные документы
Розв'язання завдання графічним способом. Зображення розв'язку системи нерівностей, визначення досягнення максимуму та мінімуму функції. Розв'язання транспортної задачі методом потенціалів та симплекс-методом, формування оціночної матриці з елементів.
задача [134,9 K], добавлен 31.05.2010Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
практическая работа [42,3 K], добавлен 09.11.2009Методи зведення до канонічної форми задач лінійного програмування. Визначення шляхів знаходження екстремумів функцій графічним способом. Побудова початкового опорного плану методом "північно-західного" напрямку. Складання двоїстої системи матриць.
контрольная работа [262,0 K], добавлен 08.02.2010Поняття та значення симплекс-методу як особливого методу розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального рішення. Розв'язання задачі з використанням програми Simplex Win.
лабораторная работа [264,1 K], добавлен 30.03.2015Запис системи рівнянь та їх розв'язання за допомогою методів оберненої матриці та Гауса. Поняття вектора-стовпця з невідомих та вільних членів. Пошук оберненої матриці до даної. Послідовне виключення невідомих за допомогою елементарних перетворень.
контрольная работа [115,2 K], добавлен 16.07.2010Розв’язання систем лінійних рівнянь методом Жордана-Гауса. Еквівалентні перетворення системи, їх виконання як елемент методів розв’язування системи рівнянь. Базисні та вільні змінні. Лінійна та фундаментальна комбінації розв’язків, таблиці коефіцієнтів.
контрольная работа [170,2 K], добавлен 16.05.2010Складання плану виробництва при максимальному прибутку. Введення додаткових (фіктивних) змінних, які перетворюють нерівності на рівності. Розв’язування задачі лінійного програмування графічним методом та економічна інтерпретація отриманого розв’язку.
контрольная работа [298,3 K], добавлен 20.11.2009Розв’язання системи рівнянь методом Крамера, методом оберненої матриці та методом Гаусса. Розрахунок довжини ребра, кута між ребрами, рівняння висоти, рівняння площини грані і кута між ребром та гранню. Дослідження функції та побудува її графіку.
контрольная работа [397,0 K], добавлен 30.10.2011Етапи розв'язування інженерних задач на ЕОМ. Цілі, засоби й методи моделювання. Створення математичної моделі. Побудова обчислювальної моделі. Реалізація методу обчислень. Розв’язання нелінійних рівнянь методом дихотомії. Алгоритм метода дихотомії.
контрольная работа [86,1 K], добавлен 06.08.2010Прийоми розв’язання задач в першому і другому степені на Далекому Сході та Греції. Досягнення арабських математиків в області алгебраїчних рівнянь. Розв'язання похідного кубічного рівняння. Найвидатніші теореми про радикали вищих степенів, їх розв’язання.
курсовая работа [536,1 K], добавлен 23.02.2014
