7. Методы построения опорного решения

Опорным решением транспортной задачи называется любое допустимое решение для которого вектор условия соответствующий положит. Координат. Линейно не зависим. В виду того что ранг системы векторов условий транспортной задачи равен n+m=1 опорное решение не может иметь отличных от 0 координат равен n+m=1

Любое допустимое решение транспорт. Задачи можно записать в ту же таблицу что и исходные данные .клетки таблицы в которых наход . отличные от 0 или базисные 0-ые перевозки называются –ЗАНЯТЫМИ соответственно остальные—СВОБОДНЫМИ

Аi\Bj	20	30	40
40	3 Х11	4 Х12	7 Х13
50	4 Х21	6 Х22	10 Х23

Для избежания трудоемких решений вводят понятие ЦИКЛ

Цикл так же используется для перехода от 1-ого опорного к др.

ЦИКЛОМ- называется такая последоват. Клеток таблицы транспортной задачи которой 2 и только 2 соседние клетки расположены в одной строке либо столбце цикл изображен в таблице транспортной задачи в виде замкнутой ломаной линии

В любой клетке цикла происходит поворот звена ломаной на 90⁰

Для того что бы система векторов условий транспортной задачибыла линейно зависимой необходимо чтобы из клеток таблицы можно было выделить часть образующую цикл

СЛЕДСТВИЕ:

Допустимое решение транспортной задачи является опорным тогда и только тогда когда из занятых им клеток таблиц нельзя образовывать ни одного цикла

5 Постановка транспортной задачи

ФОРМУЛИРОВКА:

Однородный груз сосредоточен у m поставщика в объемах а1,а2...,аn

Данный груз необходимо доставить n- потребителям в объемах в1,в2…,вn

Известны коэффэциенты Сij стоимось перевозки ед . груза от каждогоi-ого поставщика к j-ому потребителю требуется составить такой план перевозок при котором запасы всех поставщиков будут вывезены полностью а запросы всех потребителей будут полностью удовлетворены и суммарные затраты на перевозку грузов будут минимальны .исходные данные транспортной задачи обычно записывают в виде таблицы

Аi\Вj	В1	…	Вn
A1	C1	…	C1n
A2	C2	…	C2n
…	…	…	…
Am	Cm1	…	Cm2

Исходные данные задачи могут быть так же представлены в виде вектора запас поставщиков (а1,а2…am)=А

Вектора запроса потребителей (в1,в2…вт)=В

И матрицы стоимости

С=с1,…, с1n

_ _ _ _ _

Cm1,…, cm2