рямая и двойственная задача

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

Для того, чтобы завершить шаг преобразований, ведущих к новому опорному плану, в новом базисе выразим новую БП x_j₀из уравнения с номером i₀ системы x_i+_ijj=b_i(j=m+1,n), b_i0,i=1,m через СП

x_i₀+_i_0,_m₊₁x_m₊₁+…+_io_,_j_0-1x_jo_-1+_i₀_j₀x_j₀+_i_0,_j₀₊₁x_j₀₊₁+…+_i₀_nx_n=_io

x_j₀=_i₀/_i₀_j₀-((_i_0,_m₊₁/_i₀_j₀)x_m₊₁+…+ (_i_0,_j_0-1/_i₀_j₀)x_j_0-1+(1/_i₀_j₀)x_i₀+(_i_0,_j₀₊₁/_i₀_j₀)x_jo₊₁+…+(_i₀_n/_i₀_j₀)x_n (1)

Аналогично, если мы подставим в выражение (1) в остальные ограничения (1) ограничения и в ЦФ max(min)F=₀-_jx_j(j=m+1), получим след. формулу:

X_i=(_i_i₀_j₀-_i₀_ij₀)/_i₀_j₀-((_i_,_m₊₁_i₀_j₀-_i_0,_m₊₁_ij₀)/_i₀_jo+…-(_ij₀/_i₀_j₀)x_i₀+…+((_in_i₀_j₀-_i₀_n_ij₀)/_i₀_j₀)x_n),i=1,m; ii₀ (2)

F= (₀_i₀_j₀-_j₀_i₀)/_iojo-(((_m₊₁_i₀_j₀-_j₀_i_,_m₊₁)/_iojo)x_m₊₁+…-(_j₀/_iojo)x_io+…+((_nx_iojo-_jo_i₀_n)/_i₀_j₀)x_n)

Из формул (1)-(3) следуют правила пересчета элементов таблиц:

1)из выражения (1) следует, что элемент новой таблицы, стоящий на месте разрешающего , заменяется обратной величиной.

2)из выражения (1) следует, что оставшиеся элементы разрешающей строки i₀новой таблицы равны соответственно элементам разрешающей строки старой таблицы, деленным на разрешающий элемент.

3)оставшиеся элементы разрешающего столбца из выражений (2) и(3) новой таблицы равны соотв. элементам разрешающего столбца старой таблицы, деленным на разрешающий элемент и изменением знака на противоположный.

4)из формул (2) и (3) следует, что все оставшиеся элементы рассчитываются по правилу прямоугольника. Для этого, чтобы получить элемент новой таблицы, надо из соотв. элемента новой таблицы вычесть произведение второстепенной диагонали разделенное на разрешающий элемент.

18) Теорема Если в индексной строке последней симплексной табл, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечное множество оптимальных планов

Доказательство. Пусть в оптимальном плане Aj₀ = О, где jo принадлежит множеству индексов СП, а минимальное симплексное отношение соответствует строке iго- Тогда, введя Xj₀ в базис, получим новое значение ЦФ.

Значение ЦФ при переходе к новому опорному плану не изменилось.

Если нулевых небазисных оценок в последней симплексной таблице окажется несколько, то, введя каждую из соответствующих переменных в базис, найдем оптимальные планы x1*,x2*,... ,хk*, для которых значение ЦФ будет одно и то же, т. е.

Z(x1)=z(x2)=…z(xk)

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

=1x1+2x2+…..+kxk, 1+2+….+k=1

i0 (i=1,k)

Эта ф-ла опред-т бесконечное мн-во оптимальн. Планов.

Следств: Если в инд. Строке симпл. табл, содержащей оптимальный план, все оценки СП положит., то найденные опт план и единств.

19) Теорема 1.10. Если в индексной строке симплексной таблицы ЗЛП на максимум содержится отрицательная оценка j₀ < 0, а в соответствующем столбце переменной Xj₀нет ни одного положительного элемента, то целевая функция на множестве допустимых планов задачи не ограничена сверху.

Доказательство. Если бы все оценки индексной строки Aj были неотрицательны, то опорный план был бы оптимальным. Пусть j₀ < 0. Тогда можно попытаться, не изменяя нулевых значений всех свободных переменных x_m+i,... , х_п в равенстве (1.95), кроме Xj₀, увеличить значение целевой функции Z за счет увеличения переменной Xj₀ > 0. Полагая в равенствах (1.96) все Xj, кроме Xj₀, равными нулю, получаем

Так как Xi 0, то

Пусть все aij₀ 0. Тогда при любом Xi₀ 0 имеем Xi 0. Что касается целевой функции Z, то, взя^тз в качестве Xj₀достаточно большое положительное число, вследствие того, что j₀ < 0, можно сделать значение

как угодно большим. В самом деле, так как j₀ < 0, при Xj₀ —> оо имеем Z = о — j₀Xj₀ — оо, т.е. целевая функция Z не ограничена сверху.

рямая и двойственная задача

Рассмотрим задачу вида:

Max F=c₁x₁+c₂x₂+…+c_nx_n

a₁₁x₁+a₁₂x₂+…+a_1nx_nb₁

......................................

a_k1x₁+a_k2x₂+…+a_knx_nb_k

a_k+1,1x₁+a_k+1,2x₂+…+a_k+1,nx_n=b_k+1

…………………………………………..

a_m₁x₁+a_m₂x₂+…+a_mnx_n=b_m

x_j0, j=1,l; x_j-произвольные, j=l+1,n

Двойственной по отношению к исходной(прямой) задаче наз. задача вида:

min =b₁y₁+b₂y₂+…+b_my_m

a₁₁y₁+a₂₁y₂+…+a_m1y_mc₁

…………………………………..

a_1ly₁+a_2ly₂+…+a_mly_mc_l

a_1,l+1y₁+a_2,l+1y₂+…+a_m,l+1y_m=c_l+1

…………………………………………….

a_1ny₁+a_2ny₂+…+a_mny_m=c_n

y_i0, i=1,k; y_i-произвольные, i=k+1,m

Сравнивая 2 задачи видно, что:

1)если у прямой задачи ЦФ на max ,то в дв-ной на min и наоборот.

2)коэф-ми при неизвестных ЦФ дв-ной задачи явл-ся свободные члены прямой задачи, а правыми частями в осн-х ограничениях дв-ной задачи явл-ся коэф-ты при неизвестных ЦФ прямой задачи.

3)матрица, составленная из коэф-тов осн-х ограничений прямой задачи и аналогичная матрица дв-ной задачи получаются друг из друга транспонированной.

4)число переменных прямой задачи равно числу ограничений дв-ной задачи и наоборот.

5)если переменная x_j прямой задачи принимает только неотрицательные значения, то j-ое ограничение в системе осн-х ограничений дв-ной задачи явл-ся неравенством. Если же x_j прямой задачи может принимать любые значения, то j-ое ограничение в системе осн-х ограничений дв-ной задачи явл-ся уравнением.