5. Экономико-математическая модель транспортной задачи. Составление первоначального опорного плана.

Приведем экономическую формулировку транспортной задачи (ТЗ) по критерию стоимости: однородный груз, имеющийся в m пунктах отправителя А1, А2. Требуется доставить каждый груз из n пунктов назначения В1, В2, …,Вn. Стоимость перевозки из a_i в b_i известна для всех маршрутов и равна S_ij. Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится и запросы всех пунктов потребления удовлетворяются. x_ij>>0

Из приведенной таблицы легко усматривается и составляется математическая модель ТЗ для закрытой модели. ( Σ_i=1^ma_i= Σ_j=1^mb_j)

X11+X12+…+X1n=a1

X21+X22+…+X2n=a2

……………………….

Xm1+Xm2+…+Xmn=am (1)

X11+X21+…+Xm1=b1

X21+X22+…+X2n=b2

……………………….

X1n+X2n+…+Xmn=bn

F=C11X11+C12X12+…+C1nX1n+…+CmnXmn →min (общая стоимость перевозок) (2)

Число r=m+n-1 равное рангу систем (1) называется рангом транспортной системы. Если число заполненных клеток таблицы равно r, то план называется невырожденным. А если это число меньше, то – вырожденным. В случае открытой модели Σa_i≠Σb_j легко сводится к закрытой модели путем введения Bn+1 с потребностью b_n+1= Σa_i+Σb_j либо a _n+1=Σb_j-Σa_i.

Составление опорного плана.

1. Способ северо-западного угла (диагонали). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка. Оставшейся части таблицы причем максимально возможным числом: либо полностью вывозится груз из a_i, либо полностью удовлетворяется потребность b_j. Процедура производится до тех пор, пока на каком-то шаге не исчерпаются запасы a_i и не удовлетворятся потребности b_j. В заключении проверяют, что найденные компоненты плана удовлетворяют горизонтальным и вертикальным уравнениям и что выполняются условия невырожденности плана.

2. Способ наименьшего тарифа. Сущность способа в том, что каждый шаг записывается та клетка оставшейся части таблицы, которая имеет наименьший тариф. В основном действует аналогичный способ.

6. Метод потенциалов, открытая модель тз. Приложение транспортных моделей к решению некоторых экономических задач.

Потенциалом решения называется числа α_i→Ai, β_i→Bj удовлетворяющие условию α_i+β_i→Сj (1), для всех заполненных клеток ij. Соотношение (1) определяет систему из m+n-1 линейных уравнений с m+n неизвестными, имеющих бесчисленное множество решений. Для определения этой системы одному неизвестному придают любое число, обычно α_i=0, тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности:1. Если известны потенциальное решение х0 и для всех незаполненных клеток выполняется условие α_i+β_i≤Сj, то х0 является оптимальным планом Тз. 2.если план не оптимален, то необходимо перейти к следующему плану таблицы так, чтобы транспортные расходы не увеличились.

Алгоритм метода потенциала.

1. проверяем тип модели ТЗ и в случае открытой модели сводим ее к закрытой.

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

3. проверяем план на удовлетворение системы уравнений и на невырожденность. В случае вырожденности плана добавляем условно заполненные клетки.

4. проверяем опорный пан на оптимальность для чего:а) составим систему уравнений потенциалов по заполненным клеткам.б)находим одно из ее решений при α_i=0.в)находим суммы.г)сравниваем косвенные тарифы с истинными. Если косвенные тарифы не превосходят соответсвующих им истинных С’ij≤Cij во всех пустых клетках, то план оптимален. Решение закончено. Ответ дается в виде плана перевозок последней таблицы и значения minf. Если критерий оптимальности не выполняется. То переходим к сдудующему шагу.

5.а)выбираем одну из пустых клеток, где косвенный тариф обычно всех больше истинного. С’ij=α_i+β_i>Сij. б)составим цикл пересчета для этой клетки расставим знаки + и – в вершинах цикла путем их чередования, приписывая пустой клетке +. в)находим число пересчетов по циклу. Число х=хmin{хij}, где хij – числа, заполненных клетках со знаком -. г)составим новую таблицу, прибавляя х в положительные клетки и отнимая х из отрицательных клеток.

6.см п.3 а-д. Через оптимальное число шагов обязательно приходим к ответу, ибо ТЗ всегда имеет решение.