1.3. Методи складання початкового опорного плану
Як і для інших завдань лінійного програмування, ітераційний процес з відшукання оптимального плану транспортної задачі починається з опорного плану.
Розглянемо систему обмежень (2) і (3) транспортної задачі. Вона містить mn невідомих і m + n рівнянь,
Пов'язаних співвідношенням (4). Якщо скласти почленно рівняння окремо підсистеми (2) і окремо підсистеми (3), то отримаємо два однакових рівняння. У таблиці таке додавання рівнозначно відповідно Почленне додавання стовпців і почленно додаванню рядків.
Наявність в системі обмежень двох однакових рівнянь говорить про її лінійної залежності. Якщо одне з цих рівнянь відкинути, то в загальному випадку система обмежень має містити m + n-1 лінійно незалежних рівнянь, з ледовательно, невироджених опорний план транспортної задачі містить m + n-1 позитивних компонент або перевезень.
Таким чином, якщо будь-яким способом отримано невироджених опорний план транспортної задачі, то в матриці
(Xij) (i = 1, 2. m; j = 1, 2. n) значень його компонент (таблиці 2) позитивними є тільки
M + n-1, а інші рівні нулю.
Якщо умова транспортної задачі і її опорний план записані у вигляді таблиці, то клітини, в яких знаходяться відмінні від нуля перевезення, називаються зайнятими, а решта незайнятими.
Зайняті клітини відповідає невідомим, і для невиродженого опорного плану їх кількість дорівнює
M + n-1. Якщо обмеження транспортної задачі записані в вигляді (2) і (3) то, як відомо, базисним невідомим, включеним в опорний план, відповідає система лінійно незалежних векторів.
Всякий план транспортної задачі, що містить більше
M + n-1 зайнятих кліток, не є опорним, так як йому відповідає лінійно залежна система векторів. При такому плані в таблиці завжди можна побудувати замкнутий цикл, за допомогою якого зменшують число зайнятих клітин до m + n-1.
Циклом називається набір клітин виду (i1 j1) (i1 j2) (j2 i2) (j1 im), в якому дві і тільки дві сусідні клітини розташовані в одному стовпці або одному рядку таблиці, причому остання клітина знаходиться в тому ж рядку або стовпці , що і перша.
Якщо до зайнятих клітинам, що визначає опорний невироджених план, отже, і ациклічності, приєднати будь-яку незайняту клітку, то план стає опорним, з'являється єдиний цикл, всі вершини якого, за винятком однієї, лежать в зайнятих клітинах.
Існує кілька простих схем побудови початкового опорного плану транспортної задачі.
При складанні початкового опорного плану методом північно-західного кута вартість перевезення одиниці не враховується, тому побудований план далекий від оптимального, отримання якого пов'язане з великим обсягом обчислювальних робіт. Тому розглянутий метод використовується при обчисленнях за допомогою ЕОМ.
При використанні методу мінімальної вартості запаси постачальників перерозподіляються споживачам за мінімальними цінами. а в методі подвійного переваги перерозподілу переважно виробляються через ті клітини, чиї вартості мінімальні як для постачальників. так і для споживачів.
Вартості планів, отриманих методами мінімальної вартості і подвійного переваги менше вартості плану, отриманого методом північно-західного кута, значить вони ближче до оптимального.
Між собою методи мінімальної вартості і подвійного переваги рівноцінні, їх легко програмувати. Отримані плани доводять до оптимального методом потенціалів.
1.4. Поняття потенціалу й циклу
Якщо план X * = (x * ij) транспортної o завдання є оптимальним, то йому відповідає набір з m + n чисел Ui * і Vj *. які відповідають умовам
(I = 1, 2, 3. m; j = 1, 2, 3. n).
Числа Ui * і Vj * називаються потенціалами відповідно постачальників і споживачів.
Доведення. Транспортну задачу мінімізації лінійної функції Z = при обмеженнях
можна розглядати як двоїсту деякої вихідної завдання лінійного програмування, умови якої виходять за загальною схемою, якщо кожному обмеженню виду xi1 + xi2 +. + Xin = ai у вихідній задачі відповідає змінна Ui (i = 1, 2. m), а кожному обмеженню виду x1j + x2j + xmj = bj змінна Vj (j = 1, 2. n), а саме: максимізувати лінійну функцію f = при обмеженнях Ui + Vj Cij
(I = 1, 2. m; j = 1, 2. n).
План X * є оптимальним планом двоїстої задачі, тому план Y * = (Ui *, Vj *) є планом вихідної завдання і на підставі теореми подвійності
На підставі теореми про подвійну задачі, отримуємо що обмеження вихідної задачі, відповідні позитивним компонентам оптимального плану двоїстої задачі, задовольняються як строгі рівності, а відповідні компонентам, рівним нулю, як нерівності, т. Е.
З доведеної теореми випливає: для того щоб початковий опорний план був оптимальним, необхідно виконання наступних умов:
для кожної зайнятої клітини сума потенціалів повинна дорівнювати вартості одиниці перевезень, що стоїть в цій клітці:
для кожної незайнятої клітини сума потенціалів повинна бути менше або дорівнює вартості одиниці перевезення, що стоїть в цій клітці:
Якщо хоча б одна незайнята клітина не задовольняє умові (6), то опорний план є неоптимальним і його можна поліпшити, вводячи в базис вектор, відповідний клітці, для якої порушується умова оптимальності, (т. Е. В клітку треба перемістити кілька одиниць вантажу ).
Таким чином, для перевірки на оптимальність необхідно спочатку побудувати систему потенціалів.
Для побудови системи потенціалів використовуємо умову
де Cij вартість перевезення одиниці вантажу зайнятої клітини в i-му рядку і j-му стовпці.
Систему потенціалів можна побудувати тільки для невиродженого опорного плану. Такий план містить m + n-1 лінійно незалежних рівнянь виду (5) з n + m невідомими. Рівнянь на одне менше, ніж невідомих, тому система є невизначеною і одному невідомому (зазвичай Ui) надають нульове значення. Після цього інші потенціали визначаються однозначно.
Нехай відомий потенціал Ui; тоді з рівності (5) слід
Якщо відомий потенціал Vj. то з того ж рівності маємо
Таким чином, для визначення невідомого потенціалу від величини Cij зайнятої клітини слід відняти відомий потенціал.
Набором називається довільна сукупність перевезень транспортної таблиці.
Ланцюгом називають такі набори, коли кожна пара сусідніх клітин в ланцюзі розташовані або в одному стовпці, або в одному рядку.
Циклом називається ланцюг, крайні елементи якої знаходяться або в одному рядку, або в одному стовпці.
1.5.Крітерій оптимальності базисного рішення транспортної задачі
Базове розподіл поставок оптимально тоді і тільки тоді коли оцінки всіх вільних клітин більше нуля. Для вільних клітин будується цикл перерахунку, і в вершинах цього циклу розставляються послідовність чергуються знаків, починаючи зі знака плюс у вільній клітці. До коефіцієнтам витрат таблиці поставок в кожному рядку і кожному стовпці треба додати такі числа (потенціали) щоб коефіцієнт витрат в заповнених клітинах стали рівними нулю.
Отримані при цьому коефіцієнти витрат вільних клітин рівні оцінками цих клітин.
1.6. Розподільчий метод вирішення транспортної задачі
Один з найбільш простих методів вирішення транспортної задачі - розподільний метод.
Нехай для транспортної задачі знайдено початкове опорне рішення і обчислено значення цільової функції на цьому рішенні Z (). По теоремі для кожної вільної клітини таблиці завдання можна побудувати єдиний цикл, який містить цю клітку і частина клітин, зайнятих опорним рішенням. Означивши цей цикл і здійснивши зрушення (перерозподіл вантажу) по циклу на величину =, можна отримати нове опорне рішення Х2.
Визначимо, як зміниться цільова функція при переході до нового опорного рішення. При зсуві на одиницю вантажу по циклу, відповідному клітці (l, k), приріст цільової функції дорівнює різниці двох сум: =, де - сума вартостей перевезень одиниць вантажу в непарних клітинах циклу, відмічені знаком «+», - сума вартостей перевезень одиниць вантажу в парних клітинах циклу, відмічені знаком
У клітинах, відмічені знаком «+», величини вантажу додаються, що призводить до збільшення значення цільової функції Z (), а в клітинах, відмічені знаком «-», величини вантажу зменшуються, що призводить до зменшення значення цільової функції.
Якщо різниця між сумою для вільної клітини (l, k) менше нуля, тобто 1 2 3 Переглянути всі
Схожі роботи:
Оптимальні рішення за допомогою лінійних транспортнихзадач
частиною складних оптимізованих завдань Рис. 2.1. Різновиди транспортнихзадач В откритойзадаче з перевищенням ресурсів. + Сгр) г) в деяких випадках при решеніеоткритихтранспортнихзадач допускається використання в якості критерію - суми.
Узагальнення многоперіодіческой транспортнойзадачі
Курсова робота >> Економіко-математичне моделювання
тари в спеціалізованих транспортних засобах: відкритих вагонах, на. вирішення проблем, що виникають в системі, в процесі її функціонування. 2. Структурний подання многоперіодіческой транспортнойзадачі Многоперіодіческую транспортнуюзадачу.
Постановка транспортнойзадачі загального вигляду
з постановки завдання. Обмеження завдання візьмуть вигляд: Ця умова для вирішення закритих і откритихтранспортнихзадач (ЗТЗ.). Очевидно, що для розв'язання задачі 1 необхідно, щоб.
Транспортнаязадача (8)
рівність не дотримується, то задача називається відкритою. Для решеніятранспортнойзадачі необхідно, щоб вона була. за посиланням. [30] Рішення симплекс-методом → Решеніетранспортнойзадачі симплекс-методом Транспортнуюзадачу можна вирішувати також.
Транспортнаязадача (7)
ми розглянемо решеніетранспортнойзадачі за допомогою Microsoft Office Excel. Нам дана задача. Для решеніятранспортнойзадачі в Excel.