Чернігівський державний технологічний університет
Кафедра вищої математики
Контрольна робота
з дисципліни: Математичне програмування
Варіант 06
Чернігів 2009
Зміст
Завдання №1
Завдання №2
Завдання №3
Завдання №4
Завдання №5
Список використаних джерел
Завдання №1
Звести до канонічної форми задачу лінійного програмування:
Дана задача лінійного програмування задана в симетричній формі запису: умови, при яких функція F буде максимальною, задані у вигляді нерівностей. Для того, щоб отримати канонічну форму задачі лінійного програмування необхідно нерівності перетворити у рівності, використовуючи теорему, за якою нерівність
еквівалентна рівнянню
і нерівності
а нерівність вигляду
еквівалентна рівнянню
, в якому
Враховуючи наведене вище дану задачу запишемо у наступній канонічній формі:
Завдання №2
Визначити оптимальний план задачі лінійного програмування графічним методом (знайти максимум і мінімум функції):
Для задач з двома змінними можна використовувати графічний спосіб розв’язку задач лінійного програмування. Побудуємо область допустимих розв’язків системи лінійних нерівностей. Для цього будуємо відповідні даним нерівностям граничні прямі:
Потім знаходимо напівплощини, в яких виконуються задані нерівності (рисунок1).
Рисунок1– Графічне визначення максимального і мінімального значення функції
Область допустимих рішень визначається як загальна частина напівплощин, відповідних даним нерівностям, які при цьому знаходяться в першій четвертині, тобто обмежуються прямими і . З малюнку 1 видно, що функція не має рішення, оскільки напівплощина, утворена прямими
не співпадає з площиною, утвореною обмеженнями
.
Завдання №3
Побудувати двоїсту задачу. Симплексним методом знайти оптимальний план початкової задачі. Використовуючи першу теорему двоїстості, визначити план другої задачі.
Для перетворення нерівностей в рівності вводимо змінні одиничні матриці х3
, х4
і х5
. Для розв’язку задачі симплексним методом необхідно мати три одиничних матриці при невід’ємних правих частинах рівнянь. Для отримання одиничної матриці в першій і третій нерівностях вводимо введемо штучні змінну х6
і х7
та отримаємо одиничні матриці А6
і А7
. Де
і
В результаті наведених перетворень отримаємо наступну задачу:
У виразі функції величину М вважаємо достатньо великим додатнім числом, оскільки задача розв’язується на знаходження мінімального значення функції.
Запишемо задачу у векторній формі:
де
В якості базису вибираємо одиничні вектори А6
, А4
, А7
. Вільні невідомі прирівнюємо нулю . В результаті отримаємо початковий опорний план розширеної задачі
,
якому відповідає розкладення
Для перевірки початкового опорного плану складаємо першу симплексну таблицю (таблиця1) і підраховуємо значення функції і оцінок Маємо:
тобто оскільки М попередньо не фіксовано, то оцінки є лінійними функціями величини М, причому функція складається з двох доданків, одне з яких залежить від М, інше не залежить. Для зручності розрахунків в (F-C) рядок запишемо доданок, незалежний від М, а в (М) рядок – тільки коефіцієнти при М, які і дозволяють порівняти оцінки між собою. Для векторів базису оцінки дорівнюють нулю.
Таблиця1– Перша симплексна таблиця
| Базис | С базису | А0
|
|||||||
| х1
|
х2
|
х3
|
х4
|
х5
|
х6
|
х7
|
|||
| х6
|
М | 8 | 1 | -1 | 0 | 0 | 1 | 0 | |
| х4
|
0 | 20 | 3 | 4 | 0 | 1 | 0 | 0 | 0 |
| х7
|
М | 6 | 3 | 1 | 0 | 0 | -1 | 0 | 1 |
| F-C | – | 0 | -5 | -2 | 0 | 0 | 0 | 0 | 0 |
| М | – | 14 | 4 | 4 | -1 | 0 | -1 | 0 | 0 |
В (М) рядку є додатні оцінки, тому опорний план Х0
не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає . Оскільки у нас максимальне значення 4 належить двом векторам, то в базис включаємо вектор, якому відповідає мінімальне Сj
. Розв’язувальним рядком вибирається той, в якому найменше відношення Серед коефіцієнтів розкладання векторів А1
і А2
по базису є додатні, тому хоча б один з векторів існує.. Знайдемо ці значення:
;
Таким чином підтвердилося, що розв’язувальним стовпчиком буде другий, і визначилося, що розв’язувальним рядком буде перший. Тобто розв’язувальний елемент – число 3. Тоді вектор А2
включаємо в базис, а вектор А6
виключаємо з нього.
Складаємо другу симплексну таблицю (таблиця2). При цьому елементи першого (розв’язувального) рядка ділимо на 3. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.
Таблиця2– Друга симплексна таблиця
| Базис | С базису | А0
|
|||||||
| х1
|
х2
|
х3
|
х4
|
х5
|
х6
|
х7
|
|||
| х2
|
2 | 2,67 | 0,33 | 1 | -0,33 | 0 | 0 | 0,33 | 0 |
| х4
|
0 | 9,33 | 1,67 | 0 | 1,33 | 1 | 0 | -1,33 | 0 |
| х7
|
М | 3,33 | 0 | 0,33 | 0 | -1 | -0,33 | 1 | |
| F-C | – | 5,33 | -4,33 | 0 | -0,67 | 0 | 0 | 0,67 | 0 |
| М | – | 3,33 | 2,67 | 0 | 0,33 | 0 | -1 | -1,33 | 0 |
В (М) рядку є додатні оцінки, тому план, зображений в таблиці2 не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає . Тобто за розв’язувальний стовпчик вибираємо перший. Мінімальне відношення
тому розв’язувальним рядком є третій. Таким чином розв’язувальний елемент – число 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 | 130 115 |
З таблиці4 видно, що запаси продукту у виробника на складах на 15 одиниць більші ніж необхідно споживачу, тобто маємо транспортну задачу з відкритою моделлю. Для розв’язку такої задачі введемо фіктивного споживача, якому необхідно отримати одиниць продукту. Всі тарифи на доставку продукту цьому споживачеві будемо вважати рівними нулю, і весь продукт потрібний цьому споживачеві залишаємо у місці виробництва. Для побудови початкового плану перевезень (таблиця5) використаємо метод "північно-західного" напрямку: заповнювати таблицю починаємо з лівого верхнього кута, рухаючись вниз по стовбцю або вправо по рядку (тарифи перевезень напишемо в правому верхньому куту кожної клітини, кількість продукту – в нижньому лівому). В першу клітину заносимо менше з чисел (min(40;60): 40. Тобто потреба в продукті першого споживача повністю задовільнено і інші клітини першого стовпця заповнювати не будемо. Рухаємося далі по першому рядку в другий стовпчик. В цю клітину записуємо менше з 30 і (60-40), тобто пишемо 20. Таким чином перший рядок заповнювати далі не будемо, оскільки запаси першого місця виробництва остаточно вичерпано: з нього ми повністю задовольняємо потребу у продукті першого споживача і частково (20 одиниць, а не 30) другого. Рухаємося по другому стовпчику на другий рядок. Сюди записуємо менше з (30-20) або 20: маємо 10, тобто другому споживачеві ми веземо 20одиниць продукту з першого місця виробництва і 10– з другого. Аналогічно заповнюємо інші клітини.
Таблиця5– Розподіл продукту по споживачам
| Виробник | Споживач | Запаси продукту | ||||
| 8 | 3 | 3 | 4 | 0 | 60 | |
| 40 | 20 | |||||
| 5 | 2 | 7 | 5 | 0 | 20 | |
| 10 | 10 | |||||
| 5 | 4 | 8 | 2 | 0 | 30 | |
| 20 | 10 | |||||
| 7 | 1 | 5 | 7 | 0 | 20 | |
| 5 | 15 | |||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 |
Таким чином, в таблиці5 отримали початковий опорний план, транспортні витрати за яким складають:
Недоліком використаного методу знаходження опорного плану є ігнорування величини тарифів на перевезення продукту.
Для визначення оптимального плану перевезень використаємо метод потенціалів. Для цього кожному виробнику Аі
(кожному рядку) ставимо у відповідність деяке число а кожному споживачу Ві
(кожному стовпчику)– деяке число На основі таблиці5 складемо таблицю6, в якій додамо один стовпчик і один рядок для написання величини параметрів і . Їх знаходимо використовуючи першу умову оптимальності транспортної задачі: (для кожної зайнятої клітини сума потенціалів повинна дорівнювати вартості одиниці перевезення, що записана в цій клітині).
Таблиця6– Перевірка оптимальності опорного плану
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 40 | 20 | ||||||
| 5 | 2 | 7 | 5 | 0 | 20 | -1 | |
| 10 | 10 | ||||||
| 5 | 4 | 8 | 2 | 0 | 30 | 0 | |
| 20 | 10 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | 5 | |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 3 | 8 | 2 | -5 | × | × | |
Систему потенціалів можна побудувати лише для невирожденого опорного плану. Такий план містить m+n-1 лінійно незалежних рівнянь виду з m+n невідомими (де m– кількість постачальників, n– кількість споживачів). Рівнянь на одне менше, ніж невідомих, тому система є невизначеною і для її розв’язку одному невідомому (нехай ним буде u1
) придамо нульове значення.
Для того, щоб план був оптимальним, повинна виконуватись умова: для кожної незайнятої клітини сума потенціалів повинна бути менша або дорівнювати вартості одиниці перевезення, що стоїть в цій клітині: тобто Робимо перевірку для всіх вільних клітин:
З розрахунків бачимо, що умова оптимальності не виконується для клітин, А1
В3
, А2
В1
, А3
В1
, А4
В1
, А4
В2
, і А4
В3
. Клітину, в якій додатне число отримали максимальним (А2
В3
, оскільки max(5;2;3;6;7;8)=8) зробимо зайнятою, для цього побудуємо цикл і отримуємо таблицю7.
Таблиця7– Другий крок пошуку оптимального рішення
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 40 | 20 | ||||||
| 5 | 2 | 7 | 5 | 0 | 20 | -1 | |
| 10 | 10 | ||||||
| 5 | 4 | 8 | 2 | 0 | 30 | 0 | |
| 15 | 15 | ||||||
| 7
d>
1 |
5 |
7 |
0 |
20 |
-3 |
| |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 3 | 8 | 2 | 3 | × | × | |
Транспортні витрати при такому плані перевезення складають:
Перевірка всіх вільних клітин:
Отримали від’ємні значення у всіх клітинах окрім А1
В3
(5), А1
В5
(3), А2
В1
(2), А2
В5
(2), А3
В1
(3) і А3
В5
(3). Максимальне значення max(5;3;2;2;3;3)=5в клітині А1
В3
, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці7, результат дій в таблиці8).
Таблиця8– Третій крок пошуку оптимального рішення
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | - | |
| 40 | 10 | 10 | |||||
| 5 | 2 | 7 | 5 | 0 | 20 | -1 | |
| 20 | |||||||
| 5 | 4 | 8 | 2 | 0 | 30 | 5 | |
| 15 | 15 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | 2 | |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 3 | 3 | -3 | -2 | × | × | |
Транспортні витрати:
тобто при такому плані перевезення товару транспортні витрати знизилися на 50грн. в порівнянні з попереднім планом перевезення. Але, щоб визначити є отриманий план оптимальним чи ні, виконаємо перевірку.
Перевірку всіх вільних клітин зобразимо в таблиці9, в якій для всіх вільних клітин запишемо різницю між сумою потенціалів і транспортними витратами в клітині.
Таблиця9– Перевірка плану отриманого в результаті третього кроку пошуку оптимального рішення задачі
| - | - | - | -7 | -2 | |
| 2 | - | -5 | -9 | -3 | |
| 8 | 4 | - | - | 3 | |
| 3 | 4 | - | -8 | - |
З таблиці9 видно, що додатне значення отримали для клітин А2
В1
(2), А3
В1
(8), А3
В2
(4), А3
В5
(3), А4
В1
(3) і А4
В2
(4). Максимальне значення max(2;8;4;3;3;4)=8в клітині А3
В1
, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці8, результат дій в таблиці10).
Таблиця1– Четвертий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 25 | 10 | 25 | |||||
| 5 | 2 | 7 | 5 | 0 | 20 | -1 | |
| 20 | |||||||
| 5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 | 15 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | 2 | |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 3 | 3 | 5 | -2 | × | × | |
Транспортні витрати:
що на 120грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин наведена в таблиці11.
Таблиця11– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
| - | - | - | 1 | -2 | |
| 2 | - | -5 | -1 | -3 | |
| - | -4 | -8 | - | -5 | |
| 3 | 4 | - | 0 | - |
План, зображений в таблиці10 не є оптимальним, оскільки отримали додатні значення в клітинах А1
В4
(1), А2
В1
(2), А4
В1
(3), А4
В2
(4). Заповнюємо клітину А4
В2
і будуємо опорний план (таблиця12).
Таблиця12– П’ятий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 25 | 5 | 30 | |||||
| 5 | 2 | 7 | 5 | 0 | 20 | -1 | |
| 20 | |||||||
| 5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 | 15 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | -2 | |
| 5 | 15 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 3 | 3 | 5 | 2 | × | × | |
Транспортні витрати за отриманим планом перевезень складають:
що на 20грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин здійснена в таблиці 13.
Таблиця13– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
| - | - | - | 1 | 2 | |
| 2 | - | -5 | -1 | 1 | |
| - | -4 | -8 | - | -1 | |
| -1 | - | -4 | -4 | - |
Оскільки в результаті розрахунків отримали додатні значення, то знову будуємо цикл і заповнюємо необхідну клітину. В даному випадку це буде або клітина А2
В1
або клітина А1
В5
. Вибираємо останню, оскільки транспортні витрати на перевезення в ній менші. На від’ємних кутах циклу об’єм перевезень становить 10 і 0. Оскільки min(10;0)=0, то всі клітини залишаються незмінними і лише клітина з нульовим перевезенням переходить з А4
В5
на А1
В5
.
Новий план зображено в таблиці14.
Таблиця14– Шостий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 25 | 30 | 5 | |||||
| 5 | 2 | 7 | 5 | 0 | 20 | -1 | |
| 20 | |||||||
| 5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 | 15 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | 0 | |
| 10 | 10 | ||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 1 | 3 | 5 | 0 | × | × | |
Транспортні витрати за отриманим планом перевезень складають:
Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 15:
Таблиця15– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
| - | -2 | - | 1 | - | |
| 4 | - | -3 | 1 | 1 | |
| - | -6 | -8 | - | -3 | |
| 1 | - | -2 | -2 | - |
З таблиці15 видно, що максимальне додатне значення отримали для клітини А2
В1
, тому заповнюємо її будуючи для неї цикл, який показано в таблиці14. Результат дій в таблиці16.
Таблиця16– Сьомий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 15 | 30 | 15 | |||||
| 5 | 2 | 7 | 5 | 0 | 20 | -3 | |
| 10 | 10 | ||||||
| 5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 | 15 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | -4 | |
| 20 | |||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 5 | 3 | 5 | 0 | × | × | |
Транспортні витрати:
що на 40грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин наведена в таблиці17.
Таблиця17– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
| - | 2 | - | 1 | - | |
| - | - | -7 | -3 | -3 | |
| - | -2 | -8 | - | -3 | |
| -3 | - | -6 | -6 | -4 |
План, зображений в таблиці8 не є оптимальним, оскільки отримали додатні значення в клітинах А1
В2
(2) і А1
В4
(1). Заповнюємо клітину А1
В2
і будуємо опорний план (таблиця18).
Таблиця18– Восьмий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 5 | 10 | 30 | 15 | ||||
| 5 | 2 | 7 | 5 | 0 | 20 | -3 | |
| 20 | |||||||
| 5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 | 15 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | -2 | |
| 20 | |||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 8 | 3 | 3 | 5 | 0 | × | × | |
Транспортні витрати за отриманим планом перевезень складають:
що на 20грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів. Перевірка всіх вільних клітин здійснена в таблиці 19.
Таблиця19– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
| - | - | - | 1 | - | |
| - | -2 | -7 | -3 | -3 | |
| - | -4 | -8 | - | -3 | |
| -1 | - | -4 | -4 | -2 |
Оскільки в результаті розрахунків отримали додатне значення в єдиній клітині А1
В4
, то будуємо цикл і заповнюємо її. Новий план зображено в таблиці20.
Таблиця20– Дев’ятий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту | |||||
| 8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 10 | 30 | 5 | 15 | ||||
| 5 | 2 | 7 | 5 | 0 | 20 | -2 | |
| 20 | |||||||
| 5 | 4 | 8 | 2 | 0 | 30 | -2 | |
| 20 | 10 | ||||||
| 7 | 1 | 5 | 7 | 0 | 20 | -2 | |
| 20 | |||||||
| Потреба в продукті | 40 | 30 | 30 | 15 | 15 | 130 | × |
| 7 | 3 | 3 | 4 | 0 | × | × | |
Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 21:
Таблиця21– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
| -1 | - | - | - | - | |
| - | -1 | -6 | -3 | -2 | |
| - | -3 | -7 | - | -2 | |
| -2 | - | -4 | -5 | -2 |
Рішення, зображене в таблиці20 є оптимальним, оскільки для кожної незайнятої клітини сума потенціалів менша вартості перевезень, що знаходиться у відповідній клітинці. Транспортні витрати по оптимальному плану перевезень становлять:
Знайдений оптимальний план покращив результат діяльності у порівнянні з початковим (зменшив транспортні витрати) на 685-380=305гривень.
Список використаних джерел
1. Кузнецов Ю.Н. Математическое программирование. Учебное пособие для вузов– М.: Высшая школа, 1976.– 352с.
2. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.– Мн.: Высш. школа, 1978.– 256с.