4) правильность полученного ответа - оптимального плана - проверяется путем подстановки значений базисных неизвестных в целевую функцию; ответы должны совпасть.

5.  Геометрическая интерпретация ЗЛП и графический метод решения (при двух неизвестных)

Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы. Целевая функция  f = c₁x₁ + c₂x₂ геометрически изображает семейство параллельных прямых, перпендикулярных вектору n (с₁,с₂).

Теорема.    При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают.

На этих утверждениях основан графический метод решения ЗЛП.

6. Алгоритм графического метода решения ЗЛП.

1)  В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений;

2)  найти полуплоскости решения каждого неравенства системы (обозначить стрелками);

3)  найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;

4)  построить вектор n (с₁,с₂) по коэффициентам целевой функции  f = c₁x₁ + c₂x₂;

5)  в семействе параллельных прямых целевой функции выделить одну, например, через начало координат;

6)  перемещать прямую целевой функции параллельно самой себе по области решения, достигая max f при движении вектора n и min f при движении в противоположном направлении.

7)  найти координаты точек max и min по чертежу и вычислить значения функции в этих точках (ответы).

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

Приведем экономическую формулировку транспортной задачи по критерию стоимости:

Однородный груз, имеющийся в m пунктах отправления (производства) А₁, А₂, ..., А_m соответственно в количествах а₁, а₂, ..., а_m единиц, требуется доставить в каждый из n пунктов назначения (потребления) В₁, В₂, ..., В_n  соответственно в количествах b₁, b₂, ..., b_n единиц. Стоимость перевозки (тариф) единицы продукта из A_i в B_j известна для всех маршрутов A_iB_j и равна C_ij (i=1,m; j=1,n). Требуется составить такой план перевозок, при котором весь груз  из пунктов отправления вывозиться и запросы всех пунктов потребления удовлетворяются  (закрытая модель), а суммарные транспортные расходы минимальны.

Условия задачи удобно располагать в таблицу, вписывая в клетки количество перевозимого груза из A_i в B_j  груза X_ij > 0, а в маленькие клетки - соответствующие тарифы C_ij:

8. Математическая модель транспортной задачи.

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

Число r = m + n - 1, равное рангу системы (1), называется рангом транспортной задачи. Если число заполненных клеток (X_ij ¹ 0) в таблице равно r, то план называется невырожденным, а если это число меньше r, то план вырожденный - в этом случае в некоторые клетки вписывается столько нулей (условно заполненные клетки), чтобы общее число заполненных клеток было равно r.

Случай открытой модели Σа_i ¹ Σb_j  легко сводится к закрытой модели путем введения фиктивного потребителя B_n+1 c потребностью b_n+1=Σa_i-Σb_j, либо - фиктивного поставщика А_m+1 c запасом a_m+1=Σb_j-Σa_i ; при этом тарифы фиктивных участников принимаются равными 0.

9. Способы составления 1-таблицы (опорного плана).

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

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

10. Метод потенциалов решения транспортной задачи.

Определение: потенциалами решения называются числа a_i®A_i, b_j®B_j, удовлетворяющие условию a_i+b_j=C_ij (*) для всех заполненных клеток (i,j).

Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n неизвестными, имеющую бесчисленное множество решений; для ее определенности одному неизвестному придают любое число (обычно a₁=0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности. Если известны потенциалы решения X₀ транспортной задачи и для всех незаполненных клеток выполняются условия a_i+b_j £ C_{i j}, то X₀ является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличились.

Определение: циклом пересчета таблицы называется последовательность клеток, удовлетворяющая условиям:

1) одна клетка пустая, все остальные занятые;

2) любые две соседние клетки находятся в одной строке или в одном столбце;

3) никакие 3 соседние клетки не могут быть в одной строке или в одном столбце .

Пустой клетке присваивают знак « + », остальным - поочередно знаки « - » и « + ».

Для перераспределения плана перевозок с помощью цикла перерасчета сначала находят незаполненную клетку (r, s), в которой a_r+b_s>C_rs, и строят соответствующий цикл; затем в минусовых клетках находят число X=min{X_ij}. Далее составляют новую таблицу по следующему правилу:

1) в плюсовые клетки добавляем X;

2) из минусовых клеток отнимаем Х;

3) все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающее новое решение X, такое, что f(X₁) £ f(X₀); оно снова проверяется на оптимальность через конечное число шагов обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

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

1) проверяем тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;

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

3) проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью « 0 »;

4) проверяем опорный план на оптимальность, для чего:

а) составляем систему уравнений потенциалов по заполненным клеткам;

б) находим одно из ее решений при a₁=0;

в) находим суммы a_i+b_j=C¢_ij («косвенные тарифы») для всех пустых клеток;

г) сравниваем косвенные тарифы с истинными: если косвенные тарифы не превосходят соответствующих истинных(C¢_ij £ C_ij) во всех пустых клетках, то план оптимален (критерий оптимальности). Решение закончено: ответ дается в виде плана перевозок последней таблицы и значения min f.

    Если критерий оптимальности не выполняется, то переходим к следующему шагу.

5) Для перехода к следующей таблице (плану):

а) выбираем одну из пустых клеток, где косвенный тариф больше истинного (C¢_ij= a_i+b_j > C_ij );

б) составляем цикл пересчета для этой клетки и расставляем знаки « + », « - » в вершинах цикла путем их чередования, приписывая пустой клетке « + »;

в) находим число перерасчета по циклу: число X=min{X_ij}, где X_ij - числа в заполненных клетках со знаком « - »;

г) составляем новую таблицу, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла

6) См. п. 3 и т.д.

Через конечное число шагов (циклов) обязательно приходим к ответу, ибо транспортная задача всегда имеет решение.