• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Транспортна задача. Математичне формулювання і алгоритм вирішення

В аспекті вирішення задач лінійного програмування розглянемо математичне формулювання і алгоритм розв’язання транспортної задачі.

Змістовна постановка задачі: Однорідний продукт, зосереджений у m пунктах відправлення в кількостях а₁, а₂, ... а_m одиниць відповідно, необхідно доставити в кожний із n пунктів призначення в кількості b₁, b₂, ... b_n одиниць відповідно. Вартість (відстань) перевезення одиниці продукту з i-го пункту відправлення j-й пункт призначення дорівнює с_ij і відома для кожного маршруту. Нехай x_ij - кількість продукту, перевезеного з і-ro пункту відправлення в j-й пункт призначення. Задача полягає у визначенні таких розмірів x_ij для всіх маршрутів, при яких сумарна вартість (відстань) перевезень була б мінімальною.

Математична модель задачі:

Позначимо:

с_ij - тарифи (вартість, час, відстань) перевезення одиниці вантажу з i-го пункту відправлення в j-й пункт призначення;

a_i - запаси вантажу в i-му пункті відправлення;

b_і — потреба у вантажі в j-му пункті призначення;

x_ij - кількість одиниць вантажу, перевезеного з 1-го пункту відправлення в j-й пункт призначення.

Тоді математична модель транспортної задачі про планування перевезень має такий вигляд:

_{m n}

y=∑∑c_ijx_ij→min; (3.9)

^{i=1 j=1 x}_ij^ÎΩ

_{m ____}

Ω: f_j=∑x_ij=b_i, j=1,n; (3.10)

ⁱ⁼¹

_{n ____}

f_n+i=∑x_ij=a_i, i=1,m; (3.11)

^j=1 _{_______ _______}

x_ij≥0; i=1,m; i=1,m. (3.12)

Тут (3.9) - цільова функція, що визначає вартість перевезень усього вантажу. Саме екстремальне (мінімальне) значення цієї функції необхідно знайти в задачі. Причому значення змінних х_ij, при яких цільова функція досягає свого мінімуму, повинні належати області припустимих рішень Ω.

Вирази (3.10) - (3.12) визначають область припустимих рішень Ω. При цьому вираз (3.10) відбиває потреби у вантажі в пунктах призначення, вираз (3.11) визначає запаси вантажів у пунктах відправлення, а вираз (3.12) відокремлює негативну область значень х_ij, в яку дані змінні не можуть потрапляти за своїм фізичним змістом.

Вирази (3.10)-(3.12) називаються обмеженнями задачі лінійного програмування. Вирішення задачі (частковий набір значень змінних x_i) називається припустимим, якщо воно одночасно задовольняє всім 1 обмеженням задачі. Вирішення задачі називається оптимальним, якщо воно забезпечує оптимум (у даному випадку мінімум) функції цілі.

Вважатимемо, що функції y,f₁,f₂, ... ,f_n - неперервні лінійні функції, задані на невід'ємному ортанті евклідового простору Rⁿ. Дані функції мають місце, коли перевезений вантаж є рідиною, сипкою речовиною, дрібними заготівлями або дрібною неспакованою продукцією. Такий вантаж характеризується параметрами, що являють собою вагу, довжину (погонні метри), площу (квадратні метри), об'єм і т.п.

Якщо загальна потреба у вантажі в пунктах призначення дорівнює запасу вантажу в пунктах відправлення, тобто

_{m n}

∑a_i=∑b_j , (3.13)

^{i=1 j=1}

то модель такої транспортної задачі називається закритою. У противному випадку - відкритою.

Теорема 1.1. Для можливості розв'язання транспортної задачі необхідно і достатньо, щоб запаси вантажу в пунктах відправлення були рівні потребам у вантажі в пунктах призначення, тобто щоб виконувалася рівність (3.13).

У випадку перевищення запасу над потребою, тобто вводиться фіктивний (n+1)-й пункт призначення з потребою . При цьому відповідні тарифи вважаються рівними нулю:c_i,n+1=0 (i=1,m) .Така задача буде вже транспортною задачею, для якої умова (3.13) виконується.

Аналогічно, якщо , вводиться фіктивний (m+1)-й пункт відправлення з запасом вантажу .При цьому відповідні тарифи вважаються рівними нулю: c_m+1,j=0 (j=1,n).Така задача буде вже транспортною задачею, для якої умова (3.13) виконується.

Далі будемо розглядати закриту модель транспортної задачі. Якщо ж модель конкретної задачі є відкритою, то, виходячи зі сказаного вище, її необхідно перетворити так, щоб виконувалася рівність (3.13).

