Курсовая работа: Решение транспортной задачи в Excel

3. a _1' =120-60 = 60, b_1' = 0

4.В первом столбце запрещать уже нечего. Текущая таблица содержит две клетки (1,2) и (1,3).

1.Выбираем клетку (1,2)

_{2 .} x₁₂ =min{110,100} = 100

3.a₁ =110-100 = 10, b^' ₁ = 0

4.Текущая таблица содержит одну клетку (1,3).

1. Выбираем последнюю клетку(1,3)

2. x₁₃ =min{10,10} = 10

3.a₁ ^' = b₃ = 0

4.Таблица исчерпана. Конец.

Переходим к описанию следующего шага метода потенциалов.

ШАГ 2. Проверка текущего плана на оптимальность.

Признаком того, что текущий план перевозок является оптимальным, служит условие

(1)u_i +vj -c_ij ≤0

которое выполняется для всех клеток таблицы. Неизвестные здесь величины u_i и vj(называемые потенциалами) определяются из условий

(2)u_i + v_j = c_ij

Условие (1) означает невозможность появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля (У нас: "...цена перевозки единицы продукции по коммуникации равна разности цен в конце и в начале пути")

Так как заполненных клеток в таблице (m+n-1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n-1) уравнений относительно (m+n) неизвестных. Чтобы найти решение (хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных (произвольное) равным некоторому произвольно выбранному числу. Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно (продолжаем работать с нашим "старым" примером и найдем потенциалы для начального плана, построенного способом МС).

Заполненные клетки Уравнения

(1,1) u₁ + v₁ =5

(1,2) u₁ + v₂ =10

(1,3) u₁ + v₃ =12

(2,3) u₂ +v₃ =4

(3,2) u₃ +v₂ =0

Положим, например, неизвестное u₁ равным 0 (через него можно из первых трех уравнений найти v₁ , v₂ и v₃ ). Последовательно из них находим u_{2 ,} u_3.

Этот метод можно сформулировать в виде единого правила:

Неизвестный потенциал находится вычитанием известного из цены перевозки в заполненной клетке