45. Общая и каноническая злп. Переход от общей задачи к канонической.

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:ограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных

хi, (i Î 1:m), которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

Общий вид:

Переход от от общей к канонической. Любое ограничение в форме неравенства введением дополнительной неотрицательной переменной может превратиться в ограничение – равенство. Так, к примеру, условие

a_i1x₁ +a_i2x₂+…+a_inx_n  b_i

эквивалентно двум ограничениямa_i1x₁ +a_i2x₂+…+a_inx_n+x_n+1= b_i , x_n+10.

Переменные типа x_n+1 называют фиктивными или дополнительными

46. План злп, область допустимых планов, базисный (опорный) план, невырожденный план, базисные переменные.

Планом ЗЛП называется всякий вектор х из пространства Rⁿ.

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

Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию max f(x) = f(x*).

Величина f* =f(х*) называется оптимальным значением целевой функции.

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

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. 

47. Графический метод решения злп.

Если задача линейного программирования в стандартной форме содержит всего лишь две переменные x₁ и x₂ (т.е. n=2), то ее можно решить следующим способом, основанным на ее геометрической интерпретации. Каждое неравенство системы ограничений и условие неотрицательности представляют собой полуплоскость. Пересечение полуплоскостей образует выпуклое многоугольное множество (многогранник допустимых решений).

Целевая функция графически изображается множеством параллельных прямых, называемых линиями уровня, каждой из которых соответствует конкретное значение z.Для решения задачи линия уровня сдвигается в пределах области допустимых решений (многогранника допустимых решений) в направлении вектора-градиента

grad z = f (x) = до самой крайней точки области для задачи максимизации, и в направлении антиградиента– grad z=для задачи минимизации. Координаты этой точки и определяют решение ЗЛП (оптимальный план задачи).

Рис1. Геометрическая интерпретация ЗЛП в стандартной форме

Рис.2 Пример пустой области допустимых решений (X)

Рис.3 Пример ЗЛП, имеющий бесконечное множество решений (ребро АВ многогранника допустимых решений ABCDE)

48. Симплекс-метод решения злп: идея метода и построение первоначального базисного плана. Симплексная таблица.

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

Допустим, имеется исходная ЗЛП в канонической форме:F(X)=c₁X₁+c₂X₂+...+c_nX_n => max

a_1,1X₁+a_1,2X₂+...+a_1,nX_n=b₁ a_2,1X₁+a_2,2X₂+...+a_2,nX_n=b₂ . . . . . . . . . . . . . . . . . . . . .  a_m,1X₁+a_m,2X₂+...+a_m,nX_n=b_m

В общем случае m любых переменных можно выразить через оставшиеся (n-m) переменных, например - X₁...X_m через X_m+1...X_n: 

X₁=B₁-(A_1,m+1X_m+A_1,m+2X_m+2+...+A_1,nX_n) ........................................................... X_m=B_m-(A_m,m+1X_m+1+A_m,m+2X_m+2+...+A_m,nX_n) 

Здесь коэфициенты В_i и А_i,j выражаются через b_i и a_i,j.  ПеременныеX₁... X_mназываются базисными,а X_m+1...X_n-свободными.  Если положитьX_m+1=...=X_n=0, то X_i=B_iи если при этом всеB_i =0, то и X_i =0, и такой вектор:  X=(B₁, B₂, ..., B_m, 0, 0 ,..., 0)  называется базисным Выражение целевой функции через свободные переменные:F=C₀-(C_m+1X_m+1+...+ C_nX_n)  Здесь коэффициентыC₀, C_m+1, ..., C_nвыражаются черезс_j, B_i, a_{i, j}. 

Начальная симплекс-таблица

Составим по этим данным так называемую начальную симплекс-таблицу. 

Базис. Перем.	Своб. Перем.	X1	.......	Xi	.......	Xm	Xm+1	.......	Xk	.......	Xn
X1	B1	1	.......	0	.......	0	A1,m+1	.......	A1,k	.......	A1,n
X2	B2	0	.......	0	.......	0	A2,m+1	.......	A2,k	.......	A2,n
.....	.....	.....	.....	.....	.....	.....	.....	.....	.....	.....	.....
Xi	Bi	0	.......	1	.......	0	Ai,m+1	.......	Ai,k	.......	Ai,n
.....	.....	.....	.....	.....	.....	.....	.....	.....	.....	.....	.....
Xm	Bm	0	.......	0	.......	1	Am,m+1	.......	Am,k	.......	Am,n
F(X)	C0	0	.......	0	.......	0	Cm+1	.......	Ck	.......	Cn

Замечание:В простейшем случае в качестве базисных переменных можно взять такие m переменных, каждая из которых входит только в одно ограничение, причем с положительным знаком, а все свободные членыb_i>0.