У відкритій моделі область припустимих значень (за інших рівних умов) значно ширше, тому цільова функція досягає кращих значень або, принаймні, не гірше.

Особливості вирішення закритої транспортної задачі:

Визначення 1.1. Усяке невід'ємне рішення систем лінійних рівнянь (3.10) і (311) , що обумовлене матрицею X={x_ij], i=1,m, j=1,n, називається планом транспортної задачі.

Визначення 1.2. План X^* =[x^*_ij], i=1,m, j=1,n, при якому функція (3.9) приймає своє мінімальне значення, називається оптимальним планом транспортної задачі.

Число перемінних x_ijy транспортній задачі з m пунктами відправлення і n пунктами призначення дорівнює mn, а число рівнянь у системах (3.10) і (3.11) дорівнює m+n. Оскільки передбачається, що виконується умова (3.13), то число лінійно незалежних рівнянь дорівнює m+n-1. Отже, опорний план транспортної задачі може мати не більше m+n-1 відмінних від нуля невідомих.

Визначення 1.3. План X^* =[x^*_ij], i=1,m, j=1,n є опорним невиродженим, якщо в ньому кількість відмінних від нуля компонентів у точності дорівнює m+n-1, а якщо менше - то виродженим.

Для визначення опорного плану існує декілька методів. Один з них - метод північно-західного кута - буде розглянутий нижче.

Як і для всякої задачі лінійного програмування, оптимальним план транспортної задачі є також опорним планом. Для визначення оптимального плану транспортної задачі можна використовувати диференціальний алгоритм, симплекс-метод та інші універсальні методи. Однака через виняткову практичну важливість цієї задачі і специфіку її обмежень (кожна невідома входить лише в два рівняння систем (3.10) і (3.11), а коефіцієнти при невідомих дорівнюють одиниці) для визначення оптимального плану транспортної задачі розроблені спеціальні методи. Один з них - метод потенціалів - розглядається в даному курсі.

За звичаєм вихідні дані транспортної задачі записують у вигляді табл.3.1.

Таблиця 3.1. Вихідні дані транспортної завдання

Визначення початкового опорного плану транспортної задачі: Вирішення транспортної задачі починають із знаходження будь-якого опорного плану. Для цього розроблені специфічні методи. Один з них одержав у літературі назву "метод північно-західного кута". Іноді його називають також "діагональним методом", "методом перехідних приступів" і т. ін.

Сутність методу полягає в тому, що опорний план знаходять за m+n-1 кроками, на кожному з яких у таблиці транспортної задачі заповнюють одну клітку. Заповнення однієї клітки забезпечує цілком або задоволення потреби у вантажі одного з пунктів призначення (відповідно до того, в стовпці якого знаходиться клітка), або вивіз вантажу з одного з пунктів відправлення (відповідно з того, в рядку якого знаходиться клітка).

Заповнення таблиці слід починати з лівого верхнього квадрата (північно-західного кута). З позиції цього квадрата порівнюють запас вантажу в першому пункті відправлення з потребою першого пункту призначення. Вибирають менший розмір і записують у даний квадрат, який з цього моменту стає "зайнятим". Якщо в клітку записується потреба пункту призначення, то з подальшого розгляду виключають відповідний стовпець таблиці і переходять у ліву сусідню клітку. Якщо в клітку записується запас пункту відправлення, то з подальшого розгляду виключають відповідний рядок таблиці і переходять у сусідню клітку, що знаходиться нижче заповненої.

У новій клітці для частини таблиці, що залишилася, повторюють процедуру першого кроку з урахуванням зміни запасу вантажу одного з І відправників або потреби у вантажі одного з одержувачів у результаті попереднього кроку.

Після m+n-2 описаних вище кроків одержують задачу з одним пунктом відправлення і одним пунктом призначення. При цьому залишається вільною тільки одна клітка, а запаси пункту відправлення дорівнюватимуть потребам пункту призначення. Заповнення цієї клітки, тобто здійснення (m+n-1)-го кроку приводить до шуканого опорного плану.

Слід зауважити, що в процесі використання методу північно-західного кута може трапитися, що потреби у вантажі чергового пункту призначення рівні запасам чергового пункту відправлення. У цьому випадку з подальшого розгляду виключають або стовпець, або рядок, тобто тільки що-небудь одне. Таким чином, запаси відповідного пункту відправлення, або потребу відповідного пункт призначення вважають рівними нулю. Цей нуль записують у чергову клітку, яка заповнюється [61].

Зазначені вище умови гарантують одержання m+n-1 зайнятих кліток, у яких знаходяться компоненти опорного плану.

Опорний план перевезень повинен відповідати таким вимогам:

