Розв’язання лінійних задач методами лінійного програмування
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Чернігівський державний технологічний університет
Кафедра вищої математики
Контрольна робота
з дисципліни: Математичне програмування
Варіант 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 |
|
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 |
× |
× |
8
Систему потенціалів
можна побудувати лише для невирожденого
опорного плану. Такий план містить m+n-1
лінійно незалежних рівнянь виду
з m+n
невідомими (де m–
кількість постачальників, n–
кількість споживачів). Рівнянь на одне
менше, ніж невідомих, тому система є
невизначеною і для її розв’язку одному
невідомому (нехай ним буде u>1>)
придамо нульове значення.
Для того, щоб план був
оптимальним, повинна виконуватись
умова: для кожної незайнятої клітини
сума потенціалів повинна бути менша
або дорівнювати вартості одиниці
перевезення, що стоїть в цій клітині:
тобто
Робимо перевірку для всіх вільних
клітин:
З розрахунків бачимо, що умова оптимальності не виконується для клітин, А>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 |
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 |
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 |
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 |
× |
× |
3
Транспортні витрати:
що на 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 |
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 |
× |
× |
3
Транспортні витрати за отриманим планом перевезень складають:
що на 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– Шостий крок пошуку оптимального рішення задачі
|
Виробник |
Споживач |
Запаси продукту |
|
||||
|
|
|
|
|
|
|||
|
|
|
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 |
× |
× |
8Транспортні витрати за отриманим планом перевезень складають:
Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 15:
Таблиця15– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
-
-
-2
-
1
-
4
-
-3
1
1
-
-6
-8
-
-3
1
-
-2
-2
-
З таблиці15 видно, що максимальне додатне значення отримали для клітини А>2>В>1>, тому заповнюємо її будуючи для неї цикл, який показано в таблиці14. Результат дій в таблиці16.
Таблиця16– Сьомий крок пошуку оптимального рішення задачі
|
Виробник |
Споживач |
Запаси продукту |
|
||||
|
|
|
|
|
|
|||
|
|
|
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– Восьмий крок пошуку оптимального рішення задачі
|
Виробник |
Споживач |
Запаси продукту |
|
||||
|
|
|
|
|
|
|||
|
|
|
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 |
× |
× |
8Транспортні витрати за отриманим планом перевезень складають:
що на 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гривень.
Список використаних джерел
Кузнецов Ю.Н. Математическое программирование. Учебное пособие для вузов– М.: Высшая школа, 1976.– 352с.
Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.– Мн.: Высш. школа, 1978.– 256с.