Контрольная работа по "Линейная алгебра"

Таб.2

В результате заполненными оказываются следующие клетки матрицы  перевозок ( ): . Транспортные расходы по этой программе равны:

Мы получили первый опорный план. Число загруженных  клеток должно быть равно m+n-1. У нас это 6. что мы и получили.

Проверим является ли найденный опорный план оптимальным. Для этого воспользуемся методом потенциалов, основанном на следующей теореме.

Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел и , удовлетворяющих условия

(базисные клетки)               (1)

(свободные клетки),       (2) 

где  и называются потенциалами соответственно поставщиков и потребителей; - стоимость перевозок.

Таким образом, чтобы проверить план на оптимальность, следует сначала построить систему  потенциалов. 

Для построения системы потенциалов используем условие (1), где  стоимость перевозок единицы груза от i-го поставщика  к j-му потребителю для занятых клеток.

Система состоит  из 6-и уравнений и 7 неизвестных. Т.е. одно из них можно считать свободным и приравнять его к нулю. Пусть это будет . Тогда остальные неизвестные найдутся при решении системы и будут равны соответственно: , , , , , .

Таб. 2 примет вид:

 

Таб.3

После того как  система потенциалов построена  следует проверить условие оптимальности (2) для свободных клеток, то если найти косвенные тарифы и сравнить их с истинными цифрами .

Разность  называют оценкой пустой клетки, она равна коэффициенту при переменной в выражении функции затрат через не основные переменные.

 

Все оценки не отрицательны, поэтому план таблицы 3 – оптимален.

Минимальные затраты: 830.