по-перше, кількість зайнятих маршрутів (кліток) повинно бути на одиницю менше суми числа постачальників т і числа споживачів п, тобто повинна дорівнювати значенню m+n-1;

по-друге, не повинно бути жодного зайнятого маршруту (клітки), що опинився: б єдиним і в рядку, і в стовпці таблиці.

Визначення оптимального опорного плану транспортної задачі:

Для відзначення оптимального плану транспортної задачі розроблено декілька методів. Найбільш часто використовується метод потенціалів. Метод припускає, що вже відомий якийсь опорний план. Його можна одержати, наприклад, розглянутим методом північно-західного кута. Вихідний опорний план необхідно перевірити на оптимальність.

Теорема 1.2. Якщо для деякого опорного плану X^* =[x^*_ij], i=1,m, j=1,n транспортної задачі з заданими тарифами перевезень c_ij існують такі числа α_i(i=1,m) i β_j(j=1,n), що

β_i-α_j=c_ij при x_ij>0 (3.14)

і β_i-α_j≤c_ij при x_ij=0 (3.15)

для всіх i=1,m і j=1,n, то X^* =[x^*_ij] - оптимальний план.

Визначення 1.4. Числа α_i(i=1,m) i β_j(j=1,n) називаються потенціалами відповідно пунктів відправлення і пунктів призначення.

Теорема 1.2 дозволяє побудувати алгоритм знаходження рішення транспортної задачі. Він являє собою наступне.

Нехай знайдений опорний план транспортної задачі. Для кожного з пунктів відправлення і призначення визначають потенціали α_i(i=1,m) i β_j(j=1,n) із системи рівнянь

β_i-α_j=c_ij. (3.16)

Тому що число заповнених кліток дорівнює n+m-1, то система (3.16) із n+m невідомими містить n+m-1 рівнянь. Оскільки число невідомих перевищує на одиницю число рівнянь, одне з невідомих потрібно взяти рівним довільному числу, наприклад α₁=0, і знайти послідовно із системи (3.16) значення інших невідомих.

Після того, як усі потенціали знайдені, дія кожною з вільних кліток визначають числа α_ij=β_i-α_j-c_ij. Якщо серед чисел α_ij немає позитивних, то знайдений опорний план є оптимальним. Якщо ж для деякої вільної клітки α_ij>0, то опорний план , що перевіряється , не є оптимальним, і треба перейти до нового опорного плану. Для цього розглядають усі вільні клітки, для яких α_ij>0, і вибирають ту, для якої число α_ij максимальне. Обрану клітку необхідно заповнити.

Заповнюючи обрану клітку, треба змінити обсяги перевезень, записаних у ряді інших зайнятих клітках і зв'язаних з обраною циклом.

Визначення 1.5. Циклом у таблиці транспортної задачі називається замкнута ломана лінія, вершини якої розташовані в зайнятих клітках таблиці, а ланки - уздовж рядків і стовпів, причому в кожній вершині циклу зустрічаються рівно дві ланки, одна з яких знаходиться в рядку, а інша - у стовпці.

Якщо ломана лінія, що складає цикл, перетинається сама із собою, то точка самоперетину не є вершиною.

При правильній побудові опорного плану для будь-якої вільної клітки можна побудувати тільки один цикл. Після того як для обраної вільної клітки він побудований, необхідно перейти до нового опорного плану. Для цього треба перемістити вантажі в межах кліток, що утворюють цикл. Переміщення роблять за такими правилами:

кожній з кліток, пов'язаних циклом з обраною вільною кліткою, і приписують знак "+" або "-", причому вільній клітці - знак плюс, а всім іншим кліткам - по черзі знаки мінус і плюс;

у вільну клітку переносять менше з чисел x_ij, що знаходяться в мінусових клітках, і одночасно це число додають до відповідних чисел, і що знаходяться "плюсових" клітках, і віднімають із чисел, що знаходяться в "мінусових" клітках. Клітка, що раніше була вільною, стає зайнятою, а "мінусова" клітка, в якій стояло мінімальне число x_ij, стає вільною.

У результаті зазначених вище переміщень вантажів у межах кліток, пов'язаних циклом з обраною вільною кліткою, визначають новий опорний план транспортної задачі. Число зайнятих кліток залишається рівним n+m-1. Якщо в зайнятих "мінусових" клітках циклу є два і більше однакових мінімальних чисел x_ij, то звільняють тільки одну з таких кліток, а інші залишають зайнятими з нульовими постачаннями.

Отриманий новий опорний план транспортної задачі перевіряють на оптимальність. Для цього визначають потенціали пунктів відправлення і призначення і знаходять числа α_ij=β_i-α_j-c_ij для всіх вільних кліток. Якщо серед цих чисел не буде позитивних, то це означає, що новий опорний план є оптимальним. Якщо ж є позитивні числа, то І необхідно перейти до нового опорного плану. У результаті ітераційного плану кінцевого числа переходів одержують оптимальний план процесу після задачі.

