Анализ транспортной задачи

Для любой ЗЛП, заданной в каноническом виде имеются три возможных результата:

1. Задача разрешима,

2. Задача неразрешима из-за неограниченности целевой функции,

3. Задача несовместна.

Причем, какая ситуация будет реализована можно узнать только в процессе ее решения симплекс-методом.

Теорема. Для того чтобы транспортная задача была разрешима необходимо и достаточно выполнение условия баланса.

Доказательство.

Необходимость. Пусть задача разрешима и оптимальное решение. Так как - оптимально решение, то ограничения (1) и (2) выполнены

,

,

Сложим первую группу неравенств по индексу i, а вторую по j.

Получим

, (5)

. (6)

Так как порядок суммирования не меняет значения выражения, то левые части полученных неравенств одинаковы, откуда следует

.

Достаточность. Пусть условие баланса выполнено, докажем, что задача разрешима. Первоначально докажем, что дополнительное множество непустое. Введем , где

. (7)

Очевидно, что , то есть (3) выполнено.

Убедимся теперь, что выполнены (1) и (2).

В самом деле

,

и так как выполнено условие баланса, то окончательный вид (1)

.

А (2)

,

.

Таким образом, матрица , заданная формулой (7) является допустимым решением транспортной задачи.

Осталось доказать, что целевая функция (4) на допустимом множестве ограничена сверху.

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

Замечание 1. Если считать, что - стоимость перевозки продукции от поставщика к потребителю, то всегда . В этом случае, для доказательства ограниченности функции (4) сверху, достаточно того, что . Однако в общем случае целевые коэффициенты могут быть отрицательными. Например, если есть прибыль от единицы продукции. Тогда при решении задачи на минимум необходимо поменять знаки на противоположные.

Замечание 2. К задаче вида (1)-(4) могут сводиться и другие вербальные модели возможно не имеющие ни какого отношения к перевозкам. Однако всегда ЗЛП (1)-(4) называется транспортной задачей.

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

Так как транспортная задача является ЗЛП в канонической форме, причем в ней не существует единичного столбца, то при решении этой задачи должно быть два этапа:

1. Построение начального базисного решения,

2. Решение транспортной задачи.

Замечание 3. Из равенств (6) и (7) следует, что ранг матрицы системы ограничений транспортной задачи меньше числа ограничений системы равного (). Можно доказать, что ранг равен (). Отсюда следует, что базисное решение транспортной задачи будет иметь () базисную компоненту.

Для ЗЛП на первом этапе необходимо вводить искусственные переменные и решать задачу с помощью симплекс-метода с искусственным базисом. Достоинством транспортной задачи является то, что ее начальное базисное решение может быть построено без использования искусственных переменных.

 

Методы построения начального опорного плана транспортной задачи.