Условия оптимальности плана перевозок транспортной задачи. - Транспортная задача и ее решение методом потенциалов

Признак оптимальности плана перевозок T. З. устанавливает теорема.

Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным, необходимо и достаточно, чтобы ему соответствовала система из (m + n) чисел U1, U2, ..., Um ; V1, V2, ...Vn, удовлетворяющих условиям:

Числа Ui и Vj называются соответственно потенциалами пунктов отправления и пунктов назначения или потенциалами поставщиков и потребителей. А условия (1.6), (1.7) условиями оптимальности или потенциальности плана перевозок T. З..

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

T. З., т. е. задачу нахождения минимума функции Z:

Xij ? 0, ; (1.1)

(1.2)

> min. (1.3)

Можно рассматривать как двойственную задачу к некоторой исходной прямой задаче линейного программирования (з. л.п.), условия которой легко получить по правилам построения двойственных задач. [ ]

Каждому ограничению-равенству вида соответствует в прямой задаче свободная переменная Ui еа каждому ограничению-равенству вида соответствует в прямой задаче свободная переменная Vj.

Каждой несвободной переменной xij ? 0, ; соответствует в прямой задаче ограничение-неравенство

Ui + Vj ? cij, ; (1.8)

Максимизируемой функцией прямой задачи является функция

(1.9)

Задача (1.8), (1.9) в свою очередь является двойственной к T. З.. Теперь используя 1-ю и 2-ю теоремы двойственности докажем сформулированную теорему.

Необходимость. Пусть X = (xij) - оптимальный план T. З.. Поскольку оптимальный план является всегда допустимым, следовательно, он удовлетворяет условиям (1.1) и (1.2) T. З., т. е.

Xij ? 0, ; ;

Согласно 1-й теореме двойственности прямая задача (1.8), (1.9) также имеет оптимальное решение U1, U2, ..., Um; V1, V2, ...Vn; удовлетворяющее условиям (1.8), т. е. Ui + Vj ? cij, ; и следовательно, условия (1.7) выполняются. По 2-й теореме двойственности оптимальные решения обеих задач удовлетворяют условиям дополняющей нежесткости:

Xij (Ui + Vj - cij) = 0.( ; )

Отсюда следует, что для xij > 0, Ui + Vj - cij = 0 или Ui + Vj = cij т. е. условия (1.6) выполняются.

Вторая группа условий

,

Выполняется автоматически, в силу условий (1.2).

Достаточность. Пусть для некоторого допустимого плана существует система чисел ; , удовлетворяющая условиям (1.6), (1.7). Выполнение этих условий означает, что эта система чисел является допустимым решением прямой задачи (1.8), (1.9) (условия (1.8) при этом будут выполняться). Выполнение условий (1.7) означает, что допустимое решение U1, U2, ..., Um; V1, V2, ...Vn прямой задачи и допустимый план двойственной задачи (T. З.) удовлетворяют условиям дополняющей нежесткости:

Xij (Ui + Vj - cij) = 0

(вторая группа условий; выполняется автоматически).

По 2-й теореме двойственности допустимый план является оптимальным. Теорема доказана.

Рассмотрим связь условий оптимальности (1.6) и (1.7) плана перевозок транспортной задачи с критерием оптимальности решения в симплексном методе.

Решим T. З. симплексным методом, одновременно найдем и оптимальное решение U1, U2, ..., Um; V1, V2, ...Vn задачи (1.8), (1.9). Вычислим оценки ?ij векторов :

?ij =Ui + Vj - cij, ; .

Транспортная задача является задачей на минимум и поэтому в симплекс-методе, критерий оптимальности решения для з. л.п. на минимум формируется так: если для данного опорного решения все оценки неположительны, то это опорное решение оптимально. Поэтому и для T. З. решение оптимально, если все оценки ?ij ? 0. При этом для всех базисных векторов :

?ij =Ui + Vj - cij,

Следовательно, для всех базисных переменных

Xij: Ui + Vj = cij

Т. е. получим условие (1.6).

Для небазисных векторов : ?ij =Ui + Vj - cij ? 0, т. е. для небазисных переменных xij:

Ui + Vj ? cij

Т. е. получили условие (1.7).

Из теоремы следует, что для того чтобы план T. З., записанный в таблице был оптимален, необходимо выполнение следующих условий:

- для каждой базисной клетки (i, j) сумма потенциалов должна быть равна соответствующему тарифу Cij: Ui + Vj = cij;

Если опорный план является вырожденным и какая-то из базисных переменных равна нулю, то для клетки, соответствующей этой переменной тоже должно выполняться условие Ui + Vj = cij;

- для каждой свободной клетки (i, j) сумма потенциалов должна быть меньше либо равна Cij: Ui + Vj ? cij или

Дij = Ui + Vj - cij ? 0.

Значения Дij являются оценками соответствующих свободных переменных xij; будем называть их оценками свободных клеток (i, j).

Для базисных клеток оценки Дij = Ui + Vj - cij = 0.

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

Похожие статьи




Условия оптимальности плана перевозок транспортной задачи. - Транспортная задача и ее решение методом потенциалов

Предыдущая | Следующая