Таким чином, процес знаходження рішення транспортної задачі методом потенціалів включає наступні етапи:

1-й етап. Знаходять опорний план.

2 й етап. Знаходять потенціали пунктів відправлення; і призначення.

3-й етап. Визначають числа α_ij для кожної вільної клітки. Якщо серед них немає позитивних, то отримано оптимальний план транспортної задачі, у противному разі переходять до нового опорного плану.

4-й етап. Вибирають серед позитивних чисел α_ij максимальне, будують для відповідної вільної клітки цикл перерахування і роблять зсув за циклом, одержуючи при цьому новий опорний план. Далі переходять до 2-го етапу.

Розглянемо приклад вирішення транспортної задачі методом потенціалів.

Приклад вирішення транспортної задачі методом потенціалів:

Приклад 1.1. Три заводи, що виготовляють бетоні конструкції, постачаються цементом з чотирьох складів. Попит заводів b_j відповідно дорівнює 280, 90 і 180 тис.т/міс. Пропускна здатність складів a_i,- відповідно становить 200, 150, 80 і 120 тис.т/міс. Відстані перевезень (у км)

із і-го складу на j-й завод подані в матриці C=[c_ij]=

Потрібно скласти план перевезень цементу зі складів на заводи, що задовольняв би пропускним спроможностям складів і потребам заводу, а сумарний пробіг вантажного транспорту був би мінімальним.

Вирішення

Позначимо через x_ij - кількість цементу, який щомісяця потрібно доставляти щомісяця на j-го завод з i-го складу. Тоді математична модель задачі має вигляд:

y=x₁₁+5x₁₂+3x₁₃+6x₂₁+8x₂₂+9x₂₃+2x₃₁+7x₃₂+4x₃₃+4x₄₁+x₄₂+11x₄₃→min; (3.17)

^xijÎΩ

Ω: x₁₁+x₂₁+x₃₁+x₄₁=280; (3.18)

x₁₂+x₂₂+x₃₂+x₄₂=90; (3.19)

x₁₃+x₂₃+x₃₃+x₄₃=180; (3.20)

x₁₁+x₁₂+x₁₃=200; (3.21)

x₂₁+x₂₂+x₂₃=150; (3.22)

x₃₁+x₃₂+x₃₃=80; (3.23)

x₄₁+x₄₂+x₄₃=120; (3.24)

x_ij³0. (3.25)

Тут (3.17) - цільова функція, (3.18) - (3.20) - обмеження задачі! що визначають місячні запаси цементу на складах, (3.21) - (3.24) – обмеження задачі, що визначають місячну потребу в цементі на заводах (3.25) - обмеження, що визначає неможливість негативних значень для постачань цементу на заводи.

1-й крок. 1-й етап. Використовуючи метод північно-західного кута, знайдемо опорне рішення транспортної задачі (3.17)- (3.25).

Відповідно до цього методу заповнюємо таблицю, починаючи лівого верхнього квадрата. Порівнюємо запас вантажу в першому пункті відправлення (200 тис.т/міс.) із потребою першого пункту призначення (280 тис.т/міс.). Вибираємо меншу величину (200) і записуємо її в даний квадрат. Оскільки весь запас у першому пункті відправлення вичерпаний, то з подальшого розгляду виключаємо перший рядок і переходимо в сусідню клітку, що знаходиться нижче заповненої. У новій клітці для частини таблиці, що залишилася, повторюємо процедуру заповнення верхньої лівої клітки, але з урахуванням того, що потреба першого пункту призначення зменшилася на 200 тис.т/міс. і стала рівною 80 тис.т/міс. Тобто порівнюємо запас другого пункту відправлення (150 тис.т/міс.) із новою потребою першого пункту призначення (80 тис т/міс). Вибираємо меншу величину(80) і записуємо її в нову клітку Оскільки потреба у вантажі в першому пункті призначення повністю задоволена, то з подальшого розгляду виключаємо перший стовпець і переходимо в сусідню клітку, що знаходиться справа від тільки що заповненої. Для нової верхньої лівої клітки частини таблиці, що залишилася, повторюємо процедуру заповнення з урахуванням зміни запасу в другому пункті відправлення на 50 тис.т/міс. І так доти, поки не буде заповнено m+n-2 кліток.

Остання (m+n-2)-я клітка заповнюється механічно - у неї записується залишкова потреба останнього пункту призначення або залишковий запас останнього пункту відправлення. В умовах задачі це величина 120. Усі проміжні результати по знаходженню початкового опорного плану

