- •6.030504 «Економіка підприємства», 6.030509 «Облік і аудит»
- •1.Рішення систем лінійних рівнянь методом гауса - жордана
- •1.1. Основні поняття
- •1.2. Приведення системи лінійних рівнянь до жорданової форми
- •1.3. Поняття загального, часного й базисного рішень
- •2. Загальні властивості задач лінійного програмування
- •2.І. Приклад задачі лінійного програмування - задача про використання обладнання
- •2.2. Задача про використання сировини
- •2.3. Задачі складання раціону (задача про дієту)
- •2.4. Загальна постановка задач лінійного програмування
- •2.5. Геометричний метод вирішення злп
- •Приклад 1
- •2.6. Канонічний вигляд злп
- •3. Симплексний метод вирішення злп
- •3.1. Загальна характеристика й основні етапи симплекс - методу
- •3.2. Табличний вигляд злп. Симплекс - таблиці
- •3.3. Умова оптимальності опорного плану
- •3.4. Умова нерозв'язності злп через необмеженість знизу на опр цільової функції
- •3.5. Перехід до нового опорного плану.
- •3.6. Табличний симплекс-алгоритм
- •Після вибору генерального елемента переходимо до таблиці 3.11
- •Знову вибираємо генеральний елемент і переходимо до таблиці 3.14
- •3.7. Відшукування початкового опорного плану злп методом штучного базису
- •3.8. Виродженість опорного плану. Зациклення
- •Двоїстість у лінійному програмуванні
- •5.4. Цикли перерахування
- •5.4.1. Поняття циклу перерахування
- •5.4.2. Максимально припустиме зрушення по циклу перерахування
- •5.4.3. Ціна циклу перерахування
- •5.5. Потенціали
- •5.6. Алгоритм вирішення транспортної задачі методом потенціалів
- •5.7. Відкриті транспортні задачі.
- •6. Цілочислове лінійне програмування
- •6.1. Загальна постановка задачі цілочислового лінійного програмування (зцлп)
- •6.2. Цілочислова задача про використання сировини
- •6.3. Задача про рюкзак
- •6.4. Вирішення зцлп методом округлення
- •6.5. Метод гілок і меж
- •Оптимальний план оптимальний план
- •7. Загальна постановка й різновиди задач математичного програмування
- •Література
5.4.3. Ціна циклу перерахування
Ціною циклу перерахування називається різниця між сумою вартостей, що стоять у додатних клітинках, і сумою вартостей, що стоять у від’ємних клітинках.
Наприклад, ціна циклу перерахування, зазначеного в таблиці 5.4, дорівнює (1+3)-(2+6)=4-8= - 4.
Ціна циклу перерахування - це збільшення цільової функції при зрушенні h=1 по циклу перерахування.
Якщо, наприклад, зробити одиничне зрушення по циклу перерахування таблиці 5.5, вийде план перевезень, сумарна вартість якого 430 - 4 = 426.
Має місце твердження: при зрушенні на величину h >= 0 по циклу перерахування з ціною γ , збільшення Δf цільової функції обчислюється за формулою
Δf = γ · h (5.5)
У справедливості формули (5.5) можна переконатися на прикладах таблиць 5.4, 5.5, 5.6. З формули (5.5) виходить, що при додатному зрушенні по циклу перерахування з від’ємною ціною значення цільової функції зменшується. Тому пошук оптимального плану перевезень зводиться до виявлення циклів перерахування з від’ємною ціною й здійснення максимально припустимих зрушень по них. А якщо циклів перерахування з від’ємною ціною не виявиться?
Теорема: Опорний план перевезень, при якому всі цикли перерахування мають від’ємні ціни, є оптимальний.
Виявити цикл перерахування з від’ємною ціною при наявному опорному плані (або виявити, що такого циклу немає) можна було б таким чином: для кожної вільної клітинки побудуємо цикл перерахування й обчислимо його ціну. Однак у методі потенціалів з цією метою розроблена менш трудомістка процедура.
5.5. Потенціали
Нехай у транспортній задачі з пунктами відправлення А1, А2,..., Аm і пунктами призначення В1, В2,..., Вn є деякий опорний план перевезень. Поставимо кожному пункту відправлення Ai число αi (), кожному пункту призначення Вj - число βj () так, щоб для кожної базисної клітинки (p,q) виконувалася рівність
αp + βq = cpq (5.6)
Числа αi і βj називаються потенціалами пунктів відправлення й призначення відповідно.
Для відшукування потенціалів потрібно для кожної базисної клітинки скласти рівняння вигляду (5.6) і вирішити отриману систему m + n – 1 рівнянь із m + n невідомими. Така система має нескінченно багато рішень. Щоб одержати конкретне рішення, один з потенціалів вважають рівним 0.
Знайдемо, наприклад, систему потенціалів для опорного плану, наведеного у таблиці 5.6. Складемо систему рівнянь:
Покладемо α1=0. Тоді β1=2; β3=1; α2=2; α3=1; β2=1. Доповнимо таблицю 5.6 стовпцем з потенціалами αi і рядком з потенціалами βj, одержимо таблицю 5.7.
Таблиця 5.7
Пп Пв |
В1 |
В2 |
В3 |
Запаси |
αi |
А1 |
2 2 0 |
1 3
|
1 1 40 |
40 |
0 |
А2 |
44 60 |
3 2
|
3 5
|
60 |
2 |
А3 |
3 3 10 |
2 2 40 |
2 6
|
50 |
1 |
Потреби |
70 |
40 |
40 |
150=150 |
|
βj |
2 |
1 |
1 |
|
|
Назвемо псевдовартістю перевезення одиниці вантажу з пункту Аi у пункт Вj величину
Розраховані для таблиці 5.7 псевдовартості розміщені в лівих верхніх кутах цієї таблиці.
Потенціали і псевдовартості мають цікаву економічну інтерпретацію. Припустимо, що є перевізник, що бере з пункту Аi плату αi за вивіз одиниці вантажу, а з пункту Вj - плату βj за ввезення одиниці вантажу. Тоді псевдовартість – це той виторг, що одержує перевізник за перевезення одиниці вантажу з пункту Аi у пункт Вj. Корисно застосувати цю інтерпретацію для кращого розуміння тієї умови оптимальності опорного плану, що буде наведено нижче.
А поки доведемо наступне твердження:
ціна γij циклу перерахунку, що проходить через вільну клітинку (ij), виражається формулою
Для доказу розглянемо рисунок 5.1.
Рис. 5.1.
Клітинка (ij) - єдина вільна клітка зображеного циклу перерахування. Ціна γij циклу перерахування, відповідно до визначення, дорівнює
Оскільки для базисних клітинок виконуються рівності (5.6), то можна записати:
, що й було потрібно довести.
З формули (5.7) випливає, що якщо для вільної клітинки псевдовартість більше вартості, то через цю вільну клітинку проходить цикл перерахування з від’ємною ціною. Зокрема, умову оптимальності опорного плану перевезень можна сформулювати так:
якщо опорний план перевезень такий, що для всіх вільних клітинок псевдовартість не перевершує вартості, то цей план є оптимальний.
Наприклад, опорний план перевезень таблиці 5.7 не є оптимальний, оскільки для клітинки (2.2) псевдовартість більше вартості. Ціна циклу перерахування, що проходить через цю клітинку від’ємна й дорівнює 2–3=–1 (у цьому можна зайвого разу переконатися, підрахувавши ціну, виходячи з визначення). Зробивши максимально припустиме зрушення величиною h=40, одержимо таблицю 5.8.
Таблиця 5.8
Пп Пв |
В1 |
В2 |
В3 |
Запаси |
αi |
А1 |
2 2 0 |
0 3
|
1 1 40 |
40 |
0 |
А2 |
4 4 20 |
2 2 40 |
3 5
|
60 |
2 |
А3 |
3 3 50 |
1 2
|
2 6
|
50 |
1 |
Потреби |
70 |
40 |
40 |
150=150 |
|
βj |
2 |
0 |
1 |
|
|
Побудуємо систему потенціалів для таблиці 5.8. При невеликій навичці це можна зробити, не виписуючи систему рівнянь. Розрахувавши потім псевдовартості, бачимо, що для всіх вільних клітинок псевдовартості не перевершують вартостей. Отже, опорний план таблиці 5.8 є оптимальний.
fmin=40• 1+20• 4+40• 2+50• 3=350 грошових одиниць.