16. Симплекс - метод решений задач линейного программирования.

Симплекс - выпуклый многогранник в N-мерном пространстве имеющий N+1 вершину и грань. Рис 16.1. Рассмотрим способ решения задачи линейного программирования симплекс-методом. Пусть система ограничений задана в форме равенств

(1)

Пусть r<n, выразим r-независимых переменных через остальные n-r:

Х_i, i=1,2….. -базисные

X_j, j= r+1,n – свободные

т.к свободным переменным можно придавать любые значения, то X_j=0 при j= r+1,n; Х_i=B_i при i=1,r; col(b₁ (x₁),b₂ (x₂),…. b_r (x_r),0(x_r+1) ,0(x_n)) - первое базисное решение. Полученные решения являются допустимыми, т.к X_j=0 при j= r+1,n; Х_i=B_i при i=1,r;

R=C₁X₁+C₂X₂+C_nX_n (3) подставим вместо базисных элементов их выражения через свободное R=Cо’+C_r+1’X_r+1+ C_r+2’X_r+2+Cn’Xn.

Для 1-ого базисного решения R=C₀’ (5)

Далее переходим ко 2-му базисному решению таким образом, чтобы значение линейной формы r не увеличилось (пусть ищем минимум R). Переход осуществляется следующим образом – одна из базисных неизвестных заменяется свободной неизвестной и находится второе базисное решение. Этот процесс повторяется до тех пор, пока r не достигнет минимального значения.

Рассмотрим процедуру достижения минимума линейной формы:

R=3-X₄+X₅

X=arg min R(X), rangA=3

1-е Б.р: Х=col(2(x₁),7(x₂),2(x₃), 0(x₄), 0(x₅))

При переходе возникает вопрос об увеличении x₄.

Х₄ можно увеличивать только до двух, т.к. в противном x₁ случае становится <0, что по условиям линейного программирования недопустимо.

2-е Б.р: Х=col(0(x₁),3(x₂),4(x₃),2(x₄),0(x₅))

Выразим новые базисные переменные x₂, x₃ ,x₄ через свободные x₁,x₅

R=1+ x₁+ 2x₅

X(опт)=X(2-ого Б.р)= col (0(x₁),3(x₂),4(x₃),2(x₄),0(x₅)) – задача решена.

17.Метод искусственного базиса

Рассмотрим различные случаи нахождения 1-ого базисного решения. Ограничения имеют вид неравенств:

чтобы перейти к равенствам введем дополнительные переменные:

(2)

Матрицы дополнительных переменных образуют диагональную первую подматрицу, элементы которой положительны, дополнительные переменные положительны и могут быть использованы для определения 1-ого Б.Р., которые имеют вид: Х_n+j=b_j, j=1,m. Свободные переменные: Х_i=0 i=1,n. Это решение является дополнительным, т.к оно содержит m-положительных компонентов, остальные m-компоненты =0

2)

(4)

Для этого выберем из системы уравнений (1) у которого правая часть max b_j>b_k, выберем уравнение у которого b_j максимальное, остальные умножаем на (-1) и складываем каждое из них с выбранным уравнением у которого b максимальное (b_k=b_m), тогда получим новую систему, состоящую из m-1 уравнений эквивалентных исходной но с положительным коэффициентом единичной подматрицы.

(5)

(6)

Где a’_ji=-a_j2+a_mi,b’_j=b_m-b_j, i=1,n; j=1,m-1(7)

Новая система имеет единичную подматрицу с положительными элементами (порядок матрицы m-1), для того чтобы дополнить эту подматрицу до подматрицы порядка m введем в уравнение (6) искусственную переменную (Х_n+m+1) со знаком «+» в результате получим:

(8)

Тогда переменные Х_j,i=n+1,n+(m-1), совпадая с (Х_n+m+1) образуют единичную подматрицу с положительными элементами, которую использую для нахождения первого базисного решения Х_j ≥0, однако при достижении оптимума новая переменная (Х_n+m+1)=0. Чтобы исключить базисный вектор, составляющий эту переменную, её вводят в критерий R в след виде:

, где М- большое положительное число (если ищем максимум)

Значение М должно превышать на много значение R, которое ожидается при решении задачи

3)

Представляет собой простую комбинацию одного из случаев для неравенства 1-ого вида как в случай 1), а для неравенства 2-вида как в случае 2).