Х₀ = відображені в табл. 3.2. Ці результати в таблиці виділені напівжирним шрифтом.

Для початкового опорного плану обчислюємо значення цільової функції (3.17):

y₀=1х200+6х80+8х70+7х20+4х60+11х120=2940 тис.т/міс.

Це значення буде використано на наступних кроках для контролю просування до оптимуму. Значення цільової функції повинно послідовно зменшуватися з кожним кроком.

Таблиця 3.2. Проміжні результати по знаходженню початкового опорного плану

2-й етап. Знайдений опорний план перевіряємо на оптимальність. У зв'язку з там знаходимо потенціали пунктів відправлення і призначення із системи

b₁-a₁=1, b₂-a₂=8, b₃-a₃=4,

b₁-a₂=6, b₂-a₃=7, b₃-a₄=11.

що містить шість рівнянь із сімома невідомими. Вважаючи a₁=0, знаходимо b₁=1, a₂=-5, b₂=3, a₃=-4, b₃=0, a₃=-11. Записуємо знайдені потенціали в табл.3.2.

3-й етап. Для кожної вільної клітки обчислюємо числа α_ij=β_i-α_j-c_ij: α₁₂=-2, α₁₃=-3, α₂₃=-4, α₃₁=3, α₄₁=8, α₄₂=13.

Записуємо знайдені числа у відповідні вільні клітки табл.3.2 і вміщуємо їх у рамочки, щоб відрізняти їх від іншої інформації в таблиці Тому що серед чисел α_ij є позитивні, то опорний план Х₀ не є оптимальним.

4-й етап. Серед позитивних чисел α_ij вибираємо максимальне: α₄₂=13. Для відповідної вільної клітки будуємо цикл, а саму клітку позначаємо знаком «+». У табл.3.2 зайняті клітки, що складають цикл, виділені сірим фоном. Потім позначаємо знаками «-» і «+» по черзі інші клітки циклу, слідуючи уздовж ломаної лінії циклу.

Найменшим із чисел x_ij у «мінусових» клітках є x₃₂ (20). Дана клітка стає вільною, а інші клітки циклу змінюють свої значення в такий спосіб: Х₄₂=20, х₄₃=120-20=100, х₃₃=60+20=80.

У результаті зроблених перетворень одержуємо новий опорний план

X₁=

При такому опорному плані функція цілі (3.17) стає рівною 2680 тис.т/міс, що менше вихідного значення 2940 тис.т/міс.

На цьому закінчується 1-й крок оптимізації. На наступному кроці процедура 1-го кроку повторюється, але без 1-го етапу.

2-й крок. Аналізуємо новий опорний план (табл.3.3) на оптимальність. Знову знаходимо потенціали пунктів відправлення і пунктів призначення, для чого складаємо таку систему рівнянь:

b₁-a₁=1, b₂-a₂=8, b₂-a₄=1,

b₁-a₂=6, b₃-a₃=4, b₃-a₄=11.

Вважаючи a₁=0, знаходимо b₁=1, a₂=-5, b₂=3,a₄=2, b₃=13, a₃=9. Для кожної вільної клітки обчислюємо числа α_ij: α₁₂=-2, α₁₃=10, α₂₃=9, α₃₁= -10, α₃₂=-13, α₄₁=-5.

Тому що серед чисел α_ij є позитивні (α₁₃=10, α₂₃=9), то опорний план X₁ не є оптимальним.

Таблиця 3.3. Новий опорний план

Серед позитивних чисел α_ij вибираємо максимальне: α₁₃=10. Для відповідної вільної клітки будуємо цикл, а саму клітку позначає знаком «+». У табл.3.3 зайняті клітки, що складають цикл, виділені рим фоном. Потім позначаємо вузлові клітки циклу по черзі знаками «-» і «+».

Найменшим із чисел x_ij у «мінусових» клітках є х₂₃ (70). Дана клітка стає вільною, а інші клітки циклу змінюють свої значення в так спосіб: x₁₁=200-70=130, x₁₃=70, х₂₁=80+70=150, x₄₂=20+70=90, x₄₃=100-70=30.

У результаті виконаних перетворень одержуємо новий опори план

Х₂=

При такому опорному плані функція (3.17) стає рівною 1980 тис.т/міс, що значно менше попереднього значення 2680 тис.т/міс.

3-й крок. Аналізуємо новий опорний план (табл. 3.4) на оптимальність. Знову знаходимо потенціали пунктів відправлення і пунктів призначення, для чого складаємо наступну систему рівнянь:

b₁-a₁=1, b₁-a₂=6, b₂-a₄=1,

