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

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

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) следует, что ранг матрицы системы ограничений транспортной задачи меньше числа ограничений системы равного ( ). Можно доказать, что ранг равен ( ). Отсюда следует, что базисное решение транспортной задачи будет иметь ( ) базисную компоненту.

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

 

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