Специальные задачи линейного программирования

2. Основные свойства транспортной задачи

Математические модели любых транспортных задач ЛП обладают общими чертами, а именно,

коэффициенты целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);
коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);
коэффициенты в ограничениях принимают только два значения, это нули и единицы.
В силу этих особенностей транспортная задача обладает следующими свойствами.
1. Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонентов.
Доказательство. Количество базисных компонент определяется число линейно-независимых ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы. Действительно, сложив первые m ограничений и следующие n ограничений задачи, получим

Но в закрытой модели выполняется балансовое равенство

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

Теорема 2. Оптимальный план закрытой модели транспортной задачи существует всегда.
Доказательство. Оптимальное решение задачи ЛП существует, если, во-первых, существует допустимое решение и, во-вторых, целевая функция ограничена на этом допустимом решении.
Покажем существование допустимого решения. Так как суммарные запасы совпадают с суммарными потребностями то всегда можно найти такой план перевозок, который будет допустимым решением (все запасы вывозятся и все потребности выполняются в силу балансового равенства).
Покажем ограниченность целевой функции. Так как





3. Основные теоремы решение

Базисное решение закрытой модели транспортной задачи

Данная модель является открытой, так как А>В в этом случае нам надо добавить столбец, в стоимость мы поставим 0, а в запасы нужно добавить не достающие значение. В нашем случае 50.

Будет иметь следующий вид:

Теперь расставим значения, начнем с наименьшей стоимости.

Проверка занятых клеток (m+n-1) если окажется что число занятых клеток меньше (m+n-1), то дополним их до (m+n-1) нулями. Теперь найдем сумму занятых клеток, S = значение*стоимость.

=70+10+180+210+40=510 (Данный план не оптимален.)
Используя первое условие оптимального плана, найдем m+n чисел, так чтобы сумма потенциалов для занятых клеток была ровна стоимости.



= большему числу занятых клеток.
Проверяем второе условие оптимального плана, т.е. сравниваем суммы потенциалов со стоимостями. Если эти суммы не больше стоимости, то план оптимальный, в противном случае неоптимальный. Следует перейти к улучшению.

Рассмотрим все свободные клетки, где произошло нарушение оптимального плана, и выберем ту в которой разность (Ai+Bj)-Cij наибольшее поставим (+), затем для этой клетки согласно утверждению о циклах стоимости единицы цикла, отметим эти клетки по переменно.