b₃-a₁=3, b₃-a₃=4, b₃-a₄=11.

Вважаючи a₁=0, знаходимо b₁=1, b₃=3, a₂=-5, b₃=4, a₃=0, a₄=-8, b₂=-7. Для кожної вільної клітки обчислюємо числа α_ij: α₁₂=-12, α₂₂=-10, α₂₃=-1, α₃₁=-1, α₃₂=-14, α₄₁=5. Оскільки серед чисел α_ij одне позитивне (α₄₁=5), то опорний план Х₂ не є оптимальним.

Таблиця 3.4. Новий опорний план

Для відповідної вільної клітки (нижньої, лівої) будуємо цикл, а саму клітку позначаємо знаком «+». У табл.3.4 зайняті клітки, що складають цикл, виділені сірим фоном. Потім позначаємо вузлові клітки циклу по черзі знаками «-» і «+». Найменшим із чисел x_ij у «мінусових» клітках є х₄₃ (30). Дана клітка стає вільною, а інші клітки циклу змінюють свої значення в такий спосіб: x₁₁ =130-30=100, х₁₃ =70+30=100, x₁₄=30.

У результаті зроблених перетворень одержуємо новий опорі план

Х₄=

При такому опорному плані функція (3.17) стає рівною 1830 тис.т/міс, що менше попереднього значення 1980 тис.т/міс.

4-й крок. Аналізуємо новий опорний план (табл.3.5) на оптимальність. Знову знаходимо потенціали пунктів відправлення і пунктів призначення, для чого складаємо наступну систему рівнянь:

b₁-a₁=1, b₁-a₂=6, b₁-a₄=4,

b₃-a₁=3, b₃-a₃=4, b₂-a₄=1.

Вважаючи a₁=0, знаходимо b₁=1, b₃=3, a₂=-5, a₃=-1, a₄= -3, b₂= -2. Для кожної вільної клітки обчислюємо числа α_ij: α₁₂=-7, α₂₂=-4, α₂₃=-1, α₃₁=0, α₃₂=-8, α₄₁=-5. Тому що серед чисел α_ij і немає строго позитивних, то опорний план Х₃ є оптимальним.

Таблиця 3.5. Новий опорний план

Різновиди транспортних задач

Розглянута математична модель (3.9) - (3.12) є класичною моделлю транспортної задачі. У реальній практиці економіста і менеджера, як правило, транспортна задача зустрічається в дещо іншій постановці. Математична модель реальної транспортної задачі може відрізнятися від класичної або видом цільової функції, або видом обмежень, або харак3ером змінних, або будь-яким сполученням перерахованих відмінностей одночасно.

Розглянемо декілька модифікацій транспортної задачі.

Транспортна задача про розподіл випуску продукції

При комплексному вирішенні проблеми виробництва і реалізації продукції виникає задача, що полягає у визначенні такого плану випуск і перевезень готової продукції, при якому досягаються мінімальні пні витрати на її виготовлення і доставку споживачам.

Для вирішення даної задачі розглядається повна собівартість виробництва одиниці продукції на кожному підприємстві (S_i) і транспортні витрати (S_ij), що залежать від типу застосовуваних транспортних засобів і районів розташування заводів-виробників і споживачів.

Математична модель такої задачі має вигляд:

_{m n}

y=∑∑(s_i+s_ij)x_ij→min; (3.26)

^{i=1 j=1 x}_ij^ÎΩ

_{m ____}

Ω: f_j=∑x_ij=b_i, j=1,n; (3.27)

ⁱ⁼¹

_{n ____}

f_n+i=∑x_ij=a_i, i=1,m; (3.28)

^j=1 _{_____ _______}

x_ij≥0; i=1,m; i=1,m. (3.29)

_{_______ _______}

x_ij=int; i=1,m; i=1,m. (3.30)

Якщо за умовою задачі потрібні ще капітальні вкладення в засоби транспорту, то показником ефективності служать приведені витрати, (3.26) матиме вигляд

(3.31)

- нормативний коефіцієнт ефективності капітальних вкладень; к - питомі капітальні вкладення, що приводяться на одиницю перевезень.

Виконуючи підстановку в цільову функцію (3.26) і підстановку в цільову функцію (3.31), задача (3.26) - (3-30) і задача (3.31), (3.27) - (3.30) відповідно приводяться до класичної транспортної задачі, що може бути вирішена методом потенціалів.

Розподільна транспортна задача про вибір засобів доставки вантажу

