Завдання 1. Графоаналітичний метод розв'язання задач лінійного програмування
Постановка завдання: Необхідно знайти рішення задачі, що складається у визначенні максимального значення функції F = c 1 x 1 + c 2 x 2 , де змінні x j ≥ 0 (j = 1, 2) - плановане кількість одиниць j-й продукції, а з j - прибуток на одиницю j-й продукції при умовах a i 1 x 1 + a i 2 x 2 ≤ b i (i = 1, ..., k), x j ≥ 0 (j = 1,2).
Рішення
1. Замінюємо обмеження-нерівності на обмеження-рівності (привести завдання до канонічного виду).
2. Побудуємо прямі, відповідні отриманим рівнянням. p> 3. Визначити напівплощині, відповідні заданим нерівностям в системі обмежень.
4. Пошук області допустимих рішень задачі. p> 5. Побудувати градієнт функції мети: grad F = (F ' x 1 ; F' x 2 ).
6. Побудувати пряму нульового рівня c 1 x 1 + c 2 x 2 = 0, (ця пряма перпендикулярна градієнту) .
7. Перемістити цю пряму в напрямку градієнта, в результаті чого буде знайдена точка (точки), в якій цільова функція приймає максимальне значення, або ж встановлена ​​необмеженість функції на безлічі планів.
8. Визначити координати точки максимуму функції і обчислити значення цільової функції в цій точці.
Система обмежень:
В
Цільова функція.
(1)
Побудуємо прямі, що обмежують багатокутник допустимих рішень:
В В В
6
15
В
2
1
В
В В В
7
8
В
3
0
В
В
- пряма, паралельна осі.
- лінія рівня (F = 0);
В
0
5
В
0
-2
- вектор, в напрямку якого розташоване оптимальне рішення задачі
З системи нерівностей (1) випливає, що багатокутник рішень на графіку ОАВС.
Максимальну довжину має перпендикуляр, опущений з точки В, де перетинаються прямі
- оптимальний план випуску продукції.
- максимальне значення прибутку.
В
Завдання 2. Симплекс-метод розв'язання задач лінійного програмування
Постановка завдання: необхідно знайти рішення задачі, що складається в визначенні максимального значення функції F = c 1 x 1 + c 2 x 2 + c 3 x 3 , де змінні x j ≥ 0 (j = 1, 2) - плановане кількість одиниць j-й продукції, а з j прибуток на одиницю j-й продукції при умовах a i 1 x 1 + a i 2 x 2 + ... + a i n x n ≤ b i (i = +1, ..., m), x j ≥ 0 (j = 1,2, ..., m).
Рішення.
1. Записати математичну модель задачі
Сировина
Продукція
Загальна кількість сировини
А
В
З
S 1 /Td>
15
12
15
360
S 2 /Td>
6
8
4
192
S 3 /Td>
3
2
5
180
Ціна одного виробу (Грн.)
9
10
16
2. Привести завдання до канонічного вигляду, для цього перейти від обмежень-нерівностей до обмежень-равенствам, для чого вводяться додаткові змінні, які за економічним змістом означають ні використовуване при даному плані виробництва кількість сировини того чи іншого виду.
3. Заповнити симплекс-таблицю. p> 4. З'ясувати, чи є хоча б одне від'ємне число D j (у ря...
