ЗАДАЧА 1
Скласти модель оптимального випуску продукції для цеху кондитерської фабрики. Види продукції, що випускається (М), види основної сировини (П) і його запаси, норми витрат сировини на одиницю, рівні прибутку наведені в таблиці. Розрахувати план і провести його аналіз.
Зміст завдання.
Цех кондитерської фабрики виробляє три асортиментні групи цукерок, умовно позначені М 1, М 2, М 3 / в од. /.
Для їх виробництва використовуються основні види ресурсів / сировини / трьох видів, умовно названих П 1, П 2, П 3 / в од. /.
Витрата кожного ресурсу на виробництво одиниці продукції є заданою величиною, визначається за рецептурою і позначається символами а 11, a 12 ..., а 33, де а - норма витрати, перша підрядковий 1 - номер ресурсу, друга підрядковий 1, 2, 3 - номер асортиментної групи цукерок.
Наявність кожного ресурсу для виробництва всіх, груп цукерок приймається як відома величина і позначається символами в 1, в 2, в 3.
Прибуток на продукцію також приймається як відома величина і позначається символами c 1, c 2, с 3.
Перераховані параметри є величинами відомими і виражаються в єдиних одиницях виміру, крім прибутку. Прибуток або інший який показник, що є критерієм оптимальності, виражається в одиницях вимірювання доходу / наприклад, прибутку /, одержуваного від виробництва одиниці продукції в грошовому чи іншому якому-небудь вираженні.
Оскільки рішення завдання полягає в пошуку такого плану виробництва, який забезпечував би в прийнятих умовах найбільший дохід, приймаються ті величини, які є невідомими і які позначають кількості кожної групи цукерок, що включаються до плану виробництва: x 1 для M 1; х 2 для М 2; х 3 для М 3.
Економіко-математична модель у символічному вигляді.
Система обмежень
Цільова функція / сумарний дохід / F = з 1 х 1 + з 2 х 2 + з 3 х 3 = мах
Умови неотрицательности невідомих х 1 ≥ 0, х 2 ≥ 0, х 3 ≥ 0
Символічна модель, наповнена чисельної інформацією, буде мати наступний вигляд:
2x 1 + 4x 2 + 3x 3 ≤ 266
1x 1 + 3x 2 + 4x 3 ≤ 200
3x 1 + 2x 2 + 1x 3 ≤ 303
Прибуток від реалізації продукції, що випускається повинна бути максимальною, тобто F = 20х 1 + 24х 2 + 28х 3 = Max;
Рішення завдання.
Для вирішення завдання симплексним методом нерівності перетворюються на еквівалентні рівності шляхом додавання в кожне нерівність по одному додатковому невідомому з коефіцієнтом + 1 і нульовим рівнянням прибутку. Для зручності розрахунків ліві і праві частини рівнянь міняються місцями. У цьому випадку вихідні нерівності приймуть вид симплексних рівнянь:
266 = 2x 1 + 4x 2 + 3x 3 + 1x 4
200 = 1x 1 + 3x 2 + 4x 3 + 1x 5
303 = 3x 1 + 2х 2 + 1x 3 + 1x 6
F = 20х 1 + 24х 2 + 28х 3 + 0x 4 + 0x 5 + 0x 6
Коефіцієнти при невідомих записуються в симплексного таблиці, в якій виконуються розрахунки і відображаються отримані результати.
Вихідна таблиця
У стовпцях таблиці записують: в першому (C j) - прибуток одиниці продукції, яка вводиться в план випуску, у другому (Р 0) - невідомі, що включаються до плану, у третьому (Х 0) - вільні величини, у решті - коефіцієнти при невідомих рівнянь. У верхній частині цих стовпців відображаються коефіцієнти при невідомих цільової функції.
У нижньому рядку (цільової) записуються одержувані розрахунковим шляхом показники: у стовпці х 0 - сумарний прибуток планового випуску, в інших стовпцях - прибуток одиниці продукції з негативним знаком.
В останніх трьох стовпцях коефіцієнти при додаткових невідомих, що дорівнюють одиниці, розташовані по діагоналі. Ця частина таблиці, звана одиничної підматриць, необхідна для обчислювальних і аналітичних цілей.
При вирішенні задач на максимум цільової функції наявність у цільової рядку негативних чисел вказує на можливість початку чи продовження виконання завдання. Порядок вирішення такий: з негативних чисел цільової рядка вибирається найбільше за модулем. Стовпець, в якому воно знаходиться, приймається за ключовою (або що дозволяє) і для зручності розрахунків виділяється. У нашому прикладі таким стовпцем буде Х 3, що має в цільової рядку найбільшу за модулем величину -28.
Перший ітерація
Потім елементи стовпця Х 0 (вільні величини) ділять на відповідні коефіцієнти ключового стовпця і отримані результати зіставляють між собою. Рядок з найменшим ставленням приймається за ключову і також для зручності виділяється. У нашому випадку 266 / 3 = 88,7; 200 / 4 = 50; 303 / 1 = 303. Найменша ставлення 50 має терміну х 5, вона і буде ключовою. Ключовий елемент 4.
Далі елементи таблиці перетворюються і записуються в нову таблицю. Спочатку перетворять елементи ключовою рядка шляхом розподілу їх на ключовий елемент. Перетворені елементи записують у тому ж самому місці.
У стовпцях Р о і C j займають місце вводиться в план невідома х 3 із прибутком 28 (ітерація 1-а). Інші елементи перетворюються за наступним правилом:
- Для преутвореного елемента в його стовпці знаходять елемент ключовий рядки, а в його рядку - елемент ключового стовпця;
- Відповідні елементи ключовою рядки і ключового стовпця перемножуються і отриманий добуток ділять на ключовий момент;
- Частка від ділення віднімають із значення елемента, яке він мав до перетворення, і отриманий результат буде перетворений елементом, який записується в нову таблицю в тому ж самому місці. Слідуючи цьому правилу, перетворення елементів стовпця х 0 буде:
Включення на першій ітерації в план невідомою х 3 забезпечить суму прибутку 1400 руб.
Рішення завдання триває, так як в цільової рядку два негативних елемента. Найбільший за модулем елемент -13. Він знаходиться в стовпці х 1, який приймається за ключовою, а ключовий рядком буде х 6 (116:1,3 = 92,8; 50:0,3 = 200; 253:2,8 = 92), ключовим елементом 2, 8. Елементи таблиці перетворюються в тому ж порядку по викладеному правилом і записуються в нову таблицю.
2-а ітерація
В останній таблиці цільовий рядок має тільки позитивні елементи. Це означає, що складений план оптимальний і подальше поліпшення його неможливо.
Як видно з таблиці, оптимальний план передбачає випуск продукції П 1 27 од. (Х 1 = 27), П березня 1992 од. (Х 3 = 92), додаткового невідомого П 4 1 од. (Х 4 = 1). П 2 і додаткові невідомі в план не ввійшли, отже, х 2 = 0, х 5 = 0 х 6 = 0. Підставивши значення невідомих у рівняння, отримаємо:
2 * 92 + 4 * 0 + 3 * 27 + 1 = 266
1 * 92 + 3 * 0 + 4 * 27 + 0 = 200
3 * 92 + 2 * 0 + 1 * 27 + 0 = 303
F = 20 * 92 + 24 * 0 + 27 * 28 = 2596
Аналіз оптимального плану.
а) Запаси сировини трьох видів використовуються не повністю, тому що х 4 = 1, а х 5 = х 6 = 0.
б) Розглянемо елементи матриці.
Від випуску продукції II слід відмовитися.
Елементи стовпця х 5 показують, що збільшення запасів цукру на I од. (Х 5 = 1) дозволить збільшити випуск продукції III виду на 0,3 од. Сума прибутку збільшиться на 5,8 руб.
Елементи стовпця х 6 показують, що збільшення запасів жиру на I од. (Х 6 = 1) дозволить зменшити випуск тільки продукції III виду на 0,1 од. (27 - 0.1) Сума прибутку збільшиться на 4,7 руб.
Зниження запасів сировини призводить до змін випуску продукції і суми прибутку в зворотному порядку.
Елементи цільової рядки оптимального плану називаються подвійними оцінками, які визначають величину зміни прибутку при зміні запасів сировини на I од.
ЗАВДАННЯ 2
Потрібно визначити мінімальну за вартістю суміш сировини для виготовлення харчових концентратів, які повинні містити живильні речовини (П). Ці речовини містяться в сировині (М) в різних поєднаннях. Вміст поживних речовин у сировині й готовому продукті, а також ціна на кожен вид сировини показані в таблиці.
Види сировини, що використовується умовно позначені через М 1, М 2, М 3; вміст поживних речовин у сировині й готовому продукті позначені П 1, П 2, П 3, П 3.
Початкові умови завдання виражаються нерівностями:
1х 1 + 1х 2 + 0х 3 ≥ 50
4х 1 + 1х 2 + 3х 3 ≥ 140
1х 1 + 4х 2 + 1х 3 ≥ 127
0х 1 + 3х 2 + 2х 3 ≥ 80
F = 8х 1 + 12х 2 + 10х 3 = min
Помноживши обидві частини нерівностей на -1, отримаємо систему з іншим напрямом знака нерівностей:
-1х 1 - 1х 2 - 0х 3 ≥ -50
-4х 1 - 1х 2 - 3х 3 ≥ -140
-1х 1 - 4х 2 - 1х 3 ≥ -127
0х 1 - 3х 2 - 2х 3 ≥ -80
F = 8х 1 + 12х 2 + 10х 3 = min
Перетворимо нерівності в еквівалентні рівності за допомогою додаткових невідомих. Симплексних рівняння будуть наступними:
-50 =-1х 1 - 1х 2 - 0х 3 + 1х 4 + 0х 5 + 0х 6 + 0х 7
-140 =-4х 1 - 1х 2 - 3х 3 + 0х 4 + 1х 5 + 0х 6 + 0х 7
-127 =-1х 1 - 4х 2 - 1х 3 + 0х 4 + 0х 5 + 1х 6 + 0х 7
-80 = 0х 1 - 3х 2 - 2х 3 + 0х 4 + 0х 5 + 0х 6 + 1х 7
F = 8х 1 + 12х 2 + 10х 3 + 0х 4 + 0х 5 + 0х 6 + 0х 7 = min
Записані рівняння відрізняються від тих, які нами розглядалися вище, тим, що коефіцієнти при основних невідомих і вільні члени мають негативні знаки.
Вирішення таких завдань проводиться двоїстим симплексним методом. Система симплексних рівнянь записується в таблиці.
Елементи цільової рядка розраховують за звичайними правилами і отримують негативні знаки.
На відміну від обчислювальної процедури основного симплексного методу розв'язання задач двоїстим методом виконується у зворотному порядку.
У підсумковому стовпці вільні числа мають негативні знаки. Це є свідченням того, що даний план не можна вважати припустимим, тому що він суперечить економічному глузду. План можна вважати припустимим тільки тоді, коли в підсумковому стовпці не буде негативних чисел.
Ліквідація негативних чисел у підсумковому стовпці починається з найбільшого за абсолютною величиною. У нашому прикладі таким числом є (-140). Рядок х 5, в якій знаходиться це число, приймається за ключову і відповідно виділяється.
Визначивши ключову рядок, знаходимо ключовий стовпець. Для цього потрібно елементи цільової рядки розділити на елементи ключовою рядки і з отриманих відносин вибрати найменше. Стовпець, що має найменше відношення, приймається за ключовою і так само як ключова рядок, виділяється.
Стовпці х 1, х 2, х 3 будуть мати такі відносини:
Найменша відношення має стовпець х 1, він і буде ключовим.
Визначивши ключову рядок, ключовою стовпець і ключове число, за звичайними правилами перетворюються всі елементи матриці і записуються в новій таблиці.
1-а ітерація
Після перетворення елементів у підсумковому стовпці залишилося ще три негативних числа в рядку х 4, х 6 і х 7. Найбільшим за абсолютною величиною є число в рядку х 6. Цей рядок буде прийнята за ключову для подальшого розрахунку. Ключовий стовбець визначається за найменшим відношенню елементів цільової рядки до елементів ключової рядка. Їм буде стовпець х 2. Вводимо цей вид сировини в програму замість невідомого х 6. За загальними правилами перетворимо елементи матриці.
2-а ітерація
Після перетворення елементів у підсумковому стовпці залишилося ще одне негативне число в рядку х 7. Цей рядок буде прийнята за ключову для подальшого розрахунку. Ключовий стовбець визначається за найменшим відношенню елементів цільової рядки до елементів ключової рядка. Їм буде стовпець х 3. Вводимо цей вид сировини в програму замість невідомого х 7. За загальними правилами перетворимо елементи матриці.
У таблиці записані перетворені числа, отримані на 3-й ітерації. У підсумковому стовпці всі негативні числа зникли, значить отриманий план є допустимим і одночасно оптимальним. Висновок про те, що план отримано оптимальний, дозволяють зробити елементи цільової рядка. Всі вони негативні або дорівнювати нулю, що свідчить про оптимальність результату при вирішенні завдань на мінімум цільової функції.
Третя ітерація Скласти модель оптимального випуску продукції для цеху кондитерської фабрики. Види продукції, що випускається (М), види основної сировини (П) і його запаси, норми витрат сировини на одиницю, рівні прибутку наведені в таблиці. Розрахувати план і провести його аналіз.
| Види сировини | Витрати сировини на одиницю продукції | Загальний запас сировини, од. | |||
| М 1 | М 2 | М 3 | |||
| П 1 | 2 | 4 | 3 | 266 | |
| П 2 | 1 | 3 | 4 | 200 | |
| П 3 | 3 | 2 | 1 | 303 | |
| Рівень прибутку на од. продукції | 20 | 24 | 28 | ||
Цех кондитерської фабрики виробляє три асортиментні групи цукерок, умовно позначені М 1, М 2, М 3 / в од. /.
Для їх виробництва використовуються основні види ресурсів / сировини / трьох видів, умовно названих П 1, П 2, П 3 / в од. /.
Витрата кожного ресурсу на виробництво одиниці продукції є заданою величиною, визначається за рецептурою і позначається символами а 11, a 12 ..., а 33, де а - норма витрати, перша підрядковий 1 - номер ресурсу, друга підрядковий 1, 2, 3 - номер асортиментної групи цукерок.
Наявність кожного ресурсу для виробництва всіх, груп цукерок приймається як відома величина і позначається символами в 1, в 2, в 3.
Прибуток на продукцію також приймається як відома величина і позначається символами c 1, c 2, с 3.
Перераховані параметри є величинами відомими і виражаються в єдиних одиницях виміру, крім прибутку. Прибуток або інший який показник, що є критерієм оптимальності, виражається в одиницях вимірювання доходу / наприклад, прибутку /, одержуваного від виробництва одиниці продукції в грошовому чи іншому якому-небудь вираженні.
Оскільки рішення завдання полягає в пошуку такого плану виробництва, який забезпечував би в прийнятих умовах найбільший дохід, приймаються ті величини, які є невідомими і які позначають кількості кожної групи цукерок, що включаються до плану виробництва: x 1 для M 1; х 2 для М 2; х 3 для М 3.
Економіко-математична модель у символічному вигляді.
Система обмежень
Цільова функція / сумарний дохід / F = з 1 х 1 + з 2 х 2 + з 3 х 3 = мах
Умови неотрицательности невідомих х 1 ≥ 0, х 2 ≥ 0, х 3 ≥ 0
Символічна модель, наповнена чисельної інформацією, буде мати наступний вигляд:
2x 1 + 4x 2 + 3x 3 ≤ 266
1x 1 + 3x 2 + 4x 3 ≤ 200
3x 1 + 2x 2 + 1x 3 ≤ 303
Прибуток від реалізації продукції, що випускається повинна бути максимальною, тобто F = 20х 1 + 24х 2 + 28х 3 = Max;
Рішення завдання.
Для вирішення завдання симплексним методом нерівності перетворюються на еквівалентні рівності шляхом додавання в кожне нерівність по одному додатковому невідомому з коефіцієнтом + 1 і нульовим рівнянням прибутку. Для зручності розрахунків ліві і праві частини рівнянь міняються місцями. У цьому випадку вихідні нерівності приймуть вид симплексних рівнянь:
266 = 2x 1 + 4x 2 + 3x 3 + 1x 4
200 = 1x 1 + 3x 2 + 4x 3 + 1x 5
303 = 3x 1 + 2х 2 + 1x 3 + 1x 6
F = 20х 1 + 24х 2 + 28х 3 + 0x 4 + 0x 5 + 0x 6
Коефіцієнти при невідомих записуються в симплексного таблиці, в якій виконуються розрахунки і відображаються отримані результати.
Вихідна таблиця
| c j | p 0 | x 0 | 20 | 24 | 28 | 0 | 0 | 0 |
| x 1 | х 2 | х 3 | х 4 | х 5 | х 6 | |||
| 0 | х 4 | 266 | 2 | 4 | 3 | 1 | 0 | 0 |
| 0 | х 5 | 200 | 1 | 3 | 4 | 0 | 1 | 0 |
| 0 | х 6 | 303 | 3 | 2 | 1 | 0 | 0 | 1 |
| Z j - C j | 0 | -20 | -24 | -28 | 0 | 0 | 0 | |
У нижньому рядку (цільової) записуються одержувані розрахунковим шляхом показники: у стовпці х 0 - сумарний прибуток планового випуску, в інших стовпцях - прибуток одиниці продукції з негативним знаком.
В останніх трьох стовпцях коефіцієнти при додаткових невідомих, що дорівнюють одиниці, розташовані по діагоналі. Ця частина таблиці, звана одиничної підматриць, необхідна для обчислювальних і аналітичних цілей.
При вирішенні задач на максимум цільової функції наявність у цільової рядку негативних чисел вказує на можливість початку чи продовження виконання завдання. Порядок вирішення такий: з негативних чисел цільової рядка вибирається найбільше за модулем. Стовпець, в якому воно знаходиться, приймається за ключовою (або що дозволяє) і для зручності розрахунків виділяється. У нашому прикладі таким стовпцем буде Х 3, що має в цільової рядку найбільшу за модулем величину -28.
Перший ітерація
| c j | p 1 | x 0 | x 1 | х 2 | х 3 | х 4 | х 5 | х 6 |
| 0 | х 4 | 116 | 1.3 | 1.75 | 0 | 1 | -1 | 0 |
| 28 | х 3 | 50 | 0.3 | 0.75 | 1 | 0 | 0.3 | 0 |
| 0 | х 6 | 253 | 2.8 | 1.25 | 0 | 0 | -0 | 1 |
| Z j - C j | 1400 | -13 | -3 | 0 | 0 | 7 | 0 | |
Далі елементи таблиці перетворюються і записуються в нову таблицю. Спочатку перетворять елементи ключовою рядка шляхом розподілу їх на ключовий елемент. Перетворені елементи записують у тому ж самому місці.
У стовпцях Р о і C j займають місце вводиться в план невідома х 3 із прибутком 28 (ітерація 1-а). Інші елементи перетворюються за наступним правилом:
- Для преутвореного елемента в його стовпці знаходять елемент ключовий рядки, а в його рядку - елемент ключового стовпця;
- Відповідні елементи ключовою рядки і ключового стовпця перемножуються і отриманий добуток ділять на ключовий момент;
- Частка від ділення віднімають із значення елемента, яке він мав до перетворення, і отриманий результат буде перетворений елементом, який записується в нову таблицю в тому ж самому місці. Слідуючи цьому правилу, перетворення елементів стовпця х 0 буде:
Включення на першій ітерації в план невідомою х 3 забезпечить суму прибутку 1400 руб.
Рішення завдання триває, так як в цільової рядку два негативних елемента. Найбільший за модулем елемент -13. Він знаходиться в стовпці х 1, який приймається за ключовою, а ключовий рядком буде х 6 (116:1,3 = 92,8; 50:0,3 = 200; 253:2,8 = 92), ключовим елементом 2, 8. Елементи таблиці перетворюються в тому ж порядку по викладеному правилом і записуються в нову таблицю.
2-а ітерація
| c j | p 2 | x 0 | x 1 | х 2 | х 3 | х 4 | х 5 | х 6 |
| 0 | х 4 | 1 | 0 | 1.18 | 0 | 1 | -1 | -0.5 |
| 28 | х 3 | 27 | 0 | 0.64 | 1 | 0 | 0.3 | -0.1 |
| 13 | х 1 | 92 | 1 | 0 | 0 | 0 | 0 | 0 |
| Z j - C j | 2596 | 0 | 2.91 | 0 | 0 | 5.8 | 4.7 | |
Як видно з таблиці, оптимальний план передбачає випуск продукції П 1 27 од. (Х 1 = 27), П березня 1992 од. (Х 3 = 92), додаткового невідомого П 4 1 од. (Х 4 = 1). П 2 і додаткові невідомі в план не ввійшли, отже, х 2 = 0, х 5 = 0 х 6 = 0. Підставивши значення невідомих у рівняння, отримаємо:
2 * 92 + 4 * 0 + 3 * 27 + 1 = 266
1 * 92 + 3 * 0 + 4 * 27 + 0 = 200
3 * 92 + 2 * 0 + 1 * 27 + 0 = 303
F = 20 * 92 + 24 * 0 + 27 * 28 = 2596
Аналіз оптимального плану.
а) Запаси сировини трьох видів використовуються не повністю, тому що х 4 = 1, а х 5 = х 6 = 0.
б) Розглянемо елементи матриці.
Від випуску продукції II слід відмовитися.
Елементи стовпця х 5 показують, що збільшення запасів цукру на I од. (Х 5 = 1) дозволить збільшити випуск продукції III виду на 0,3 од. Сума прибутку збільшиться на 5,8 руб.
Елементи стовпця х 6 показують, що збільшення запасів жиру на I од. (Х 6 = 1) дозволить зменшити випуск тільки продукції III виду на 0,1 од. (27 - 0.1) Сума прибутку збільшиться на 4,7 руб.
Зниження запасів сировини призводить до змін випуску продукції і суми прибутку в зворотному порядку.
Елементи цільової рядки оптимального плану називаються подвійними оцінками, які визначають величину зміни прибутку при зміні запасів сировини на I од.
ЗАВДАННЯ 2
Потрібно визначити мінімальну за вартістю суміш сировини для виготовлення харчових концентратів, які повинні містити живильні речовини (П). Ці речовини містяться в сировині (М) в різних поєднаннях. Вміст поживних речовин у сировині й готовому продукті, а також ціна на кожен вид сировини показані в таблиці.
| Живильні речовини | Види сировини | Мінімальний вміст (Одиниць) поживних речовин в готовому продукті | ||
| M 1 | М 2 | М 3 | ||
| П 1 | 1 | 1 | 0 | 50 |
| П 2 | 4 | 1 | 3 | 140 |
| П 3 | 1 | 4 | 1 | 127 |
| П 4 | 0 | 3 | 2 | 80 |
| Ціна за одиницю сировини, руб. | 8 | 12 | 10 | |
Початкові умови завдання виражаються нерівностями:
1х 1 + 1х 2 + 0х 3 ≥ 50
4х 1 + 1х 2 + 3х 3 ≥ 140
1х 1 + 4х 2 + 1х 3 ≥ 127
0х 1 + 3х 2 + 2х 3 ≥ 80
F = 8х 1 + 12х 2 + 10х 3 = min
Помноживши обидві частини нерівностей на -1, отримаємо систему з іншим напрямом знака нерівностей:
-1х 1 - 1х 2 - 0х 3 ≥ -50
-4х 1 - 1х 2 - 3х 3 ≥ -140
-1х 1 - 4х 2 - 1х 3 ≥ -127
0х 1 - 3х 2 - 2х 3 ≥ -80
F = 8х 1 + 12х 2 + 10х 3 = min
Перетворимо нерівності в еквівалентні рівності за допомогою додаткових невідомих. Симплексних рівняння будуть наступними:
-50 =-1х 1 - 1х 2 - 0х 3 + 1х 4 + 0х 5 + 0х 6 + 0х 7
-140 =-4х 1 - 1х 2 - 3х 3 + 0х 4 + 1х 5 + 0х 6 + 0х 7
-127 =-1х 1 - 4х 2 - 1х 3 + 0х 4 + 0х 5 + 1х 6 + 0х 7
-80 = 0х 1 - 3х 2 - 2х 3 + 0х 4 + 0х 5 + 0х 6 + 1х 7
F = 8х 1 + 12х 2 + 10х 3 + 0х 4 + 0х 5 + 0х 6 + 0х 7 = min
Записані рівняння відрізняються від тих, які нами розглядалися вище, тим, що коефіцієнти при основних невідомих і вільні члени мають негативні знаки.
Вирішення таких завдань проводиться двоїстим симплексним методом. Система симплексних рівнянь записується в таблиці.
| c j | p 0 | x 0 | 8 | 12 | 10 | 0 | 0 | 0 | 0 |
| x 1 | х 2 | х 3 | х 4 | х 5 | х 6 | х 7 | |||
| 0 | х 4 | -50 | -1 | -1 | 0 | 1 | 0 | 0 | 0 |
| 0 | х 5 | -140 | -4 | -1 | -3 | 0 | 1 | 0 | 0 |
| 0 | х 6 | -127 | -1 | -4 | -1 | 0 | 0 | 1 | 0 |
| 0 | х 7 | -80 | 0 | -3 | -2 | 0 | 0 | 0 | 1 |
| Z j - C j | 0 | -8 | -12 | -10 | 0 | 0 | 0 | 0 | |
На відміну від обчислювальної процедури основного симплексного методу розв'язання задач двоїстим методом виконується у зворотному порядку.
У підсумковому стовпці вільні числа мають негативні знаки. Це є свідченням того, що даний план не можна вважати припустимим, тому що він суперечить економічному глузду. План можна вважати припустимим тільки тоді, коли в підсумковому стовпці не буде негативних чисел.
Ліквідація негативних чисел у підсумковому стовпці починається з найбільшого за абсолютною величиною. У нашому прикладі таким числом є (-140). Рядок х 5, в якій знаходиться це число, приймається за ключову і відповідно виділяється.
Визначивши ключову рядок, знаходимо ключовий стовпець. Для цього потрібно елементи цільової рядки розділити на елементи ключовою рядки і з отриманих відносин вибрати найменше. Стовпець, що має найменше відношення, приймається за ключовою і так само як ключова рядок, виділяється.
Стовпці х 1, х 2, х 3 будуть мати такі відносини:
Найменша відношення має стовпець х 1, він і буде ключовим.
Визначивши ключову рядок, ключовою стовпець і ключове число, за звичайними правилами перетворюються всі елементи матриці і записуються в новій таблиці.
1-а ітерація
| c j | p 0 | x 0 | 18 | 15 | 24 | 0 | 0 | 0 | 0 |
| x 1 | х 2 | х 3 | х 4 | х 5 | х 6 | х 7 | |||
| 0 | х 4 | -15 | 0 | -0.75 | 0.75 | 1 | -0.25 | 0 | 0 |
| 8 | х 1 | 35 | 1 | 0.25 | 0.75 | 0 | -0.25 | 0 | 0 |
| 0 | х 6 | -92 | 0 | -3.75 | -0.25 | 0 | -0.25 | 1 | 0 |
| 0 | х 7 | -80 | 0 | -3 | -2 | 0 | 0 | 0 | 1 |
| Z j - C j | 280 | 0 | -10 | -4 | 0 | -2 | 0 | 0 | |
2-а ітерація
| c j | p 0 | x 0 | x 1 | х 2 | х 3 | х 4 | х 5 | х 6 | х 7 |
| 0 | х 4 | 3.4 | 0 | 0 | 0.8 | 1 | -0.2 | -0.2 | 0 |
| 8 | х 1 | 28.9 | 1.0 | 0.0 | 0.7 | 0.0 | -0.3 | 0.1 | 0.0 |
| 15 | х 2 | 24.5 | 0.0 | 1.0 | 0.1 | 0.0 | 0.1 | -0.3 | 0.0 |
| 0 | х 7 | -6.4 | 0.0 | 0.0 | -1.8 | 0.0 | 0.2 | -0.8 | 1.0 |
| Z j - C j | 525.3 | 0.0 | 0.0 | -3.3 | 0.0 | -1.3 | -2.7 | 0.0 | |
У таблиці записані перетворені числа, отримані на 3-й ітерації. У підсумковому стовпці всі негативні числа зникли, значить отриманий план є допустимим і одночасно оптимальним. Висновок про те, що план отримано оптимальний, дозволяють зробити елементи цільової рядка. Всі вони негативні або дорівнювати нулю, що свідчить про оптимальність результату при вирішенні завдань на мінімум цільової функції.
| c j | p 0 | x 0 | x 1 | х 2 | х 3 | х 4 | х 5 | х 6 | х 7 |
| 0 | х 4 | 0.6 | 0.0 | 0.0 | 0.0 | 1.0 | -0.1 | -0.6 | 0.4 |
| 8 | х 1 | 26.3 | 1.0 | 0.0 | 0.0 | 0.0 | -0.2 | -0.3 | 0.4 |
| 15 | х 2 | 24.3 | 0.0 | 1.0 | 0.0 | 0.0 | 0.1 | -0.3 | 0.0 |
| 10 | х 3 | 3.6 | 0.0 | 0.0 | 1.0 | 0.0 | -0.1 | 0.4 | -0.6 |
| Z j - C j | 537.2 | 0.0 | 0.0 | 0.0 | 0.0 | -1.7 | -1.2 | -1.9 | |
1 * 26,3 + 1 * 24,3 + 0 * 3,6 ≥ 50
4 * 26,3 + 1 * 24,3 + 3 * 3,6 ≥ 140
1 * 26,3 + 4 * 24,3 + 1 * 3,6 ≥ 127
0 * 26,3 + 3 * 24,3 + 2 * 3,6 ≥ 80
Вартість сировини при цьому буде мінімальною і становитиме:
F = 8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2
ЗАДАЧА 3
Скласти оптимальний план перевезень харчових продуктів від 4-х постачальників до 6-ти споживачам. Постачальники (П), споживачі (М), обсяги вивезення і завезення, найкоротші відстані між пунктами вивозу і завезення наведені в таблиці.
| Постачальники | Споживачі | Обсяги вивозу, т | |||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | ||
| П 1 | 24 | 30 | 42 | 15 | 39 | 21 | 144 |
| П 2 | 9 | 24 | 30 | 33 | 27 | 29 | 148 |
| П 3 | 24 | 22 | 20 | 45 | 21 | 23 | 76 |
| П 4 | 11 | 36 | 27 | 40 | 30 | 8 | 132 |
| Обсяги завезення, т | 92 | 84 | 80 | 112 | 96 | 36 | |
Спосіб північно-західного кута полягає в тому, що розподіл обсягів вивезення проводиться, починаючи з верхнього лівого кута таблиці і закінчуючи нижнім кутом її. Результати розподілу показані в таблиці.
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 92 | 52 | |||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | -6 |
| 32 | 80 | 36 | ||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | 6 |
| 76 | 0 | |||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | 15 |
| 96 | 36 | |||||||
| Потенціали стовпців | 24 | 30 | 36 | 39 | 15 | -7 | ||
Суть методу потенціалів полягає в тому, що для кожного рядка і кожного стовпця таблиці (матриці) визначають спеціальні числа, що називаються потенціалами. За допомогою цих потенціалів можна встановити, чи потрібно заповнювати вільну клітину матриці або її потрібно залишити незаповненою.
Для вирішення задач методом потенціалів вихідний план повинен мати кількість заповнених клітин m + n - 1 (m - число рядків, n - число стовпців). Якщо план не відповідає цим вимогам, то не для всіх рядків і стовпців можна розрахувати потенціали, а без них не можна перевірити план на оптимальність.
Потенціали рядків і стовпців визначаються по заповненим клітинам, які знаходяться на їх перетині.
Елемент заповненої клітини повинен дорівнювати сумі потенціалів рядка і стовпця, на перетині яких знаходиться ця заповнена клітка.
Для початку обчислень перший потенціал для рядка або стовпця приймається умовно рівним нулю, всі інші потенціали визначаються за допомогою елементів заповнених клітин.
Позначивши потенціали рядків u i, потенціали стовпців Vj, елементи заповнення клітин
З основного вимоги
u i =
З цих виразів видно, що для розрахунку потенціалу рядка необхідно мати заповнену клітку, в стовпці якої потенціал вже визначено, а для розрахунку потенціалу стовпця потрібна заповнена клітка, що має потенціал в рядку.
Потенціали показані в таблиці.
Після того, як по рядках і стовпцях визначені потенціали, з їх допомогою з'ясовується, чи є план оптимальним, і якщо ні, то як його можна поліпшити. З цією метою для кожної вільної клітини обчислюється сума потенціалів рядків і стовпців, на перетині яких знаходиться ця клітина.
Порівняння суми потенціалів з величиною елемента у вільних клітинах дозволяє визначити, чи потрібно заповнювати цю клітину або її потрібно залишити вільною.
При вирішенні задач на мінімум функціоналу (у нашому випадку на мінімум тонно-кілометрової роботи) не заповнюються ті вільні клітини, в яких сума потенціалів менше величини елемента (у нашому випадку - відстані).
Іншими словами, якщо характеристика, значення якої дорівнює різниці
Вільні клітини, що мають нульове значення характеристики, показують на те, що їх заповнення призведе до перерозподілу поставок, але обсяг робіт (значення функціоналу) залишиться незмінним.
Суми потенціалів, значення елементів і характеристики для незаповнених клітин наведені в таблиці.
| Шифри клітин | П 1-М 3 | П 1-М 4 | П 1-М 5 | П 1-M 6 | П 2-М 1 | П 2-М 5 | П 2-М 6 | П 3-М 1 | П 3-М 2 | П 3-М 3 | П 3-М 6 | П 4-М 1 | П 4-М 2 | П 4-М 3 | П 4-М 4 |
| Суми потенціалів | 36 | 39 | 15 | -7 | 18 | 9 | -13 | 30 | 36 | 42 | -1 | 39 | 45 | 51 | 54 |
| Значення елементів | 42 | 15 | 39 | 21 | 9 | 27 | 29 | 24 | 22 | 20 | 23 | 11 | 36 | 27 | 40 |
| Характеристики | 6 | -24 | 24 | 28 | -9 | 18 | 42 | -6 | -14 | -22 | 24 | -28 | -9 | -24 | -14 |
Так як завдання вирішується на мінімум цільової функції, то саме ці негативні клітини повинні бути заповнені постачальниками. Але заповнення вільної клітини і пов'язане з ним перерозподіл поставок проводиться не ізольовано, а в зв'язку з кількома заповненими клітинами. Цей зв'язок виявляється шляхом побудови замкнутих багатокутників, вершинами яких є клітини таблиці. Одна вершина багатокутника знаходиться у вільній клітці, а всі інші - в заповнених клітках. Багатокутник, або як його називають ланцюг, має прямі кути і парне число вершин.
У результаті перерозподілу в кожній вершині (клітині) ланцюга відбувається зміна величини поставок: в одних клітинах вони збільшуються, в інших - зменшуються.
Ті клітини кайдани, у яких постачання збільшуються, називаються позитивними, а ті, у яких постачання зменшуються - негативними. Кожна ланцюг має однакове число позитивних і негативних вершин (клітин). Позитивні і негативні вершини чергуються. Якщо вільну клітину, в яку передбачається провести запис, прийняти як позитивну (оскільки зміна відбудеться у бік збільшення), то наступна клітина буде негативною, потім знову позитивною, знову негативною, і т.д.
З вільних клітин для заповнення вибирають звичайно клітки, що має найбільшу негативну характеристику. У неї записують саму найменшу величину з негативних вершин ланцюга.
+ П4М1-П1М1 + П1М2-П2М2 + П2М4-П3М4 + П3М5-П4М5
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 60 | 84 | |||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | -6 |
| 80 | 68 | |||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | 6 |
| 44 | 32 | |||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | 15 |
| 32 | 64 | 36 | ||||||
| Потенціали стовпців | 24 | 30 | 36 | 39 | 15 | -7 | ||
| Шифри клітин | П 1-М 3 | П 1-М 4 | П 1-М 5 | П 1-М 6 | П 2-М 1 | П 2-М 2 | П 2-М 5 | П 2-М 6 | П 3-М 1 | П 3-М 2 | П 3-М 3 | П 3-М 6 | П 4-М 2 | П 4-М 3 | П 4-М 4 |
| Суми потенціалів | 36 | 39 | 15 | -7 | 18 | 24 | 9 | -13 | 30 | 36 | 42 | -1 | 45 | 51 | 54 |
| Значення елементів | 42 | 15 | 39 | 21 | 9 | 24 | 27 | 29 | 24 | 22 | 20 | 23 | 36 | 27 | 40 |
| Характеристики | 6 | -24 | 24 | 28 | -9 | 0 | 18 | 42 | -6 | -14 | -22 | 24 | -9 | -24 | -14 |
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 16 | 84 | 44 | ||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | 18 |
| 80 | 68 | |||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | -22 |
| 76 | ||||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | -13 |
| 76 | 20 | 36 | ||||||
| Потенціали стовпців | 24 | 30 | 12 | 15 | 43 | 21 | ||
| Шифри клітин | П 1-М 3 | П 1-М 5 | П 1-М 6 | П 2-М 1 | П 2-М 2 | П 2-М 5 | П 2-М 6 | П 3-М 1 | П 3-М 2 | П 3-М 3 | П 3-М 4 | П 3-М 6 | П 4-М 2 | П 4-М 3 | П 4-М 4 |
| Суми потенціалів | 12 | 43 | 21 | 42 | 48 | 61 | 39 | 2 | 8 | -10 | -7 | -1 | 17 | -1 | 2 |
| Значення елементів | 42 | 39 | 21 | 9 | 24 | 27 | 29 | 24 | 22 | 20 | 45 | 23 | 36 | 27 | 40 |
| Характеристики | 30 | -4 | 0 | -33 | -24 | -34 | -10 | 22 | 14 | 30 | 52 | 24 | 19 | 28 | 38 |
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 84 | 60 | |||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | 18 |
| 80 | 52 | 16 | ||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | 12 |
| 76 | ||||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | 21 |
| 92 | 4 | 36 | ||||||
| Потенціали стовпців | -10 | 30 | 12 | 15 | 9 | -13 | ||
| Шифри клітин | П 1-М 1 | П 1-М 3 | П 1-М 5 | П 1-М 6 | П 2-М 1 | П 2-М 2 | П 2-М 6 | П 3-М 1 | П 3-М 2 | П 3-М 3 | П 3-М 4 | П 3-М 6 | П 4-М 2 | П 4-М 3 | П 4-М 4 |
| Суми потенціалів | -10 | 12 | 9 | -13 | 8 | 30 | 5 | 2 | 42 | 24 | 27 | -1 | 51 | 33 | 36 |
| Значення елементів | 24 | 42 | 39 | 21 | 9 | 24 | 29 | 24 | 22 | 20 | 45 | 23 | 36 | 27 | 40 |
| Характеристики | 34 | 30 | 30 | 34 | 1 | -6 | 24 | 22 | -20 | -4 | 18 | 24 | -15 | -6 | 4 |
+ П3М2-П1М2 + П1М4-П2М4 + П2М5-П3М5
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 32 | 112 | |||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | -2 |
| 80 | 68 | |||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | -8 |
| 52 | 24 | |||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | 1 |
| 92 | 4 | 36 | ||||||
| Потенціали стовпців | 10 | 30 | 32 | 15 | 29 | 7 | ||
| Шифри клітин | П 1-М 1 | П 1-М 3 | П 1-М 5 | П 1-М 6 | П 2-М 1 | П 2-М 2 | П 2-М 4 | П 2-М 6 | П 3-М 1 | П 3-М 3 | П 3-М 4 | П 3-М 6 | П 4-М 2 | П 4-М 3 | П 4-М 4 |
| Суми потенціалів | 10 | 32 | 29 | 7 | 8 | 28 | 13 | 5 | 2 | 24 | 7 | -1 | 31 | 33 | 16 |
| Значення елементів | 24 | 42 | 39 | 21 | 9 | 24 | 33 | 29 | 24 | 20 | 45 | 23 | 36 | 27 | 40 |
| Характеристики | 14 | 10 | 10 | 14 | 1 | -4 | 20 | 24 | 22 | -4 | 38 | 24 | 5 | -6 | 24 |
+ П4М3-П2М3 + П2М5-П4М5
+ П2М1-П2М3 + П4М3-П4М1
+ П2М2-П2М5 + П3М5-П3М2
Усі вільні клітини мають позитивні характеристики, які свідчать про те, що подальше поліпшення плану неможливо і отриманий план є оптимальним.
Обсяг робіт складе: 32 * 30 + 112 * 15 + 76 * 9 + 52 * 24 + 20 * 27 + 76 * 21 + 16 * 11 + 80 * 27 + 36 * 8 = 9332 ткм.
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 32 | 112 | |||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | -2 |
| 76 | 72 | |||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | -8 |
| 52 | 24 | |||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | -5 |
| 92 | 4 | 36 | ||||||
| Потенціали стовпців | 16 | 30 | 32 | 15 | 29 | 13 | ||
| Шифри клітин | П 1-М 1 | П 1-М 3 | П 1-М 5 | П 1-М 6 | П 2-М 1 | П 2-М 2 | П 2-М 4 | П 2-М 6 | П 3-М 1 | П 3-М 3 | П 3-М 4 | П 3-М 6 | П 4-М 2 | П 4-М 4 | П 4-М 5 |
| Суми потенціалів | 16 | 32 | 29 | 13 | 14 | 28 | 13 | 11 | 8 | 24 | 7 | 5 | 25 | 10 | 24 |
| Значення елементів | 24 | 42 | 39 | 21 | 9 | 24 | 33 | 29 | 24 | 20 | 45 | 23 | 36 | 40 | 30 |
| Характеристики | 8 | 10 | 10 | 8 | -5 | -4 | 20 | 18 | 16 | -4 | 38 | 18 | 11 | 30 | 6 |
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 32 | 112 | |||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | -2 |
| 76 | 72 | |||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | -8 |
| 52 | 24 | |||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | 0 |
| 16 | 80 | 36 | ||||||
| Потенціали стовпців | 11 | 30 | 27 | 15 | 29 | 8 | ||
| Шифри клітин | П 1-М 1 | П 1-М 3 | П 1-М 5 | П 1-М 6 | П 2-М 2 | П 2-М 3 | П 2-М 4 | П 2-М 6 | П 3-М 1 | П 3-М 3 | П 3-М 4 | П 3-М 6 | П 4-М 2 | П 4-М 4 | П 4-М 5 |
| Суми потенціалів | 11 | 27 | 29 | 8 | 28 | 25 | 13 | 6 | 3 | 19 | 7 | 0 | 30 | 15 | 29 |
| Значення елементів | 24 | 42 | 39 | 21 | 24 | 30 | 33 | 29 | 24 | 20 | 45 | 23 | 36 | 40 | 30 |
| Характеристики | 13 | 15 | 10 | 13 | -4 | 5 | 20 | 23 | 21 | 1 | 38 | 23 | 6 | 25 | 1 |
+ П2М2-П2М5 + П3М5-П3М2
| Постачальники і обсяги вивезення, т | Споживачі та обсяги завезення | Потенціали рядків | ||||||
| М 1 | М 2 | М 3 | М 4 | М 5 | М 6 | |||
| 92 | 84 | 80 | 112 | 96 | 36 | |||
| П 1 | 144 | 24 | 30 | 42 | 15 | 39 | 21 | 0 |
| 32 | 112 | |||||||
| П 2 | 148 | 9 | 24 | 30 | 33 | 27 | 29 | -6 |
| 76 | 52 | 20 | ||||||
| П 3 | 76 | 24 | 22 | 20 | 45 | 21 | 23 | -12 |
| 76 | ||||||||
| П 4 | 132 | 11 | 36 | 27 | 40 | 30 | 8 | -4 |
| 16 | 80 | 36 | ||||||
| Потенціали стовпців | 15 | 30 | 31 | 15 | 33 | 12 | ||
| Шифри клітин | П 1-М 1 | П 1-М 3 | П 1-М 5 | П 1-М 6 | П 2-М 3 | П 2-М 4 | П 2-М 6 | П 3-М 1 | П 3-М 2 | П 3-М 3 | П 3-М 4 | П 3-М 6 | П 4-М 2 | П 4-М 4 | П 4-М 5 |
| Суми потенціалів | 15 | 31 | 33 | 12 | 25 | 9 | 6 | 3 | 18 | 19 | 3 | 0 | 26 | 11 | 29 |
| Значення елементів | 24 | 42 | 39 | 21 | 30 | 33 | 29 | 24 | 22 | 20 | 45 | 23 | 36 | 40 | 30 |
| Характеристики | 9 | 11 | 6 | 9 | 5 | 24 | 23 | 21 | 4 | 1 | 42 | 23 | 10 | 29 | 1 |
Обсяг робіт складе: 32 * 30 + 112 * 15 + 76 * 9 + 52 * 24 + 20 * 27 + 76 * 21 + 16 * 11 + 80 * 27 + 36 * 8 = 9332 ткм.