Контрольная работа: Математичні моделі задач лінійного програмування
8x1 + 3x2 + 0x3 + 1x4 + 0x5 = 5
-14x1 + 2x2-11x3 + 0x4 + 1x5 = 3
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план
| План | Базис | В | x1 | x2 | x3 | x4 | x5 |
| 0 | x4 | 5 | 8 | 3 | 0 | 1 | 0 |
| x5 | 3 | -14 | 2 | -11 | 0 | 1 | |
| Індексний рядок | F(X0) | 0 | 8 | 3 | -9 | 0 | 0 |
Перейдемо до основного алгоритму симплекс-метода.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 1 | x4 | 5 | 8 | 3 | 0 | 1 | 0 | 1.67 |
| x5 | 3 | -14 | 2 | -11 | 0 | 1 | 1.5 | |
| Індексний рядок | F(X1) | 0 | -14 | -27 | 11 | 0 | 0 | 0 |
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 2 | X4 | 0.5 | 29 | 0 | 16.5 | 1 | -1.5 | 0.0172 |
| X2 | 1.5 | -7 | 1 | -5.5 | 0 | 0.5 | 0 | |
| Индексная строка | F(X2) | 40.5 | -203 | 0 | -137.5 | 0 | 13.5 | 0 |
| План | Базис | В | x1 | x2 | x3 | x4 | x5 |
| 3 | x1 | 0.0172 | 1 | 0 | 0.569 | 0.0345 | -0.0517 |
| x2 | 1.62 | 0 | 1 | -1.52 | 0.2414 | 0.1379 | |
| Индексная строка | F(X3) | 44 | 0 | 0 | -22 | 7 | 3 |
| План | Базис | В | x1 | x2 | x3 | x4 | x5 |
| 4 | x3 | 0.0303 | 1.76 | 0 | 1 | 0.0606 | -0.0909 |
| x2 | 1.67 | 2.67 | 1 | 0 | 0.3333 | 0 | |
| Индексная строка | F(X4) | 44.67 | 38.67 | 0 | 0 | 8.33 | 1 |
Оптимальний план можливо записати так:
x3 = 0.0303
x2 = 1.67
F(X) = 27*1.67 + -11*0.03 = 44.67
Завдання 3
Розвязати транспортну задачц.
| 1 | 4 | 1 | 5 | 6 | 300 |
| 1 | 3 | 1 | 1 | 2 | 250 |
| 4 | 1 | 2 | 2 | 3 | 200 |
| 100 | 120 | 90 | 70 | 80 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача 
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби
У нашому випадку робиться це введенням фіктивного постачальника, оскільки 
. З уведенням фіктивного споживача в транспортній таблиці додатково заявляється n робочих клітинок (додатковий стовпчик).
Виникає проблема, які ціни присвоїти цим клітинкам, щоб фіктивний стовпчик був нейтральним щодо оптимального вибору планових перевезень. Нейтральність забезпечується тим, що всі ціни у фіктивних клітинках вибираються однаковими, а оскільки ці ціни при поставках не повинні впливати на значення цільової функції f, то їх беруть усі рівними нулю.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | В5 | В6 | Запаси | |
| А1 | 1 | 4 | 1 | 5 | 6 | 0 | 300 |
| А2 | 1 | 3 | 1 | 1 | 2 | 0 | 250 |
| А3 | 4 | 1 | 2 | 2 | 3 | 0 | 200 |
| Потреби | 100 | 120 | 90 | 70 | 80 | 290 |
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ = 1x11 + 4x12 + 1x13 + 5x14 +6x15 + 0x16 +1x21 + 3x22 + 1x23 + 1x24 +2x25+0x26+4x31 + 1x32 + 2x33 + 2x34 +3x35 + 0x36.
Загалом математична модель сформульованої задачі має вигляд:
minZ = 1x11 + 4x12 + 1x13 + 5x14 +6x15 + 0x16 +1x21 + 3x22 + 1x23 + 1x24 +2x25 +0x26+4x31 + 1x32 + 2x33 + 2x34 +3x35 + 0x36.
за умов:
