3.7.Алгоритм построения начального опорного плана.

1.Среди отрицат. чисел единичного столбца выбирают max по модулю, просматр-т соотв-ю строку и по любому отрицат. числу этой строки назн-т разрешающ. строку. Если в этой строке нет отрицат. числа, то задание не имеет плана.

2.Для чисел с одинак. знаками сост-т симплексные отн-я.Миним-е симплексн-е отн-я опред-т разреш-ю строку.

3.Строят новую симплексн. Таблицу. Процесс продолж-т до тех пор, пока все числа в единичном столбце не станут положит-ми.

4.1 Симметричные и несимметричные двойственные задачи

Рассм. ЗЛП, записанную в симметричной форме записи

(1-3)

Коэф-ты ЗЛП 1-3 занесем в спец таблицу:

a11	a12	…	a1n	b1
a21	a22	…	a2n	b2
…	…	…	…	…
am1	am2	…	amn	bm
c1	c2	…	cn	f

Транспонируем:

a11	a21	…	am1	c1
a12	a22	…	am2	c2
…	…	…	…	…
a1n	a2n	…	amn	cn
b1	b2	…	bm

По транспортированной таблице строим нов. Задачу и в ней переменные обозначаем через y (m-переменных и n-ограничений):

(4-6)

ЗЛП (1-3) (4-6) наз симметричными взаимодаойственными задачами. Между элементами этих зад сущ-т след отношения: 1) если в зад 1-3 цел-я функ-и максимизир-ся, то в зад 4-6 — минимизир-ся; 2) если в зад 1-3 имелось n- перемен-х и m-огранич-й, то в зад 4-6 — m-перем-х и n-огранич-й; 3) если в зад 1-3 знаки срав-я ≤, то в 4-6 — ≥; 4) Матрица коэф-в при переменных осн ограничений одной задачи явл транспонированной по отнош-ю к соотв-й матрице др задачи.

Рассмотрим ЗЛП, построенную в произвольной форме записи:

(7)

Можно доказ-ть, что двойственной для зад (7) б/задача:

(8)

Каждому i-му ограничению зад (7) соотв-т i-я переменная зад (8). Если i-е огранич-е в зад (7) имеет знак сравн-я (≤, ≥), то i-я перем-я в зад (8) имеет условие неотрицательности. Если же i-е огранич-е в зад (7) имеет знак сравн-я (=), то на i-ю перем-ю в зад (8) не накладыв-ся условие неотрицательности. Каждой j-ой переменной зад (7) соотв-т j-е огранич-е зад (8). И если на j-ю перем-ю зад (7) есть усл-е неотриц-ти, то j-е огран-е зад (8) имеет знак сравн-я (≥). Если на j–ю перемен-ю в зад (7) нет условия неотриц-ти, то j-е огранич-е в зад (8) имеет знак (=).

4.2 Соответствие между переменными пары взаимодвойственных задач

Приведем симметричные взаимодвойств. задачи к каноническому виду:

f =c₁x₁+c₂x₂+…+c_nx_n(max);

a₁₁x₁+a₁₂x₂+…+a_1nx_n+x_n+1=b₁ ;

a₂₁x₁+a₂₂x₂+…+a_2nx_n+x _n+2=b₂; (9)

…

a_m1x₁+a_m2x₂+…+a_mnx_n+x_n+m=b_m;

x_j>=0, j=1,n+m

φ =b₁y₁+b₂y₂+…+b_my_m(min);

a₁₁y₁+a₂₁y₂+…+a_m1y_m-y_m+1=c₁;

a₁₂y₁+a₂₂y₂+…+a_m2y_m-y_m+2=c₂; (10)

…

a_1ny₁+a_2ny₂+…+a_mny_m-y_m+n=c_n;

y_i>=0, i=1,n+m

Между перем. задач 9 и 10 сущ. след соответствие. Основные перем. исходной задачи соотв. основным перем. двойственной задачи.

ОП ДП

X₁ X₂ … X_n X_n+1 X_m+2 X_m+n

(11)

Y_m+1 Y_m+2 Y_m+n Y₁ Y₂ … Y_n

ДП ОП

Используя соотв-ие между перем. (11) можно найти оптим. План двойствен. задачи (10). Значения базисных переменных оптимального плана двойственной задачи находится в f строке оптимальной симплексной таблицы решение исходной задачи под соответствующими свободными переменными.