Главная | Обратная связь

Симплексний метод оптимізації транспортних перевезень

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

Оскільки ТЗ є окремим випадком загальної задачі ЛП (ЗЗЛП), то до неї також цілком можливо застосувати всі стандартні методи її розв’язання (зокрема найвідоміший з них – симплексний метод), попередньо привівши ТЗ до вигляду задачі ЛП і врахувавши її специфічність. Для цього необхідно провести над математичною моделлю ТЗ ряд перетворень. Ці перетворення будемо здійснювати на конкретному прикладі ТЗ, а саме для m постачальників (m=3) і n споживачів продукції (n=4).

а) спочатку запишемо вихідну систему рівнянь ТЗ у такому вигляді:

|| || || ||

b₁ b₂ b₃ b₄

де: x_ij –кількість продукції, відправленої від і-го постачальника до j-го споживача;

а_i – обсяг продукції наявної у і-го постачальника ( i=1, 2, 3);

b_j –обсяг продукції необхідної j-ому споживачу (j=1, 2, 3, 4).

б) подамо її у вигляді системи (т + n)лінійних рівнянь таким чином:

в) замінимо x₁₁ на x₁, x₁₂ на x₂, x₁₃ на x₃, . . ., x₃₄ на x₁₂. Маємо:

г) додамо, як того вимагає симплексний метод, до всіх рівнянь додаткові перемінні, які становитимуть початковий базисний розв’язок ТЗ:

У результаті цих перетворень ми утворили систему (т + п)лінійних рівнянь з (m´п + т+ n)позитивними перемінними, розв’язати яку можна за допомогою симплекс-методу. Оскільки сума рівнянь системи в рядках дорівнює сумі рівнянь системи в стовпцях, то ми одержали лінійно-залежну систему рівнянь. Щоб привести її до нормального (лінійно-незалежного) виду, одне з рівнянь системи (переважно останнє) можна без шкоди для кінцевого результату розв’язку ТЗ відкинути. Тоді ми матимемо (т + п – 1)лінійних рівнянь і (m´п + т+ n - 1) перемінних.

Необхідно також відзначити те, що у класичній ТЗ перевезти продукцію від усіх постачальників (а_i)потрібно так, щоб усі замовлення були виконані (b_j),а загальна вартість (L) транспортних перевезень була б мінімальною, тобто:

,

де: с₁ , с₂, ... с_k –вартість перевезення одиниці продукції від кожного постачальника до кожного споживача (k = 1,т´ п).