- •Математичне програмування
- •0305 “Економіка та підприємництво” та 0306 „Менеджмент і адміністрування” Видання друге, доповнене, допрацьоване
- •Розділ 1. Загальні методичні вказівки з вивчення дисципліни
- •Та питання для самостійної перевірки знань Модуль 1. Лінійне програмування
- •Модуль 2. Двоїсті задачі, нелінійне та інші види математичного програмування
- •Розділ 3. Завдання для контрольної роботи
- •Завдання 2. Симплексний метод розв'язання задач лінійного програмування
- •Завдання 3. Двоїсті задачі лінійного програмування
- •Примітка. Розрахунки виконати для всіх небазисних змінни кінцевої симплексної таблиці прямої задачі.
- •Скласти план вантажних перевезень з мінімальним вантажообігом.
- •Площі попередників озимої пшениці, га
- •Площа сортів озимої пшениці, га
- •Середня урожайність озимої пшениці за попередниками, ц з 1 га
- •Завдання 5. Задачі нелінійного програмування
- •Визначимо головні мінори, починаючи з 2-го порядку
- •Отже, головні мінори визначаються множником
- •Тестові завдання Модуль 1. Лінійне програмування
- •1.12. В частинному розв’язку системи рівнянь при
- •1.13. В частинному розв’язку системи рівнянь при
- •1.14. Базисні невідомі, які складають допустимий розв’язок задачі лінійного програмування, можуть бути:
- •1.16. Небазисні невідомі задачі лінійного програмування:
- •1.17. Канонічна форма задачі лінійного програмування представляє собою систему:
- •1.18. Приведення загальної задачі лінійного програмування до канонічної форми виконується шляхом введення в кожне обмеження-нерівність по одній невідомій, яка називається:
- •Модуль 2. Двоїсті задачі, нелінійне та інші види математичного програмування
- •Відомість виконання тестових завдань
- •Приклад використання Excel для розв’язання симплексних задач лінійного програмування (лп)
- •Приклад використання Excel для розв’язання транспортних задач лінійного програмування (тлп)
- •Список рекомендованої літератури Підручники та навчальні посібники
- •Електронні ресурси
- •Володимир Петрович марченко Надія Іванівна гринчак Математичне програмування
- •0305 “Економіка та підприємництво” та 0306 „Менеджмент і адміністрування”
Примітка. Розрахунки виконати для всіх небазисних змінни кінцевої симплексної таблиці прямої задачі.
Завдання 4. Розв'язання транспортних задач методом потенціалів
Приклад 4.1. Потрібно перевезти мінеральні добрива з трьох складів (постачальники) ємністю по 200 т кожний до чотирьох господарств (споживачі), потреба яких в мінеральних добривах становить відповідно 150, 100, 150 та 200т. Відстані від складів до господарств наведені в таблиці 4.1.
Таблиця 4.1
Відстані від складів до господарств, км
Склади |
Господарства |
|||
S1 |
S2 |
S3 |
S4 |
|
D1 |
5 |
6 |
7 |
8 |
D2 |
8 |
9 |
10 |
11 |
D3 |
7 |
14 |
15 |
20 |
Скласти план вантажних перевезень з мінімальним вантажообігом.
Розв’язання. В даній задачі потреба всіх господарств у мінеральних добривах (150 + 100 + 150 + 200 = 600 т) дорівнює сумарній наявності добрив на складах (200 3 = 600 т). Тому транспортна задача називається закритою.
Умови задачі запишемо у вигляді таблиці 4.2.
Таблиця 4.2
Склади |
Господарства |
Наявність добрив, т |
|||
S1 |
S2 |
S3 |
S4 |
|
|
D1 |
5 |
6 |
7 |
8 |
200 |
D2 |
8 |
9 |
10 |
11 |
200 |
D3 |
7 |
14 |
15 |
20 |
200 |
Потреба в добривах,т |
150 |
100 |
150 |
200 |
600 |
Алгоритм методу потенціалів складається з таких етапів:
1) побудова опорного плану;
2) виконання розрахунків, що приводять до оптимального розв'язку.
Опорний план задачі можна отримати декількома методами:
1) діагональний або північно-західного кута - у верхню ліву клітину (північно-західний кут) записуємо максимально можливий вантаж 150 т, тоді всі інші клітини 1-ої колонки будуть незаповненими (небазисними). В клітину 1-го рядка 2-ої колонки можна поставити вантаж 200-150=50 т, тоді всі інші клітини 1-ого рядка будуть незаповненими. В клітину 2-го рядка 2-ої колонки можна поставити вантаж 100-50=50 т, тоді всі інші клітини 2-ої колонки будуть незаповненими. Розрахунки продовжуються до тих пір, поки не буде розподілений весь вантаж. Недоліком цього методу є те, що вантаж розподіляється без врахування вартості перевезення , внаслідок чого отримуємо опорний план задачі далекій від оптимального. Збільшується кількість ітерацій для отримання оптимального розв’язку, а перевагою - відсутність виродженого опорного плану задачі;
2) подвійної переваги - спочатку в кожному рядку і кожній колонці відмічаються клітини з найменшими оцінками ci j . У клітини, які мають найменшу оцінку як по рядку, так і по колонці ставимо максимально можливий вантаж. Розрахунки продовжуються до тих пір, поки не буде розподілений весь вантаж. Недоліками цього методу є велика ймовірність отримання виродженого опорного плану, внаслідок чого потрібно виконати додаткові розрахунки для подолання виродженності, та трудоємкість пошуку клітин з найменшими оцінками як по рядку, так і по колонці при достатньо великих розмірах транспортної задачі, а перевагою - зменшення кількості ітерацій порівняно з методом північно-західного кута.
3) 'найкращого' елементу в матриці - знаходиться клітина матриці транспортної задачі з найменшою (при розв'язанні задачі на мінімум цільової функції) або найбільшою (при розв'язанні задачі на максимум цільової функції) оцінкою, в яку ставиться максимально можливий вантаж, потім наступна за нею і т.д. поки не буде розподілено весь вантаж. Недоліки і переваги - цього методу такі ж, як і в методі подвійної переваги.
Для отримання допустимого опорного плану задачі за будь-яким із наведених вище методів повинні виконуватися такі умови:
1) транспортна задача повинна бути закритою. Для перетворення відкритої транспортної задачі в закриту вводяться фіктивні постачальник або споживач з нульовими оцінками клітин та потужністю, яка дорівнює різниці між сумарними потужностями постачальників та споживачів;
2) при розрахунках повинен забезпечуватися баланс вантажів по кожному рядку і по кожній колонці транспортної таблиці;
3) заповнені клітини (базисні невідомі) в транспортній таблиці не повинні утворювати циклів (замкнутих контурів);
4) кількість заповнених клітин в транспортної таблиці повинна дорівнювати m + n – 1, де m - кількість рядків, а n - кількість колонок. Якщо кількість заповнених клітин менше m + n – 1, то отриманий опорний план задачі буде виродженим. Для подолання виродженості кількість заповнених клітин доповнюється нуль-поставками до m + n – 1, але так щоб сукупність заповнених клітин разом з нуль-поставками не утворювала циклів.
Опорний план задачі побудуємо методом ‘найкращого’ елементу в матриці.
У матриці найменша відстань – це відстань від складу D1 до господарства S1, яка дорівнює 5 км. Потреба в добривах S1 господарства – 150 т, тому в клітину (D1,S1) ставимо число 150 (транспортна таблиця 1). Але на D1 складі ще залишається добрива в кількості 200-150 = 50т. Ці добрива доцільно перевезти до господарства S2 (відстань 6 км), тому в клітину (D1,S2) ставимо число 50.
Переходимо до розподілу мінеральних добрив із D2 складу. Найближча відстань від D2 складу до S1 господарства (8 км), але потреба в добривах для S1 господарства уже задоволена. Тому добрива перевозимо до господарства S2 (9 км) в кількості 100 – 50 = 50 т, а до S3 (10 км) – 200 - 50 = 150 т. Ставимо в клітинах (D2,S2) і (D2,S3) відповідно числа 50 і 150.
Зі складу D3 мінеральні добрива можна перевезти тільки до господарства S4, тому що три перших свої потреби вже задовольнили. Ставимо в клітину (D3,S4) число 200.
Застосування методу потенціалів можливо тільки тоді, коли кількість базисних змінних (заповнених клітин) в транспортній таблиці дорівнює m + n – 1 = 3 + 4 – 1 = 6, де m – кількість рядків (складів), а n – кількість колонок (господарств).
В транспортній таблиці 1 кількість заповнених клітин дорівнює 5, тому вводимо ‘нуль-поставку’, але так, щоб заповнені клітини разом з ‘нуль-поставкою’ не складали циклу (поняття ‘цикл’ буде розглянуто нижче). Обсяг вантажоперевезень побудованого опорного плану складає:
Z1=1505+506+509+15010+07+20020 = 7000ткм
Для перевірки оптимальності задачі визначимо потенціали рядків (ui) та колонок ( vj).
Умови оптимальності розв'язку транспортної задачі такі:
ui+vj=cij – для базисних змінних (заповнені клітини);
ui+ vj cij – для небазисних змінних (незаповнені клітини) при розв'язанні задачі на мінімум цільової функції;
ui+vj cij – для небазисних змінних (незаповнені клітини) при розв'язанні задачі на максимум цільової функції, де сij – оцінка клітини (відстань від і-го складу до j-го господарства).
Транспортна таблиця 1
Склади |
Господарства |
Наявність добрив, т |
Потенціали рядків, uі |
|||||||
S1 |
S2 |
S3 |
S4 |
|||||||
D1 |
150 |
5 |
50 |
6 |
|
7 |
|
8 |
200 |
u1=0 |
- |
|
|
|
|
|
+ |
|
|||
D2 |
|
8 |
50 |
9 |
150 |
10 |
|
11 |
200 |
u2=3 |
D3 |
0 |
7 |
|
14 |
|
15 |
200 |
20 |
200 |
u3=2 |
+ |
|
|
|
|
|
- |
|
|||
Потреба в добривах, т |
150 |
|
100 |
|
150 |
|
200 |
|
600 |
|
Потенціали колонок, vj |
v1=5 |
v2=6 |
v3=7 |
v4=18 |
|
|
Складемо систему рівнянь для заповнених клітин транспортної таблиці 2:
u1+v1 = 5; u1+v2 = 6; u2+v2 = 9;
u2+v3 = 10; u3+v1= 7; u3+v4= 20
Поклавши, наприклад, u1=0, одержимо значення потенціалів, які запишемо в транспортну таблицю 2.
v1=5-u1=5-0=5 v2=6-u1=6-0=6............u2=9-v2=9-6=3 v3=10-u2=10-3=7 u3=7-v1=7-5=2 v4=20-u3=20-2=18
Перевіримо виконання умови оптимальності для незаповнених клітин
(ui+ vj cij) :
-:клітина (D1,S3) 0+7=7 – умова виконується; клітина (D1,S4) 0+18>8 – умова не виконується на 10 одиниць; клітина (D2,S1) 3+5=8 – умова виконується; клітина (D2,S3) 2+6 <14 – умова виконується;клітина (D2,S4) 3+18 >11 – умова не виконується на 10 одиниць; клітина (D3,S3) 2+7 <15 – умова виконується.
Таким чином, опорний план не оптимальний, тому що умова оптимальності не виконується для клітин (D1,S4) та (D2,S4). Цей план можна наблизити до оптимального, якщо до однієї з ‘неоптимальних’ клітин побудувати ‘цикл’. При цьому вибирається та клітина, для якої різниця між сумою потенціалів і оцінкою клітини найбільша. В зв'язку з тим, що для клітини (D1,S4) та (D2,S4) ця різниця однакова, вибираємо ту, де оцінка клітини найменша (D1,S4). В транспортній таблиці 2 побудуємо цикл до клітини (D1,S4).
Цикл – це набір клітин, який будується за такими правилами:
Перша клітина – це вибрана незаповнена, а всі інші клітини циклу повинні бути заповненими.
Будь-якому рядку або будь-якій колонці можуть належати тільки дві вершини циклу.
Перехід від однієї клітини до іншої може бути тільки в заповненій клітині під кутом 90о.
Цикл повинен замикатися на першій (вибраній) незаповненій клітині (тобто там, де він починався). Цикли можуть бути різної конфігурації, наприклад:
Після побудови циклу в незаповнену клітину (D1,S4) ставимо знак ‘+’, а далі у вершинах циклу знаки ‘-’, ‘+’, ‘-’ таким чином, щоб у будь-якому рядку або у будь-якій колонці були тільки протилежні знаки, тобто ‘+’ і ‘-’. Отримуємо додатній ‘півцикл’ з вершинами (D1,S4) та (D3,S1) і від'ємний ‘півцикл’ з вершинами (D1,S1) та (D3,S4). У від'ємному ‘півциклі’ знаходимо вершину з найменшим числом. Це клітина (D1,S1) з числом 150. Тепер це число додаємо в клітинах із знаком ‘+’ і віднімаємо в клітинах із знаком ‘-’. В результаті отримуємо новий базисний розв'язок транспортної задачі (транспортна таблиця 2).
Транспортна таблиця 2
Склади |
Господарства |
Наявність добрив, т |
uі |
|||||||
S1 |
S2 |
S3 |
S4 |
|||||||
D1 |
|
5 |
50 |
6 |
|
7 |
150 |
8 |
200 |
0 |
|
|
- |
|
|
|
+ |
|
|
|
|
D2
|
|
8 |
50 |
9 |
150 |
10 |
|
11 |
200 |
3 |
D3 |
150 |
7 |
|
14 |
|
15 |
50 |
20 |
200 |
12 |
|
|
+ |
|
|
|
- |
|
|
|
|
Потреба в добривах, т |
150 |
100 |
150 |
200 |
600 |
|
||||
vj |
v1=-5 |
v2=6 |
v3=7 |
v4=8 |
|
|
Обсяг вантажоперевезень складає:
Z2 = 506+1508+509+15010+1507+5020=5450 ткм
Розв'язок в транспортній таблиці 2 знову треба перевірити на оптимальність. Для цього складемо систему рівнянь для заповнених клітин (ui+vj=cij)
u1+v2 = 6; u1+v4 = 8; u2+v2 = 9;
u2+v3 = 10; u3+v1= 7; u3+v4 = 20
Поклавши u1=0, одержимо потенціали
v2=6-u1=6-0=6 v4=8-u1=8-0=8 u2=9-v2=9-6=3
v3=10-u2=10-3=7 u3=20-v4=20-8=12 v1=7-u3=7-12=-5
які запишемо в транспортну таблицю 2.
В транспортній таблиці 2 перевіримо виконання умови оптимальності для незаповнених клітин (ui+vj cij):
клітина (D1,S1) 0+(-5)< 5 – умова виконується;
клітина (D1,S3) 0+7=7 – умова виконується;
клітина (D2,S1) 3+(-5)<8 – умова виконується
- клітина (D2,S4) 3+8 =11 – умова виконується;
клітина (D3,S2) 12+6 >14 – умова не виконується на 4 одиниці;
клітина (D3,S3) 12+7 >15 – умова не виконується на 4 одиниці;
В транспортній таблиці 2 розв'язок не оптимальний, тому що для клітин (D3,S2) та (D3,S3) умова оптимальності не виконується. До клітини (D3,S3) в транспортній таблиці 2 побудуємо цикл. У від'ємному ‘півциклі’ знаходимо найменше число (50) і додаємо його у заповнених клітинах із знаком ‘+’ та віднімаємо у клітинах із знаком ‘-’. В результаті отримуємо новий розв'язок транспортної задачі, який запишемо в транспортній таблиці 3.
Транспортна таблиця 3
Склади |
Господарства |
Наяв ність |
uі |
|||||||
S1 |
S2 |
S3 |
S4 |
|||||||
D1 |
|
5 |
0 |
6 |
|
7 |
200 |
8 |
200 |
0 |
D2 |
|
8 |
100 |
9 |
100 |
10 |
|
11 |
200 |
3 |
D3 |
150 |
7 |
|
14 |
50 |
15 |
|
20 |
200 |
8 |
Потреба
|
150 |
100 |
150 |
200 |
600 |
|
||||
vj |
-1 |
6 |
7 |
8 |
|
|
Z3= 2008+01009+10010+1507+5015=5300 ткм
Перевіримо опорний план в транспортній таблиці 3 на оптимальність. В зв'язку з тим, що в транспортній таблиці 3 не виконується умова m+n-1, в клітину (D1,S2) вводимо ‘нуль-поставку’. Поклавши u1=0, одержимо значення потенціалів: v1= -1, v2 = 6, v3 = 7, v4 = 8, u2 =3, u3=8
Перевіримо виконання умови оптимальності для незаповнених клітин (ui+vj cij):
клітина (D1,S1) 0+(-1)< 5– умова виконується;
клітина(D1,S3) 0+7=7 – умова виконується;
клітина (D2,S1) 3+(-1)<8 – умова виконується;
клітина (D2,S4) 3+8 =11 – умова виконується;
клітина (D3,S2) 8+6 =14 – умова виконується;
клітина (D3,S4) 8+8 <20 – умова виконується.
Таким чином, розв'язок задачі в транспортній таблиці 3 є оптимальним.
Висновки. Мінеральні добрива потрібно перевозити:
- зі складу D1 до господарства S4–200 т;
- зі складу D2 до господарства S2 –100 т і до господарства S3 –100 т;
- зі складу D3 до господарства S1 –150 т і до господарства S3–50 т.
Обсяг вантажоперевезень буде дорівнювати 5300 ткм, що на 1700 ткм менше, ніж у початковому плані (Z1-Z3=7000-5300).
Зауваження 1. Якщо сумарні запаси вантажу не дорівнюють сумарним потребам у ньому, то така транспортна модель називається відкритою. В зв'язку з тим, що метод потенціалів можна застосовувати тільки до закритої транспортної задачі, відкрита транспортна задача перетворюється у закриту шляхом введення фіктивного постачальника або фіктивного споживача. Оцінки всіх його клітин дорівнюють нулю.
Нехай, наприклад, в наведеній транспортній задачі наявність мінеральних добрив на D3 складі дорівнює не 200 т, а 250 т. Тоді сумарна наявність добрив буде дорівнювати 200 + 200 + 250 =650 т, а потреба в них господарств дорівнює – 150 + 100 + 150 + 200 = 600 т.
Введемо фіктивне господарство, потреба в мінеральних добривах для якого буде дорівнювати 650 – 600 = 50 т. Тоді відкрита модель перетворюється в закриту і розв'язується за допомогою розглянутого вище методу потенціалів
Тоді транспортна таблиця буде мати такий вигляд:
Склади |
Господарства |
Наявність добрив, т |
||||
S1 |
S2 |
S3 |
S4 |
S5 -фіктивне |
||
D1 |
5 |
6 |
7 |
8 |
0 |
200 |
D2 |
8 |
9 |
10 |
11 |
0 |
200 |
D3 |
7 |
14 |
15 |
20 |
0 |
250 |
Потреба в добривах, т |
150 |
100 |
150 |
200 |
50 |
650 |
З
Х1
Задача 4. Потрібно скласти такий план розміщення сортів озимої пшениці за попередниками, щоб очікуваниваловий збір зерна був максимальним. Площі попередників та посівні площі сортів озимої пшениці наведені в таблицях 4.1, 4.2, а середня урожайність сортів озимої пшениціза попередниками в таблиці 4.3.
Таблиця 4.1