Розв’язання лінійних задач методами лінійного програмування (стр. 2 из 6)
тому розв’язувальним рядком є третій. Таким чином розв’язувальний елемент – число 2,67. Тоді вектор А1 включаємо в базис, а вектор А7 виключаємо з нього.
Складаємо другу симплексну таблицю (таблиця3). При цьому елементи третього (розв’язувального) рядка ділимо на 2,67. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.
Таблиця3– Третя симплексна таблиця
| Базис | С базису | А0 |  |  |  |  |  |  |  |
| х1 | х2 | х3 | х4 | х5 | х6 | х7 | |||
| х2 | 2 | 2,25 | 0 | 1 | -0,375 | 0 | 0,125 | 0,375 | -0,125 |
| х4 | 0 | 7,25 | 0 | 0 | 1,125 | 1 | 0,625 | -1,125 | -0,625 |
| х1 | 5 | 1,25 | 1 | 0 | 0,125 | 0 | -0,375 | -0,125 | 0,375 |
| F-C | – | 10,75 | 0 | 0 | -0,125 | 0 | -1,625 | 0,125 | 1,625 |
| М | – | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
В результаті проведеної ітерації з базису виключено штучні елементи, тому в рядку (М)всі оцінки, крім оцінки штучного вектору, перетворилися на нуль. Оскільки в рядках (F-C) і (М) не має додатних значень, то знайдене рішення
(
)є оптимальним. Функція при цьому
Перевірка
Кожній задачі лінійного програмування можна поставити у відповідність двоїсту задачу. Для цього першим кроком необхідно впорядкувати запис вихідної задачі. Оскільки у нас функція мінімізується, то всі умови-нерівності повинні бути вигляду
. Виконання цієї умови досягаємо множенням відповідних умов на (1-). В результаті система обмежень матиме наступний вигляд: 
Оскільки вихідна задача є задачею мінімізації, то двоїста буде задачею максимізації. Двоїста задача буде мати три змінні
, оскільки вихідна задача має три обмеження. При цьому вектор, отриманий із коефіцієнтів при невідомих цільової функції вихідної задачі 
, співпадає з вектором констант у правих частинах обмежень двоїстої задачі. Аналогічно пов’язані між собою вектори, утворені з коефіцієнтів при невідомих цільової функції двоїстої задачі 
, і константи в правих частинах обмежень вихідної задачі. Кожній змінній 
двоїстої задачі відповідає і-те обмеження вихідної задачі, і, навпаки, кожній змінній 
прямої задачі відповідає j-те обмеження двоїстої задачі. Матриця з коефіцієнтів при невідомих двоїстої задачі 
утворюється транспортуванням матриці А, складеної з коефіцієнтів при невідомих вихідної задачі. Якщо на j-ту змінну вихідної задачі накладена умова невід’ємності, то j-те обмеження двоїстої задачі буде нерівністю, в іншому випадку j-те обмеження буде рівністю; аналогічно пов’язані між собою обмеження вихідної задачі і змінні двоїстої.Складаємо матрицю при невідомих вихідної задачі:
,тоді матриця при невідомих двоїстої задачі матиме наступний вигляд:
На
накладено умову невід’ємності, тому обмеження двоїстої задачі матимуть вигляд нерівності, а не рівності. Оскільки в початковій задачі всі обмеження мають вигляд нерівності, то накладаємо умови 
Враховуючи все наведене, двоїста задача матиме наступний вигляд:
Якщо розглянути першу симплексну таблицю з одиничним додатковим базисом, то можна помітити, що в стовбцях записана вихідна задача, а в рядках – двоїста. Причому оцінками плану вихідної задачі є
, а оцінками плану двоїстої задачі – 
З таблиці3, отриманої в результаті рішення вихідної задачі знаходимо: 
Завдання №4
Визначити оптимальний план транспортної задачі:
а) побудувати початковий опорний план методом "північно-західного" напрямку;
б) побудувати оптимальний план методом потенціалів:
Нехай в матриці А міститься інформація про кількість продукту в кожному місці виробництва, який необхідно доставити споживачам в кількості записаній в матриці В. Транспортні витрати, пов’язані з перевезенням одиниці продукту із одного місця виробництва одному споживачеві, записані в матриці С. Задані матриці і сказане вище для спрощення сприйняття узагальнимо в таблиці4.
Таблиця4–Поставка продукту із різних місць виробництва різним споживачам і пов’язані з цим витрати
| Виробник | Споживач | Запаси продукту | |||
 |  |  |  | ||
 | 8 | 3 | 3 | 4 | 60 |
 | 5 | 2 | 7 | 5 | 20 |
 | 5 | 4 | 8 | 2 | 30 |
 | 7 | 1 | 5 | 7 | 20 |
| Потреба в продукті | 40 | 30 | 30 | 15 | 130115 |
З таблиці4 видно, що запаси продукту у виробника на складах на 15 одиниць більші ніж необхідно споживачу, тобто маємо транспортну задачу з відкритою моделлю. Для розв’язку такої задачі введемо фіктивного споживача, якому необхідно отримати
одиниць продукту. Всі тарифи на доставку продукту цьому споживачеві будемо вважати рівними нулю, і весь продукт потрібний цьому споживачеві залишаємо у місці виробництва. Для побудови початкового плану перевезень (таблиця5) використаємо метод "північно-західного" напрямку: заповнювати таблицю починаємо з лівого верхнього кута, рухаючись вниз по стовбцю або вправо по рядку (тарифи перевезень напишемо в правому верхньому куту кожної клітини, кількість продукту – в нижньому лівому). В першу клітину заносимо менше з чисел (min(40;60): 40. Тобто потреба в продукті першого споживача повністю задовільнено і інші клітини першого стовпця заповнювати не будемо. Рухаємося далі по першому рядку в другий стовпчик. В цю клітину записуємо менше з 30 і (60-40), тобто пишемо 20. Таким чином перший рядок заповнювати далі не будемо, оскільки запаси першого місця виробництва остаточно вичерпано: з нього ми повністю задовольняємо потребу у продукті першого споживача і частково (20 одиниць, а не 30) другого. Рухаємося по другому стовпчику на другий рядок. Сюди записуємо менше з (30-20) або 20: маємо 10, тобто другому споживачеві ми веземо 20одиниць продукту з першого місця виробництва і 10– з другого. Аналогічно заповнюємо інші клітини.