Змістовна постановка задачі. Нехай через j=1,2, ...,n позначено пункти, що мають вантажі для перевезень об'ємами a_j відповідно. Є m засобів доставки вантажу (видів транспорту). Вантажопідйомність i-го засобу доставки складає р_i а наявний його парк дорівнює b_i, і=1,2,...,m... Вантажі підлягають доставці в один центральний пункт (склад). Витрати при здійсненні однією одиницею і-го засобу доставки від j-го пункту до складу дорівнюють С_ij. Потрібно скласти найбільш економічний план доставки.

Математична модель задачі. Позначимо через Х_ij кількість засобів доставки і-го типу, що відправляється j-го пункту. Тоді математична модель розподільної транспортної задачі про вибір транспортних засобів має вигляд:

(3.32)

(3.33)

(3.34)

(3.35)

(3.36)

Цільова функція (3.32) визначає сумарні витрати на доставку в вантажу на центральний склад. Вираз (3.33) вказує на необхідність вивезення всього вантажу з пунктів відправлення. Обмеження (3.34) вказує те, що кількість використовуваних засобів доставки не повинна перевищувати їхній наявний парк.

Поява параметра ,- у системі обмежень (3.33) перешкоджає зведенню математичної моделі завдання до моделі класичної. Тому вирішувати її методом потенціалів неможливо. Вирішення даної задачі класичними методами лінійного програмування також неможливе через цілочисельність змінних . Вирішення задачі можна одержати методом відсікання (шляхом введення в задачу додаткових обмежень у вигляді нерівностей Гомори), однак процедура вирішення різко ускладнюється. Тому вирішення задачі найбільш доцільно покласти на програм; Solver (Пошук рішення) інформаційної системи Microsoft Excel.

Транспортна задача про двохетапне перевезення вантажу

Змістовна постановка задачі. Однорідний вантаж потрібно доставити з т пунктів відправлення в п пунктів призначення. При доставці в пункти призначення вантажі можуть бути спочатку доставлені на р перевалочних пунктів. Задано вартості перевезень С_у з кожного пункту відправлення в кожний пункт призначення і перевалочний пункт, а також вартості перевезення з кожного перевалочного пункту в пункт призначення.

Математична модель завдання. Позначимо:

- вартість перевезення одиниці вантажу з i-го пункту відправлення j-й пункт призначення, ;

- вартість перевезення одиниці вантажу з i-го пункту відправлення в k-й перевалочний пункт ;

- вартість перевезення одиниці вантажу з к-го перевалочного пункту j-й пункт призначення

- запаси вантажу в i-м пункті відправлення;

- потреба у вантажі j-м пункті призначення;

- місткість k-го перевалочного пункту;

- кількість вантажу, перевезеного з i-го пункту відправлення в j-й пункт призначення;

- кількість вантажу, перевезеного з і-го пункту відправлення в k-й перевалочний пункт;

- кількість вантажу, перевезеного з k-го перевалочного пункту в j-й пункт призначення.

Математична модель задачі з урахуванням вище наведених позначень може бути подана у вигляді задачі лінійного програмування:

; (3.37)

(3.38)

(3.39)

(3.40)

(3.41)

(3.42)

Тут цільова функція (3.37) складається з витрат трьох видів: на уставку частини вантажу з пунктів відправлення в пункти призначення, маючи перевалочні пункти; на перевезення частини вантажу з пункт призначення в перевалочні пункти; на доставку вантажу з перевалочних пунктів у пункти призначення. Система обмежень (3.38) говорить про те, що сумарні об'єми вантажів, що вивозяться з пунктів відправлення, не можуть перевищувати запаси вантажів у цих пунктах. Система обмежень (3.39) свідчить про те, що сумарні об'єми вантажів, що надходять у пункти призначення, не можуть бути менше відповідних потреб пунктів призначення. Система обмежень (3.40) означає, що сумарне завезення вантажів на кожний перевалочний пункт не може перевищувати його місткості. Система обмежень (3.41) вказує на те, що весь вантаж із перевалочних пунктів повинен бути вивезений повністю.

Як і в попередній задачі, математична модель (3.37) - (3.42) не може бути приведена до класичної. Тому вирішення задачі найбільш доцільно покласти на програму Solver (Пошук рішення) інформаційної системи Microsoft Excel.

Транспортна задача про двохетапне перевезення вантажу декількох видів

Змістовна постановка завдання. Вантаж, що включає q видів продукції, потрібно доставити з т пунктів відправлення в n пунктів призначення. При доставці в пункти призначення вантажі можуть бути спочатку доставлені на q перевалочних пунктів. Задано вартості перевезень для кожного виду вантажу з кожного пункту відправлення в кожний пункт призначення і перевалочний пункт, а також вартості перевезення з кожного перевалочного пункту в кожний пункт призначення.

Математична модель завдання. Позначимо:

- вартість перевезення одиниці 1-го виду вантажу з г-го пункту відправлення в у-й пункт призначення,

