Рішення транспортної задачі методом північно-західного кута

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

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

Представлення транспортної задачі у вигляді таблиці

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

Читати повністю

Транспортна задача лінійного програмування

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

Перш ніж перейти до розгляду основних методів розв'язання транспортної задачі, визначимо принципи її формулювання. Отже, нехай маємо  пунктів відправлення вантажів (постачальників) , на яких зосереджені запаси якого-небудь однорідного вантажу в обсягах  одиниць відповідно. Величини , при цьому, визначають максимально можливі розміри вивозу вантажу з пунктів відправлення. Сумарний запас вантажу у постачальників становить одиниць. Крім того, є  пунктів призначення (споживачів) , які подали заявки на поставку вантажу в обсягах  одиниць. Сумарна величина заявок становить . Вартість перевезення однієї одиниці вантажу від постачальника  до споживача  подані як лементи матриці (транспортні тарифи):

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

Читати повністю

« Попередня сторінка