 |
Спеціальні задачі лінійного програмування
|
|
|
|
ТРАНСПОРТНА ЗАДАЧА
1. Математична постановка задачі. Загальна постановка транспортної задачі полягає у визначенні оптимального плану перевезень деякого однорідного вантажу з т пунктів відправлення A1, A2,...; Aт у п пунктів призначення B1, B2,...; Bn. При цьому за критерій оптимальності звичайно береться або мінімальна вартість перевезень усього вантажу, або мінімальний час його доставки. Розглянемо транспортну задачу, за критерій оптимальності якої взята мінімальна вартість перевезень усього вантажу. Позначимо через сij тарифи перевезення одиниці вантажу з i -го пункту відправлення в j -й пункт призначення, через ai – запаси вантажу в i -му пункті відправлення, через bj – потреби у вантажі в j -му пункті призначення, а через хij – кількість одиниць вантажу, перевезеного з i -го пункту відправлення в j -й пункт призначення. Тоді математична постановка задачі полягає увизначенні мінімального значення функції
при умовах
xij ≥ 0 (i = 
; j = 
) (4)
Оскільки змінні xij (i = ; j = ) задовольняють системам лінійних рівнянь (2) і (3) і умові невід’ємності (4), забезпечуються доставка необхідної кількості вантажу в кожний з пунктів призначення, вивіз наявного вантажу із всіх пунктів відправлення, а також виключаються зворотні перевезення.
Визначення 2.1. Усяке невід’ємний розв’язок систем лінійних рівнянь (2) і (3), обумовлений матрицею Х= (xij) (i = ; j = ), називається планом транспортної задачі.
Визначення 2.2. План Х= (x*ij) (i = ; j = ),при якому функція (1) приймає своє мінімальне значення, називається оптимальним планом транспортної задачі.
Звичайно вихідні дані транспортної задачі записують у вигляді табл. 2.1.
Таблиця 2.1
| Пункти відправлення | Пункти призначення | Запаси | ||||
| В1 | … | Вj | … | Вn | ||
| А1 | c11 x11 | … | c1j x1j | … | c1n x1n | a1 |
| … | … | … | … | … | … | … |
| А2 | ci1 xi1 | … | cij xij | … | cin xin | ai |
| … | … | … | … | … | … | … |
| Am | cm1 xm1 | … | cmj xmj | … | cmn xmn | am |
| Потреби | b1 | … | bj | … | bn |
|
|
|
Очевидно, загальна наявність вантажу в постачальників дорівнює 
, загальна потреба у вантажі в пунктах призначення дорівнює 
одиниць. Якщо загальна потреба у вантажі в пунктах призначення дорівнює запасу вантажу в пунктах відправлення, тобто
то модель такої транспортної задачі називається закритою. Якщо ж зазначена умова не виконується, то модель транспортної задачі називається відкритою.
Теорема 2.1. Для можливості розв’язання транспортної задачі необхідно і достатньо, щоб запаси вантажу в пунктах відправлення дорівнювали потребі у вантажі в пунктах призначення, тобто щоб виконувалася рівність (5).
У випадку перевищення запасу над потребою, тобто 
, вводиться фіктивний (п +1)-й пункт призначення з потребою bп+1= 
івідповідні тарифи вважаються рівними нулю: сin+1= 0 (i = ). Отримана задача є транспортною задачею, для якої виконується рівність (5).
Аналогічно, при 
вводиться фіктивний (т +1)-й пункт відправлення із запасом вантажу ат+1= 
і тарифи покладаються рівними нулю: ст+1j= 0(j = ). Цим задача зводиться до звичайної транспортної задачі, з оптимального плану якої отримується оптимальний план вихідної задачі. У подальшому будемо розглядати закриту модель транспортної задачі. Якщо ж модель конкретної задачі є відкритою, то, виходячи зі сказаного вище, перепишемо таблицю умов задачі так, щоб виконувалася рівність (5).
Число змінних xij у транспортній задачі з т пунктами відправлення і п пунктами призначення дорівнює пт, а число рівнянь у системах (2) і (3) дорівнює п+т. Так як ми припускаємо, що виконується умова (5), то число лінійно незалежних рівнянь дорівнює п+т- 1. Отже, опорний план транспортної задачі може мати не більше п+т- 1 відмінних від нуля невідомих.
|
|
|
Якщо в опорному плані число відмінних від нуля компонентів дорівнює в точності п+т- 1, то план є не виродженим, а якщо менше – то виродженим.
Для визначення опорного плану існує кілька методів. Три з них – метод північно-західного кута, метод мінімального елемента і метод апроксимації Фогеля – розглядаються нижче.
Як і для всякої задачі лінійного програмування, оптимальний план транспортної задачі є і опорним планом.
Для визначення оптимального плану транспортної задачі можна використовувати викладені вище методи. Однак через виняткову практичну важливість цієї задачі і специфіку її обмежень [кожна невідома входить лише у два рівняння систем (2) і (3) і коефіцієнти при невідомих дорівнюють одиниці] для визначення оптимального плану транспортної задачі розроблені спеціальні методи. Два з них – метод потенціалів і метод диференціальних рент – розглянуті нижче.
2.1. Чотири підприємства даного економічного району для виробництва продукції використовують тривиди сировини. Потреби у сировині кожного з підприємств відповідно рівні 120, 50, 190 і 110 од. Сировина зосереджена в трьох місцях її отримання, а запаси відповідно рівні 160, 140, 170 од. На кожне з підприємств сировина може завозитися з будь-якого пункту її одержання. Тарифи перевезень є відомими величинами і задаються матрицею
Скласти c такий план перевезень, при якому загальна вартість перевезень є мінімальною.
Розв’язок. Позначимо через xij кількість одиниць сировини, перевезеної з i -го пункту її одержання на j -е підприємство. Тоді умови доставки і вивозу необхідної і наявної сировини забезпечуються за рахунок виконання наступних рівностей:
(6)
При даному плані Х= (xij) (i = 
; j = 
) перевезень загальна вартість перевезень складе
F =7 х11 +8 х12 + х13 +2 х14 +4 х21 +5 х22 +9 х23 +8 х24 +9 х31 +2 х32 +3 х33 +6 х34 (7)
Таким чином, математична постановка даної транспортної задачі полягає в знаходженні такого невід’ємного розв’язок системи лінійних рівнянь (6), при якому цільова функція (7) приймає мінімальне значення.
2. Визначення опорного плану транспортної задачі. Як і при рішенні задачі лінійного програмування симплексним методом, визначення оптимального плану транспортної задачі починають зі знаходження якого-небудь її опорного плану. Цей план, як ми вже відзначали вище, знаходять методом північно-західного кута, методом мінімального елемента або методом апроксимації Фогеля. Сутність цих методів полягає в тому, що опорний план знаходять послідовно за п+т –1 кроків, на кожному з яких у таблиці умов задачі заповнюють одну клітку, що називають зайнятою. Заповнення однієї із кліток забезпечує повністю або задоволення потреби у вантажі одного з пунктів призначення (того, у стовпці якого перебуває заповнена клітка), або вивіз вантажу з одного з пунктів відправлення (з того, у рядку якого перебуває клітка, що заповнюється).
|
|
|
У першому випадку тимчасово виключають із розгляду стовпець, що містить заповнену на даному кроці клітку, і розглядають задачу, таблиця умов якої містить на один стовпець менше, ніж було перед цим кроком, але ту ж кількість рядків і відповідно змінені запаси вантажу в одному з пунктів відправлення (у тому, за рахунок запасу якого була задоволена потреба у вантажі пункту призначення на даному кроці). У другому випадку тимчасово виключають із розгляду рядок, що містить заповнену клітку, і вважають, що таблиця умов має на один рядок менше при незмінній кількості стовпців і при відповідній зміні потреби у вантажі у пункті призначення, у стовпці якого перебуває клітка, що заповнюється.
Після того, як пророблені т+п –2 описаних вище кроків, одержують задачу з одним пунктом відправлення і одним пунктом призначення. При цьому залишиться вільною тільки одна клітка, а запаси пункту відправлення, що залишився, будуть дорівнювати потребам пункту призначення, що залишився. Заповнивши цю клітку, тим самим роблять (п + т –1)-й крок і одержують шуканий опорний план. Варто помітити, що на деякому кроці (але не на останньому) може виявитися, що потреби чергового пункту призначення дорівнюють запасам чергового пункту відправлення. У цьому випадку також тимчасово виключають із розгляду або стовпець, або рядок (що-небудь одне). Таким чином, або запаси відповідного пункту відправлення, або потреби даного пункту призначення вважають рівними нулю. Цей нуль записують у чергову заповнювану клітку. Зазначені вище умови гарантують одержання п + т –1 зайнятих кліток, у яких стоять компоненти опорного плану, що є вихідною умовою для перевірки останнього на оптимальність і знаходження оптимального плану.
|
|
|
Метод північно-західного кута. При знаходженні опорного плану транспортної задачі методом північно-західного кута на кожному кроці розглядають перший з пунктів відправлення, що залишилися, і перший з пунктів призначення, що залишилися. Заповнення кліток таблиці умов починається з лівої верхньої клітки для невідомого х11 («північно-західний кут») і закінчується кліткою для невідомого хтn,тобто іде як би по діагоналі таблиці.
2.8. На три бази А1, А2, А3 надійшов однорідний вантаж у кількостях, відповідно рівних 140, 180 і 160 од. Цей вантаж потрібно перевезти в п’ять пунктів призначення В1, В2, В3, В4, В5 відповідно в кількостях 60, 70, 120, 130 і 100 од. Тарифи перевезень одиниці вантажу з кожного з пунктів відправлення у відповідні пункти призначення зазначені в наступній таблиці:
Таблиця 2.2
| Пункти відправлення | Пункти призначення | Запаси | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 А2 А3 | ||||||
| Потреби |
Знайти план перевезень даної транспортної задачі методом північно-західного кута.
Рішення. Тут число пунктів відправлення т =3, а число пунктів призначення п=5. Отже, опорний план задачі визначається числами, що стоять в 5+3–1=7 заповнених клітках.
Заповнення таблиці почнемо із клітки для невідомого x11,тобто спробуємо задовольнити потреби першого пункту призначення за рахунок запасів першого пункту відправлення. Так як запаси пункту А1 більше, ніж потреби пункту В1,то покладемо x11 =60, записуємо це значення у відповідній клітці табл. 2.3 і тимчасово виключаємо з розгляду стовпець В1,вважаючи при цьому запаси пункту А1 рівними 80.
Таблиця 2.3
| Пункти відправлення | Пункти призначення | Запаси | ||||
| B1 | В2 | В3 | В4 | В5 | ||
| А1 | ||||||
| А2 | ||||||
| А3 | ||||||
| Потреби |
Розглянемо перші з пунктів відправлення і призначення, що залишилися, відповідно А1 і В2. Запаси пункту А1 більше потреб пункту В2. Покладемо x12 =70, запишемо це значення у відповідній клітці табл. 2.3 і тимчасово виключимо з розгляду стовпець В2. У пункті А1 запаси вважаємо рівними 10 од. Знову розглянемо перші з пунктів відправлення і призначення, що залишилися, відповідно А1 і В3. Потреби пункту В3 більше запасів, пункту А1, що залишилися. Покладемо х13= 10і виключимо з розгляду рядок А1. Значення х13= 10запишемо у відповідну клітку табл. 2.3 і вважаємо потреби пункту В3 рівними 110 од.
|
|
|
Тепер перейдемо до заповнення клітки для невідомого х23 і т. д. Через шість кроків залишається один пункт відправлення А3 із запасом вантажу 100 од. і один пункт призначення В5 з потребою 100 од. Відповідно є одна вільна клітка, яку і заповнюємо, покладаючи х35 =100 (табл. 2.3). У результаті одержуємо опорний план
Відповідно до даного плану перевезень, загальна вартість перевезень усього вантажу становить
S =2·60+3·70+4·10+1·110+4·70+7·60+2·100=1380
Метод мінімального елемента. У методі північно-західного кута на кожному кроці потреби першого з пунктів призначення, що залишилися, задовольнялися за-рахунок запасів першого з пунктів відправлення, що залишилися,. Очевидно, вибір пунктів призначення і відправлення доцільно робити, орієнтуючись на тарифи перевезень, а саме: на кожному кроці варто вибирати яку-небудь клітку, що відповідає мінімальному тарифу (якщо таких кліток декілька, то варто вибрати кожну з них), і розглянути пункти призначення і відправлення, що відповідають обраній клітці. Сутність методу мінімального елемента і полягає у виборі клітки з мінімальним тарифом. Слід зазначити, що цей метод, як правило, дозволяє знайти опорний план транспортної задачі, при якому загальна вартість перевезень вантажу менше, ніж загальна вартість перевезень при плані, знайденому для даної задачі за допомогою методу північно-західного кута. Тому найбільш доцільно опорний план транспортної задачі знаходити методом мінімального елемента.
2.9. Знайти опорний план транспортної задачі 2.1 методом мінімального елемента.
Рішення. Вихідні дані задачі запишемо у вигляді табл. 2.4. Мінімальний тариф, рівний 1, перебуває в клітці для змінної х13. Покладемо х13= 160, запишемо це значення у відповідну клітку табл. 2.4 і виключимо тимчасово з розгляду рядок А1. Потреби пункту призначення В3 вважаємо рівними 30 од.
У частині таблиці, що залишилася, із двома рядками А2 і А3 і чотирма стовпцями В1, В2, В3 і В4 клітка з найменшим значенням тарифу сij перебуває на перетині рядка А3 і стовпця В2, де с32 =2. Покладемо x32 =50 і внесемо це значення у відповідну клітку табл. 2.4.
Тимчасово виключимо з розгляду стовпець В2 і будемо вважати запаси пункту А3 рівними 120 од. Після цього розглянемо частину таблиці, що залишилася, із двома рядками А2 і А3 і трьома стовпцями В1, В3 і В4. У ній мінімальний тариф сij перебуває в клітці на перетині рядка А3 і стовпці В3 і дорівнює 3. Заповнимо описаним вище способом цю клітку і аналогічно заповнимо (у певній послідовності) клітки, що перебувають на перетині рядка А2 і стовпця В1,рядка А3 і стовпця В4, рядка А2 і стовпця В4.
Таблиця 2.4
| Пункти відправлення | Пункти призначення | Запаси | |||
| B1 | В2 | В3 | В4 | ||
| А1 | |||||
| А2 | |||||
| А3 | |||||
| Потреби |
У результаті одержимо опорний план
При даному плані перевезень загальна вартість перевезень, становить
S =1·160+4·120+8·20+2·50+3·30+6·90=1530.
Метод апроксимації Фогеля. При визначенні оптимального плану транспортної задачі методом апроксимації Фогеля на кожній ітерації по всіх стовпцях і по всіх рядках знаходять різницю між двома записаними в них мінімальними тарифами. Ці різниці записують у спеціально відведені для цього рядки і стовпці в таблиці умов задачі. Серед зазначених різниць вибирають мінімальну. У рядку (або в стовпці), якому відповідає дана різниця, визначають мінімальний тариф. Клітку, у якій він записаний, заповнюють на даній ітерації.
Якщо мінімальний тариф однаковий для декількох кліток даного рядка (стовпця), то для заповнення вибирають ту клітку, що розташована в стовпці (рядку), що відповідає найбільшій різниці між двома мінімальними тарифами, що перебувають у даному стовпці (рядку).
2.10. Використовуючи метод апроксимації Фогеля, найти опорний план транспортної задачі 2.1, вихідні дані якої наведені в табл. 2.5 (опорний план цієї задачі раніше був знайдений методом мінімального елемента).
Таблиця 2.5
| Пункти відправлення | Пункт призначення | Запаси | |||
| В1 | В2 | В3 | В4 | ||
| А1 А2 А3 | |||||
| Потреби |
Розв’язок. Для кожного рядка і стовпця таблиці умов знайдемо різниці між двома мінімальними тарифами, записаними в даному рядку або стовпці, і помістимо їх у відповідному додатковому стовпці або додатковому рядку табл. 2.6. Так, у рядку А2 мінімальний тариф дорівнює 4, а наступний за ним дорівнює 5, різниця між ними 5–4=1. Точно так само різниця між мінімальними елементами в стовпці В4 дорівнює 6–2=4. Обчисливши всі ці різниці, бачимо, що найбільша з них відповідає стовпцю В4. У цьому стовпці мінімальний тариф записаний у клітці, що перебуває на перетині рядка А1 і стовпця В4. Таким чином, цю клітку варто заповнити. Заповнивши її, тим самим ми задовольнимо потреби пункту В4. Тому виключимо з розгляду стовпець В4 і будемо вважати запаси пункту А1 рівними 160–110=50 од. Після цього визначимо наступну клітку для заповнення. Знову знайдемо різниці між двома мінімальними тарифами, що залишилися, у кожному з рядків і стовпців і запишемо їх у другому додатковому стовпці і у другому додатковому рядку табл. 2.6.
Таблиця 2.6
| Пункти відправлення | Пункти призначення | Запаси | Різниці по рядках | ||||||||
| В1 | В2 | В3 | B4 | ||||||||
| А1 | - | - | - | - | |||||||
| А2 | |||||||||||
| А3 | - | - | |||||||||
| Потреби | |||||||||||
| Різниці по стовпцях | |||||||||||
| - | |||||||||||
| - | |||||||||||
| - | - | ||||||||||
| - | - | - | |||||||||
| - | - | - |
Як видно із цієї таблиці, найбільша зазначена різниця відповідає рядку А1. Мінімальний тариф у цьому рядку записаний у клітці, що перебуває на перетині її зі стовпцем В3. Отже, заповнюємо цю клітку. Помістивши в неї число 50, тим самим припускаємо, що запаси в пункті А1 повністю вичерпані, а потреби в пункті В3 стали рівними 190–50=140 од. Виключимо з розгляду рядок А1 і визначимо нову клітку для заповнення. Продовжуючи ітераційний процес, послідовно заповнюємо клітки, що перебувають на перетині рядки А3 і стовпця В3, рядка А3 і стовпця В2, рядка А2 і стовпця В1, рядка А2 і стовпця В2. У результаті одержимо опорний план
При цьому плані загальна вартість перевезень така:
S =1·50+2·110+4·120+5·20+2·30+3·140=1330.
Як правило, застосування методу апроксимації Фогеля дозволяє одержати або опорний план, близький до оптимального, або сам оптимальний план. До речі, знайдений вище опорний план транспортної задачі є оптимальним.
3. Визначення оптимального плану транспортної задачі.
Для визначення оптимального плану транспортної задачі розроблено декілька методів. Однак найчастіше використовуються метод потенціалів і метод диференційних рент.
Метод потенціалів. Загальний принцип визначення оптимального плану транспортної задачі методом потенціалів аналогічний принципу Розв’язок задачі лінійного програмування симплексним методом, а саме: спочатку знаходять опорний план транспортної задачі, а потім його послідовно поліпшують до одержання оптимального плану.
Для визначення опорного плану транспортної задачі будемо користуватися одним з методів, розглянутих у попередньому параграфі. Ці методи гарантують одержання зайнятих у вихідному плані п + т -1 кліток, причому в деяких з них можуть стояти нулі. Отриманий план варто перевірити на оптимальність.
Тоорема 2.2. Якщо для деякого опорного плану Х*= (xij*) (i = ; j = ) транспортної задачі існують такі числа α1, α2,..., α т, β1, β 2,...; βт що
βj –αi=cij при хij> 0 (8)
і
βj –αi ≤ cij при хij= 0 (9)
для всіх i = і j = , то Х*= (xij*) – оптимальний план транспортної задачі.
Визначення 2.3. Числа αi і βj (i = ; j = )називаються потенціалами відповідно пунктів призначення і пунктів споживання.
Сформульована теорема дозволяє побудувати алгоритм знаходження Розв’язок транспортної задачі. Він полягає в наступному. Нехай одним з розглянутих вище методів знайдений опорний план транспортної задачі. Для кожного з пунктів відправлення і призначення визначають потенціали αi і βj (i = ; j = ). Ці числа знаходять із системи рівнянь
βj –αi ≤ cij (10)
де cij – тарифи, що стоять у заповнених клітках таблиці умов транспортної задачі.
Так як число заповнених кліток дорівнює п + т -1, то система (10) з п + т невідомими містить п + т -1 рівнянь. Оскільки число невідомих перевищує на одиницю число рівнянь, одне з невідомих можна покласти рівним довільному числу, наприклад αi =0, і знайти послідовно з рівнянь (10) значення інших невідомих. Після того як всі потенціали знайдені, для кожної з вільних кліток визначають числа αij = βj –αi–cij
Рис. 2.1
Якщо серед чисел αij немає додатних, то знайдений опорний план є оптимальним. Якщо ж для деякої вільної клітки αij > 0, то вихідний опорний план не є оптимальним і необхідно перейти до нового опорного плану. Для цього розглядають всі вільні клітки, для яких αij > 0, і серед даних чисел вибирають максимальне. Клітку, який це число відповідає, варто заповнити.
Заповнюючи обрану клітку, необхідно змінити об’єми поставок, записаних у ряді інших зайнятих кліток і пов’язаних із заповненою так званим циклом.
Визначення 2.4. Циклом у таблиці умов транспортної задачі називається ламана лінія, вершини якої розташовані в зайнятих клітках таблиці, а ланки-уздовж рядків і стовпців, причому в кожній вершині циклу зустрічається рівно дві ланки, одна з яких перебуває в рядку, а інша - у стовпці.
Якщо ламана лінія, що утворить цикл, перетинається, то точки самоперетину не є вершинами. Приклади деяких циклів показані на рис. 2.1.
При правильній побудові опорного плану для будь-якої вільної клітки можна побудувати лише один цикл. Після того як для обраної вільної клітки він побудований, варто перейти до нового опорного плану. Для цього необхідно перемістити вантажі в межах кліток, пов’язаних з даною вільною кліткою. Це переміщення роблять за наступними правилами:
1) кожної із кліток, зв’язаних циклом з даною вільною кліткою, приписують певний знак, причому вільній клітці – знак плюс, а всім іншим кліткам – по черзі знаки мінус і плюс (будемо називати ці клітки мінусовими і плюсовими);
2) у дану вільну клітку переносять менше із чисел xij, що стоять у мінусових клітках. Одночасно це число додають до відповідних чисел, що стоять у плюсових клітках, і віднімають від чисел, що стоять у мінусових клітках. Клітка, що раніше була вільною, стає зайнятою, а мінусова клітка, у якій стояло мінімальне із чисел xij вважається вільною.
У результаті зазначених вище переміщень вантажів у межах кліток, зв’язаних циклом з даною вільною кліткою, визначають новий опорний план транспортної задачі.
Описаний вище перехід від одного опорного плану транспортної задачі до іншого її опорного плану називається зрушенням по циклу перерахунку.
Слід зазначити, що при зрушенні по циклі перерахунку число зайнятих кліток залишається незмінним, а саме залишається рівним п + т -1. При цьому якщо в мінусових клітках є два (або більше) однакових числа xij то звільняють лише одну з таких кліток, а інші залишають зайнятими (з нульовими поставками).
Отриманий новий опорний план транспортної задачі перевіряють на оптимальність. Для цього визначають потенціали пунктів відправлення і призначення і знаходять числа αij = βj –αi–cij для всіх вільних кліток. Якщо серед цих чисел не виявиться додатних, то це свідчить про одержання оптимального плану. Якщо ж додатні числа є, то варто перейти до нового опорного плану. У результаті ітераційного процесу після кінцевого числа кроків одержують оптимальний план задачі.
З викладеного вище випливає, що процес знаходження Розв’язок транспортної задачі методом потенціалів включає наступні етапи:
1. Знаходять опорний план. При цьому число заповнених кліток повинне бути рівним п + т -1.
2. Знаходять потенціали βj і αi відповідно пунктів призначення і відправлення.
3. Для кожної вільної клітки визначають число αij. Якщо серед чисел αij немає додатних, то отримано оптимальний план транспортної задачі; якщо ж вони є, то переходять до нового опорного плану.
4. Серед додатних чисел αij вибирають максимальне, будують для вільної клітки, якій воно відповідає, цикл перерахунку і роблять зрушення по циклу перерахунку.
5. Отриманий опорний план перевіряють на оптимальність, тобто знову повторять всі дії починаючи з етапу 2.
На закінчення відзначимо, що при визначенні опорного плану чи в процесі Розв’язок задачі може бути отриманий вироджений опорний план. Щоб уникнути в цьому випадку зациклення, треба відповідні нульові елементи опорного плану замінити як завгодно малим позитивним числом ε і вирішувати задачу як не вироджену. В оптимальному плані такої задачі необхідно вважати ε рівним нулю.
2.17. Для транспортної задачі, вихідні дані якої наведені в табл. 2.7, знайти оптимальний план.
Таблиця 2.7
| Пункти відправлення | Пункти призначення | Запаси | |||
| B1 | В2 | В3 | В4 | ||
| А1 | |||||
| А2 | |||||
| А3 | |||||
| Потреби |
Розв’язок. Спочатку, використовуючи метод північно-західного кута, знаходимо опорний план задачі. Цей план записаний у табл. 2.7.
Знайдений опорний план перевіряємо на оптимальність. У зв’язку з цим знаходимо потенціали пунктів відправлення і призначення. Для визначення потенціалів одержуємо систему
β1–α1= 1, β2–α1= 2, β2–α2= 3,
β3–α2= 1, β4–α2= 5, β4–α3= 4,
що містить шість рівнянь із сьома невідомими. Покладаючи α1 =0, знаходимо
β1 =1, β2 =2, α2 =–1, β3 =0, β4 =4, α3 =0. Для кожної вільної клітки обчислюємо число αij=βj –αi –cij
α13 = – 4, α14 =3, α21 = α32 =0, α31 = – 2, α33 = – 4.
Поміщаємо знайдені числа в рамки і записуємо їх у кожну з вільних кліток табл. 2.8.
Таблиця 2.8
| Пункти відправлення | Пункти призначення | Запаси | |||
| B1 | В2 | В3 | В4 | ||
| А1 | 2 –4 | 1 + | |||
| А2 | 3 + | 5 – | |||
| А3 | -2 | – 4 | |||
| Потреби |
Так як серед чисел αij є додатні, то побудований план перевезень не є оптимальним і треба перейти до нового опорного плану. Найбільшим серед додатних чисел αij є α14 =3, тому для даної вільної клітки будуємо цикл перерахунку (табл. 2.8) і робимо зсув по цьому циклу. Найменше із чисел у мінусових клітках дорівнює 10. Клітка, у якій перебуває це число, стає вільною в новій табл. 2.9. Інші числа в табл. 2.9 отримуються так: до числа 10, що стоїть в плюсовій клітці табл. 2.8, додамо 10 і віднімемо 10 із числа 20, що перебуває в мінусовій клітці табл. 2.8. Клітка на перетині рядка А2 і стовпця В4 стає вільною.
Після цих перетворень одержуємо новий опорний план (табл. 2.9).
Таблиця 2.9
| Пункти відправлення | Пункти призначення | Запаси | |||
| B1 | В2 | В3 | В4 | ||
| А1 | 2 – | –2 | 1 + | ||
| А2 | – 3 | ||||
| А3 | +1 | 2 + +3 | – 1 | 4 – | |
| Потреби |
Цей план перевіряємо на оптимальність. Знову знаходимо потенціали пунктів відправлення і призначення. Для цього складемо наступну систему рівнянь:
β1–α1= 1, β2–α1= 2, β4–α1= 1,
β2–α2= 3, β3–α2= 1, β4–α3= 4,
Покладаємо α1 =0, одержуємо β1 = β4 =1, β2 =2, β3 =0, α3 = – 3, α2 = – 1. Для кожної вільної клітки обчислюємо число αij маємо, α13 = – 2, α21 =0, α24 = – 3, α31 =1, α32 =3, α33 = – 1.
Таким чином, бачимо, що даний план перевезень не є оптимальним. Тому переходимо до нового опорного плану (табл. 2.10).
Таблиця 2.10
| Пункти відправлення | Пункти призначення | Запаси | |||
| B1 | В2 | В3 | В4 | ||
| А1 | –4 | ||||
| А2 | – 3 | ||||
| А3 | –2 | – 4 | – 3 | ||
| Потреби |
Порівнюючи різниці βj –αi нових потенціалів, що відповідають вільним кліткам табл. 2.10, з відповідними числами cij бачимо, що зазначені різниці потенціалів для всіх вільних кліток не перевершують відповідних чисел Сц. Отже, отриманий план
є оптимальним. При даному плані вартість перевезень
S =1·30+2·0+1·20+3·20+1·10+2·10=140.
4. Визначення оптимального плану транспортних задач, що мають деякі ускладнення в їх постановці. При знаходженні Розв’язок ряду конкретних транспортних задач часто буває необхідно враховувати додаткові обмеження, які не зустрічалися вище при розгляді простих варіантів даних задач. Зупинимося докладніше на деяких можливих ускладненнях у постановках транспортних задач.
1. При деяких реальних умовах перевезення вантажу з певного пункту відправлення Ai у пункт призначення Вj не можуть бути здійснені. Для визначення оптимальних планів таких задач припускають, що тариф перевезення одиниці вантажу з пункту Ai у пункт Вj є як завгодно великою величиною М, і при цій умові відомими методами знаходять Розв’язок нової транспортної задачі. При такому припущенні виключається можливість при оптимальному плані транспортної задачі перевозити вантаж з пункту Ai у пункт Вj. Такий підхід до знаходження Розв’язок транспортної задачі називають забороною перевезень або блокуванням відповідної клітки таблиці даних задачі.
2. В окремих транспортних задачах додатковою умовою є забезпечення перевезення по відповідних маршрутах певної кількості вантажу. Нехай, наприклад, із пункту відправлення Ai у пункт призначення Вj потрібно обов’язково перевести dij одиниць вантажу. Тоді в клітку таблиці даних транспортної задачі, що перебуває на перетині рядка Ai і стовпця Вj записують зазначене число αij і надалі цю клітку вважають вільною з як завгодно великим тарифом перевезень М. Для отриманої в такий спосіб нової транспортної задачі знаходять оптимальний план, що визначає оптимальний план вихідної задачі.
3. Іноді потрібно найти Розв’язок транспортної задачі, при якому з пункту відправлення Ai у пункт призначення Вj повинне бути завезене не менше заданої кількості вантажу αij. Для визначення оптимального плану такої задачі вважають, що запаси пункту Ai і потреби пункту Вj менше фактичних на αij одиниць. Після цього знаходять оптимальний план нової транспортної задачі, на підставі якого і визначають Розв’язок вихідної задачі.
4. У деяких транспортних задачах потрібно знайти оптимальний план перевезень за умови, що з пункту відправлення Ai у пункт призначення Вj перевозиться не більш ніж αij одиниць вантажу, тобто
xij ≤ αij (11)
Сформульовану задачу можна вирішити так. У таблиці вихідних даних задачі для кожного j -го обмеження (11) передбачають додатковий стовпець, тобто вводять додатковий пункт призначення. У даному стовпці записують ті ж тарифи, що і у стовпці Вj, за винятком тарифу, що перебуває в i -му рядку. У додатковому стовпці в цьому рядку тариф вважають рівним деякому як завгодно великому числу М. При цьому потреби пункту Вj вважають рівними αij, а потреби знову введеного пункту призначення вважають рівними bj – αij. Розв’язок отриманої транспортної задачі може бути знайдено методом потенціалів, і тим самим буде визначений оптимальний план або встановлена нерозв’язність вихідної задачі. Помітимо, що вихідна транспортна задача має розв’язок лише в тому випадку, коли для неї існує хоча б один опорний план.
Наведену вище задачу можна вирішити і таким способом. З урахуванням обмеження (11) за правилом мінімального елемента будують опорний план. При цьому якщо величина записуваного на даному кроці у відповідну клітку числа визначається тільки обмеженням (11), то надалі з розгляду виключають тільки заповнену клітку. В інших випадках з розгляду виключають або рядок, або стовпець (що-небудь одне).
Якщо в результаті складання плану поставок всі наявні запаси пунктів відправлення розподілені і потреби в пунктах призначення задоволені, то отримано опорний план транспортної задачі.
Якщо в якомусь рядку (а отже, і в стовпці) залишилася нерозподілена остача, рівна d,то вводять додатковий пункт призначення і додатковий пункт відправлення з потребами і запасами, рівними d. У клітці, що перебуває на перетині стовпця додаткового пункту призначення і рядку додаткового пункту відправлення, тариф уважають рівним нулю. У всіх інших клітках даного рядка і стовпця тарифи вважають рівними деякому як завгодно великому числу М. Отриману в результаті цього транспортну задачу вирішують методом потенціалів. Після кінцевого числа кроків або встановлюють, що вихідна задача не має опорного плану, або знаходять її оптимальний план. При цьому (хij*) – оптимальний план вихідної задачі, якщо
(12)
2.29. Знайти Розв’язок транспортної задачі, вихідні дані якої наведені в табл. 2.18, при додаткових умовах: з А1 у В2 і з А2 у В5 перевезення не можуть бути здійснені, а з А2 у В1 буде завезено 60 од. вантажу.
Таблиця 2.18
| Пункти відправлення | Пункти призначення | Запаси | ||||
| В1 | В2 | В3 | В4 | В5 | ||
| А1 А2 А3 | ||||||
| Потреби |
Розв’язок. Так як з А1 у В2 і з А2 у В5 перевезення не можуть бути здійснені, то в клітках А1 В2 і А2 В5 табл. 2.19 тарифи вважаємо рівними деякому як завгодно великому числу М. Вважаємо рівним цьому ж числу і тариф для клітки А2В1. Одночасно в цю клітку поміщаємо число 60, оскільки, за умовою, з А2 в В1 потрібно завести 60 од. вантажу. Надалі клітку А2В1 вважаємо вільною з як завгодно великим тарифом М.
Таблиця 2.19
| Пункти відправлення | Пункти призначення | Запаси | ||||
| B1 | В2 | В3 | В4 | В5 | ||
| А1 | М 2– М | М –5 | ||||
| А2 | М 602– М | –3 | М | |||
| А3 | –9 | –2 | –10 | М –6 | ||
| Потреби |
Для транспортної задачі, вихідні дані якої записані в табл. 2.19, методом мінімального елемента знаходимо опорний план. Цей план перевіряємо на оптимальність. Для кожного з пунктів відправлення і призначення знаходимо потенціали, а для кожної з вільних кліток – числа αij = βj – αi – cij. Ці числа записуємо у квадратах у відповідних клітках табл. 2.19. Якщо серед даних чисел немає додатних, то знайдений опорний план є оптимальним. У цьому випадку є два додатних числа, розташованих у клітках А1В5 і А3В5. Тому переходимо до нового опорного плану. Будуємо для клітки А1B5 цикл перерахунку і робимо зсув по циклу перерахунку (табл. 2.20).
Таблиця 2.20
| Пункти відправлення | Пункти призначення | Запаси | ||||
| B1 | В2 | В3 | В4 | В5 | ||
| А1 | М –2 М+ 7 | – М+ 5 | ||||
| А2 | М 60 М –3 | M –8 | М | |||
| А3 | M –8 | –2 | M –15 | М –6 | ||
| Потреби |
Отриманий опорний план перевіряємо на оптимальність; так як він не оптимальний, то переходимо до нового опорного плану (табл. 2.21).
Таблиця 2.20
| Пункти відправлення | Пункти призначення | Запаси | ||||
| B1 | В2 | В3 | В4 | В5 | ||
| А1 | М 1– М | –1 | ||||
| А2 | М 603– М | –2 | М 6– М | |||
| А3 | –8 | –2 | –9 | |||
| Потреби |
Як видно з табл. 2.21, вихідна транспортна задача має оптимальний план
При цьому загальна вартість перевезень
S =1·60+1·90+4·30+6·60+3·80+4·80+1·80+3·20=1330
є мінімальною.
5. Знаходження Розв’язок деяких економічних задач, що зводяться до транспортної. Вище були докладно розглянуті методи знаходження Розв’язок транспортної задачі. Цими ж методами може бути також знайдене Розв’язок багатьох інших задач, які по своїй економічній сутності не пов’язані із транспортними перевезеннями. Розглянемо деякі з них.
2.35. На текстильному підприємстві є три типи ткацьких верстатів. На верстатах кожного з типів можуть вироблятися чотири види тканин: міткаль, бязь, ситець і сатин. Продуктивність кожного верстата і собівартість тканин наведені в табл. 2.25. З огляду на те, що фонд робочого часу кожної із груп ткацьких верстатів відповідно дорівнює 90, 220 і 180 станко-год, скласти такий план їхнього завантаження, при якому загальна собівартість тканин, що випускаються, у кількості 1200 м міткалю, 900 м бязі, 1800 м ситцю і 840 м сатину є мінімальною.
Таблиця 2.25
| Тип верстата | Продуктивність верстата (м/год) при виготовленні | Собівартість (грн.) тканини при виготовленні 1 м/год | ||||||
| міткалю | бязі | ситцю | сатину | міткалю | бязі | ситцю | сатину | |
| I | ||||||||
| II | ||||||||
| III |
Розв’язок. Складемо математичну модель задачі. Будемо вважати, що і -йтип верстатів зайнятий виготовленням j -го виду тканин хij станко-годин. Тоді змінні хij повинні задовольняти наступним рівнянням:
(13)
(14)
Змінні xij повинні задовольняти також умові невід’ємності:
xij ≥ 0 (i = ; j = ) (15)
Серед всіх можливих значень невідомих xij,щозадовольняють рівнянням (13) і (14) і умові невід’ємності змінних (15), потрібно знайти таке, при якому лінійна функція
F= 2 x11 + x12 +3 x13 + x14 +3 x21 +2 x22 +4 x23 + x24 +6 x31 +3 x32 +5 x33 +2 x34 (16)
приймає найменше значення.
Перетворимо математичну модель задачі таким чином, щоб звести її до моделі транспортної задачі. Для цього приведемо вихідні дані і невідомі величини вихідної задачі до однієї одиниці, у якості якої візьмемо 1 станко-год роботи верстатів I типу. Тоді, оскільки продуктивність верстатів II і III типів відповідно складають 1/2 і 1/3 продуктивності верстатів I типу (табл. 2.25), фактичний фонд робочого часу в наведених станко-годинах для II типу верстатів дорівнює 105, а для III типу – 60. Загальний фонд робочого часу в наведених станко-годинах становить 90+105+60=255.
Визначимо тепер, який час потрібний для вироблення потрібної кількості кожного з видів тканин. Так як необхідно виготовити 1200 м міткалю і за одну зведену станко-годину можна виробити 24 м, то для випуску необхідної кількості міткалю буде потрібно 1200/24=50 станко-год. Аналогічно визначаємо потреби для вироблення бязі, ситцю і сатину. Ці потреби відповідно складають 30, 100 і 20 станко-год. Позначимо тепер через х′ij,кількість зведених станко-годин і -го типу верстатів, що використовуються при виробленні j -го виду тканини. Тоді системи рівнянь (13) і (14) вихідної задачі можна переписати так:
(17)
(18)
де
х′11 = х11; х′12 = х12; х′13 = х13; х′14 = х14;
х′21 =1/2 х21; х′22 =1/2 х22; х′23 =1/2 х23; х′24 =1/2 х24; (19)
х′31 =1/3 х31; х′32 =1/3 х32; х′33 =1/3 х33; х′34 =1/3 х34;
Цільова функція (16) вихідної задачі записується у вигляді
F =2 х′11 + х′12 +3 х′13 + х′14 +6 х′21 +4 х′22 +8 х′23 +2 х′24 +18 х′31 +9 х32 +15 х′32 +6 х′34 (20)
В результаті приходимо до наступної математичної задачі: потрібно серед всіх невід’ємних рішень систем лінійних рівнянь (17) і (18) знайти таке, при якому функція (20) приймає мінімальне значення.
Таким чином, вихідна задача звелася до задачі, математична модель якої нічим не відрізняється від математичної моделі транспортної задачі. Оскільки 90+105+60=225>50+30+100+20=200, отримана задача має відкриту модель. Тому, щоб найти її Розв’язок, вважаємо, що є фіктивна потреба в тканинах, на вироблення яких необхідно затратити 255-200=55 станко-год. Отриману в результаті останнього припущення задачу вирішуємо методом потенціалів (табл. 2.26).
Таблиця 2.26
| Тип верстатів | Тканина | Виробнича потужність | ||||
| міткаль | бязь | ситець | сатин | деяка тканина | ||
| І | ||||||
| ІІ | ||||||
| ІІІ | ||||||
| Потреба у тканині |
Як видно з табл. 2.26, оптимальний план задачі (17) - (20) визначається матрицею
Використовуючи співвідношення (19), для визначення оптимального плану вихідної задачі (13)-(16) одержимо матрицю
Таким чином, відповідно до плану вироблення тканин, передбачається використовувати 90 станко-год верстатів I типу для виробництва ситцю, відповідно 100,60, 20 і 30 станко-год верстатів II типу для вироблення міткалю, бязі, ситцю і сатину, 15 станко-год верстатів III типу для виготовлення сатину. При цьому 155 станко-год верстати III типу залишаються вільними.
Відповідно до даного плану на верстатах І типу виробляється 1620 м ситцю, на верстатах II типу – 1200 м міткалю, 900 м бязі, 180 м ситцю і 630 м сатину, на верстатах III типу – 210 м сатину. При цьому 165 станко-год станки IIIтипу можуть бути використані для вироблення понадпланової продукції. При даному плані вироблення тканин їхня собівартість є мінімальною і становить
S =3·1620+3·1200+2·900+4·180+1·630+2·210=12030.
2.36. На п’яти токарських верстатах різних типів можна виконувати п’ять операцій по обробці деталі. При цьому за кожним з верстатів може бути закріплені лише одна операція і одна і та сама операція може виконуватися тільки одним верстатом. Знаючи час виконання кожної з операцій на кожному з верстатів, що задається матрицею
скласти такий розподіл виконуваних операцій між верстатами, при якому сумарні витрати часу на обробку деталі є мінімальними.
Розв’язок. Складемо математичну модель задачі. Позначимо через xij (i = 
; j = ) змінну, значення якої дорівнює 1, якщо на i -му верстаті j -а операція виконується, і дорівнює 0 у противному випадку. Тоді закріплення за кожним верстатом тільки однієї операції виражається рівностями
(21)
а закріплення кожної з операцій тільки на одному верстаті – рівностями
(22)
Потрібно знайти такі значення невідомих xij (i = ; j = ), що задовольняють системам лінійних рівнянь (21) і (22) і рівні 0 або 1, при яких функція
F= 2 x11 +4 x12 +6 x13 +8 x14 +3 x15 + x21 +3
I. ОСНОВНІ ЗАДАЧІ І НАПРЯМКИ САМОСТІЙНОЇ НДР СТУДЕНТІВ
V. Спрямованість особистості учня та спеціальні здібності
Аудиторська палата України: функції, задачі.
Взаємно двоїсті задачі
Визначте предмет і задачі психології юридичної праці.
ВИРОБНИЧІ ФУНКЦІЇ, ТИПОВІ ЗАДАЧІ ДІЯЛЬНОСТІ ТА УМІННЯ ЩОДО ВИРІШЕННЯ ТИПОВИХ ЗАДАЧ ДІЯЛЬНОСТІ
Військовий тил, його роль, задачі і призначення в сучасному бою.
ВЛАСТИВОСТІ ОСНОВНОЇ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ГЕОМЕТРИЧНЕ ТЛУМАЧЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині
ДВОЇСТІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