- вартість перевезення одиниці l-го виду вантажу з i-го пункту відправлення в к-й перевалочний пункт,

- вартість перевезення одиниці l-го виду вантажу з k-го перевалочного пункту в j-й пункт призначення,

- запаси l-го виду вантажу в і-м пункті відправлення;

- потреба в l-м виді вантажу j-м пункті призначення;

- місткість k-го перевалочного пункту стосовно l-го виду вантажу;

- кількість l-го виду вантажу, перевезеного з i-го пункту відправлення j-й пункт призначення;

- кількість l-го виду вантажу, перевезеного з i-го пункту відправлення k -й перевалочний пункт;

- кількість l-го виду вантажу, перевезеного з k-то перевалочного пункту j-й пункт призначення.

Математична модель задачі з урахуванням вище приведених позначень може бути подана у вигляді задачі лінійного програмування:

(3.43)

(3.44)

(3.45)

(3.46)

(3.47)

(3.48)

Математична модель задачі відрізняється від попередньої тільки там, що вона враховує різновид вантажів.

Транспортна задача про двохетапне перевезення вант декількох видів за запитами споживачів

Існує модифікація транспортної задачі двохетапного перевезення вантажів декількох видів, у якій кількість вантажу в пунктах відправлення не фіксована. Вона залежить від запитів споживачів.

Математична модель задачі. Позначимо:

- вартість перевезення одиниці l-го виду вантажу з i-го пункту відправлення j-й пункт призначення,

- вартість перевезення одиниці l-го виду вантажу з i-го пункту відправлення в k-й перевалочний пункт,

- вартість перевезення одиниці l-го виду вантажу з k-го перевалочного пункту в j-й пункт призначення,

- витрати на виробництво l-го виду вантажу в 2-м пункті відправлення;

- потреба в l-м виді вантажу в j-м пункті призначення;

- місткість k-то перевалочного пункту стосовно l-го вантажу;

- кількість l-го виду вантажу, перевезеного з i-го пункту відправлення в j-й пункт призначення;

- кількість l-го виду вантажу, перевезеного з i-го пункту відправлення в k-й перевалочний пункт;

- кількість l-го виду вантажу, перевезеного з k-го перевалочного пункту в j-й пункт призначення;

- кількість виробленого l-го виду вантажу в i-м пункті відправлення.

Математичну модель задачі з урахуванням вище наведених значень можна подати у вигляді задачі лінійного програмування:

(3.49)

(3.50)

(3.51)

(3.52)

(3.53)

(3.54)

Цільова функція в математичній моделі (3.49) - (3.54) відрізняється від цільової функції (3.43) тільки тим, що враховує витрати на виробництво продукції (вантажу) в пунктах відправлення.

Транспортна задача про закриття підприємства

Змістовна постановка задачі Виробниче об'єднання складається з п заводів і т складів. Задано потреби складів у продукті й вартості на перевезення продуктів з кожного заводу на кожний склад. Задані фіксовані вартості функціонування заводів і можливості заводів по виробництву продукту. Виробниче об'єднання розглядає можливість закриття одного або декількох заводів. Це повинно зменшити витрати на перевезення. Які заводи, якщо це доцільно, повинні бути закриті?

Математичне формулювання завдання. Позначимо:

- вартості перевезення j-го заводу на i-й склад;

- потреби i-го складу в продукті, i=1,…,m;

- можливість j-го заводу по виробництву продукту;

- фіксована вартість функціонування j-го заводу;

- булєве число, що показує, чи потрібно закрити j-й завод (значення 0), чи залишити його працювати (значення 1);

- кількість перевезеного товару з j-го заводу на і-й склад.

Тоді математична модель транспортної задачі про закриття заводу може бути подана у такому вигляді:

(3.55)

(3.56)

(3.57)

(3.58)

(3.59)

Тут цільова функція (3.55) визначає загальні витрати виробничої об'єднання на функціонування заводів і транспортування готової продукції на склади. Обмеження (3.56) визначає можливості заводів з виробництва продукції. Обмеження (3.57) визначають потреби складів у готовій продукції.

Читайте також:

1. IV. Алгоритм вирішення задачі
2. IV. Алгоритм розв’язання задачі
3. IV. Алгоритм розв’язання задачі
4. IV. Алгоритм розв’язання задачі
5. IІI. Формулювання мети і завдань уроку. Мотивація учбової діяльності
6. Rete-алгоритм
7. V. ФОРМУЛЮВАННЯ ЗАВДАНЬ УРОКУ
8. АЛГОРИТМ
9. Алгоритм
10. Алгоритм
11. Алгоритм
12. АЛГОРИТМ

Переглядів: 2080