Контрольна робота
З дисциплiни: Математичне програмування
Варіант№5
Київ 2009 рiк.
Завдання 1. Скласти математичну модель задачі та розв'язати її графічним методом
На виробництво двох видів продукції використовується три групи устаткування. Необхідна кількість устаткування для випуску одиниці продукції та прибуток від реалізації одиниці продукції (у тис. грн.) зазначено в таблиці. Потрібно організувати випуск продукції так, щоб прибуток від її реалізації був найбільшим.
Група виробничого
устаткування
Кількість устаткування для випуску
одиниці продукції
Кількість
устаткування
в групі
Продукція І
Продукція ІІ
А
2
3
12
В
1
2
8
С
4
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 ≤ 1
x1 ≥ 0, x2 ≥ 0
Рішення.
Перепишемо ЗЛП, помноживши першу нерівність на -1:
F = x1+ x2→ max
-x1+ x2≤ 6
3x1+ 4x2≤ 26
2x1 — x2 ≤ 10
x1 ≥ 0, x2 ≥ 0
Двоїста задача записується у вигляді:--PAGE_BREAK--
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
—
x4
26
3
4
1
26/3
x5
10
2
-1
1
5 (min)
Δ
-1
-1
Вводимо в базис x1 замість x5 і перераховуємо таблицю. Вибираємо стовпець (x2) з єдиним від'ємним значенням (-3/2) в останньому рядку, вибираємо рядок (x4) з найменшим значенням bi/xi (2) і виділяємо розв'язувальний елемент (11/2):
xб
b
x1
x2
x3
x4
x5
bi/xi
x3
11
1/2
1
1/2
22
x4
11
11/2
1
-3/2
2 (min)
x1
5
1
-1/2
1/2
—
Δ продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
-1
-1
А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 досягається в точці (0; 3) і дорівнює -9.
Список використаної літератури
1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навчально-методичний посібник для самостійного вивчення дисципліни. — К.: КНЕУ, 2001. — 248 с.
2. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы: Учебное пособие для студентов. — М.: Просвещение, 1991. — 176 с.
3. Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С. Математичне програмування (методичний посібник для студентів економічних спеціальностей). — Чернівці: Рута, 1998. — 168 с.
4. Наконечний С.І., Савіна С.С. Математичне програмування: Навчальний посібник. — К.: КНЕУ, 2003. — 452 с.
5. Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації. — К.: КНУ, 2003. — 215 с.