Мітки: транспотрна таблиця

Побудова опорного плану транспортної задачі методом мінімального елемента

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

method_minimum_element161

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

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

Читати далі

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

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

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

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

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

Читати далі