Симплексный метод решения задач ЛП.

До того как решать задачку ЛП симплекс-методом ее нужно привести к каноническому виду :

(1.7)

(1.8)

(1.9)

Для этого в случае необходимости задачка (1.1) поиска минимума сводится к задачке на поиск максимума (1.7) методом конфигурации символов коэффициентов Сj

;

Неравенства (1.2) преобразуются в строгие равенства методом введения дополнительных неотрицательных переменных; условия неотрицательности (1.3) распространяются на все переменные методом введения подстановок Симплексный метод решения задач ЛП..

Пример. Дана задачка ЛП в общем виде:

Приведем ее к каноническому виду. Условие неотрицательности не распространяется на переменную х2. Потому введем подстановку: х2 = х5 – х4, где .

Тогда

Изменим вид экстремума на максимум:

Изменим неравенства на строгие равенства методом введения дополнительных неотрицательных переменных. Тогда

Главные понятия и определения. Начальная задачка Симплексный метод решения задач ЛП. (1.7), (1.8), (1.9) может быть представлена в векторной форме:

x1Р1+x2Р2+…+xnPn=P0

С=(c1, c2 … cn); X=(x1,x2 … xn); P1,P2…Pn, P0 – m-мерные вектор-столбцы.

Вектор X=(x1,x2 … xn) именуется опорным планом задачки ЛП, если он удовлетворяет ограничениям (1.8); (1.9) и содержит m хороших от нуля положительных компонент. Другие Симплексный метод решения задач ЛП. (n-m) частей опорного плана равны нулю. Метод симплекс-метода подразумевает переход от 1-го опорного плана к другому с повышением при всем этом значения мотивированной функции.

В неких случаях начальный опорный план можно просто найти. Это происходит тогда, когда посреди векторов Pj имеется m единичных. В данном случае надлежащие единичным Симплексный метод решения задач ЛП. векторам переменные в опорном плане будут отличны от нуля. Они именуются базовыми. Другие переменные равны нулю; они именуются свободными.

Симплекс-преобразования длятся до того времени, пока посреди чисел не будет отрицательных.

Начальная симплекс-таблица в общем случае имеет вид

i Базис Сб P0 C1 C2 Cm Cm Симплексный метод решения задач ЛП.+1 Cn
P1 P2 Pm Pm+1 Pn
P1 C1 b1 a1m+1 a1n
P1 C2 b2 a2m+1 a2n
m Pm Cm bm amm+1 amn
M+1 F0 Δm+1 Δn

В столбце Сб записываются коэффициенты мотивированной функции с теми же индексами, что и векторы базиса.

В столбце Р0 записываются положительные составляющие начального Симплексный метод решения задач ЛП. опорного плана, в нем же в итоге вычислений получают положительные составляющие рационального плана. В столбцах Р1…Рn записаны коэффициенты ограничений при неведомых.

В (m+1)-й строке: F0 – текущее значение мотивированной функции; в столбцах Pj записаны числа .

Метод решения.

1. Задачку ЛП приводят к каноническому виду и находят Симплексный метод решения задач ЛП. начальный опорный план.

2. Составляют начальную симплекс-таблицу.

3. Определяют, имеется ли хотя бы одно отрицательное число Δj в (m+1)-й строке. Если нет, то отысканный опорный план оптимален.

4. Находят меньшее отрицательное Δj и соответственный столбец обозначают как разрешающий. Если в разрешающем столбце посреди чисел aij нет положительных, то мотивированная функция не Симплексный метод решения задач ЛП. ограничена сверху, а задачка ЛП не имеет решения.

5. Находят дела bi к положительным aij разрешающего столбца. Малое из этих отношений определяет разрешающую строчку.

6. На скрещении разрешающих строчки и столбца определяют разрешающий элемент.

7. Все элементы разрешающей строчки делят на разрешающий элемент.

8. Все элементы разрешающего столбца (не считая разрешающего элемента Симплексный метод решения задач ЛП.) подменяют нулями.

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

10. Перебегают к пт 3.

Правило прямоугольника

a1 A2 p. строчка
a3 А4
p. столбец

Пример. Решить задачку ЛП:

1. Представим Симплексный метод решения задач ЛП. задачку в каноническом виде:

Найдем опорный план X=(0,0,0,360,192,180). Т.о. базовые переменные x4, x5, x6; свободные – x1, x2, x3.

2. Составим начальную симплекс-таблицу:

I Базис Сб P0 bi/aij
P1 P2 P3 P4 P5 P6
P4 360/12=30
P5 192/8=24 p.стр
P6 180/3=60
-9 –10 –16
p.ст.

Δ1= 0·18 + 0·6 + 0·5 – 9 = – 9

Δ2= 0·15 + 0·4 + 0·3 – 10 = – 10

Δ3= 0·12 + 0·8 + 0·3 – 16 = – 16

Δ4= 0·1 + 0·0 + 0·0 – 0 = 0

Δ5= 0·0 + 0·1 + 0·0 – 0 = 0

Δ6= 0·0 + 0·0 + 0·1 – 0 = 0


3. Отысканный опорный план X=(0,0,0,360,192,180) не оптимален Симплексный метод решения задач ЛП., т.к. Δ1, Δ2, Δ3 – отрицательны.

4. – разрешающий столбец

5. – разрешающая строчка

6. а23 = 8 – разрешающий элемент.

7, 8, 9, 10 Строим новейшую симплекс-таблицу по приведенному выше методу, вводя в базис P3 заместо P5.

I Базис Сб P0 bi/aij
P1 P2 P3 P4 P5 P6
P4 –3/2 72/9=8 p.стр
P3 6/8 1/2 1/8 24 :1/2 = 48
P6 11/4 3/2 –3/8 108 : 3/2=72
–2
p.ст.

Приобретенный опорный план X=(0,0,24,72,0,108) так же не оптимален Симплексный метод решения задач ЛП., т.к. Δ2= – 2 < 0. Потому по методу симплекс-метода перебегаем к новенькому опорному плану, вводя в базис P2 заместо P4.

i Базис Сб P0 bi/aij
P1 P2 P3 P4 P5 P6
P2 1/9 –1/6
P3 1/4 –1/8 5/24
P6 5/4 –1/6 –1/8
2/9 5/3

Этот опорный план X*=(0; 8; 20; 0; 0; 96) оптимален, т.к. все Δj неотрицательны.

Наибольшее значение функции на Симплексный метод решения задач ЛП. рациональном решении равно:

Fmax = 0·9 + 8·10 + 20·16 + 0·0 + 0·0 + 0·96 = 400

Решение общей задачки ЛП: x1*= 0; x2* = 8; x3* = 20; Fmax= 400.

Личные задания. Решить задачку ЛП симплексным способом. Варианты заданий взять из личных заданий пт 1.1.

1.3. Способ искусственного базиса.

В общем случае после приведения задачки ЛП к каноническому виду конкретно записать опорный план не удается, т.к. посреди векторов Pj Симплексный метод решения задач ЛП. . нет m единичных. В данном случае задачка ЛП решается способом искусственного базиса.

Постановка задачки. Требуется отыскать максимум функции

(1.10)

При критериях

(1.11)

m

но посреди векторов Pj нет m единичных.

Определение. Задачка, состоящая в определении максимума функции

(1.12)

при критериях

(1.13)

именуется расширенной по отношению к начальной задачке (1.10), (1.11).

Тут M некие огромные положительные числа, значения которых не задаются Симплексный метод решения задач ЛП..

Расширенная задачка (1.12), (1.13) имеет опорный план:

Переменные xn+1, xn+2 … xn+m именуются искусственными, а система единичных векторов Pn+1, Pn+2 … Pn+m образует искусственный базис.

Если в рациональном плане расширенной задачки (1.12), (1.13) значения искусственных переменных равны нулю, то – есть лучший план начальной задачки (1.10), (1.11).

Потому процесс решения задачки ЛП (1.10), (1.11) включает последующие этапы:

1. Для Симплексный метод решения задач ЛП. начальной задачки составляют расширенную задачку вида (1.12), (1.13).

2. Находят опорный план расширенной задачки.

3. При помощи вычислений симплекс-метода исключают искусственные вектора из базиса. В итоге находят опорный план начальной задачки. Если искусственные переменные исключить из базиса не удается, то задачка ЛП неразрешима.

4. Используя отысканный опорный план начальной задачки (1.10), (1.11), или Симплексный метод решения задач ЛП. находят симплекс-методом ее лучший план, или устанавливают ее неразрешимость

Пример. Отыскать минимум функции

при критериях:

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

Для образования базиса нужно три единичных вектора, т.к. m = 3. Но посреди векторов Pj :

есть только два единичных – P4 и P5. Потому составим расширенную задачку, введя искусственную переменную Симплексный метод решения задач ЛП. x7 в мотивированную функцию и в третье ограничение:

Расширенная задачка имеет опорный план X=(0;0;0;24;22;0;10), определяемый базисом P4, P5, P7.

Составим начальную таблицу:

i Базис Сб P0 –3 -M bi/aij
P1 P2 P3 P4 P5 P6 P7
P4 –2
P5 22/4
P7 –M –1 –1 10/2 p.стр.
–8
–10 –1 –2
р.ст.

F=1·24+0·22+(–M) ·10 = 24 – 10M

Δ1= 2·1 + 1·0 + 1·(–M) – 2 = 0 – M

Δ2= 1·1 + 2·0 + 2(–M)–(–3) =4 + M

Δ3= (–2)·1 + 4·0 + 2(–M)–6=–8–2M

Δ4= 1·1 + 0·0 + 0·(–M) – 1 = 0

Δ5= 0·1 + 0·0 + 0·(–M) – 0 = 0

Δ6= 0·1 + 0·0 + (–1)·(–M Симплексный метод решения задач ЛП.) – 0=M

Δ7= 0·1 + 0·0 + 1·(–M) – (–M)=0


При всем этом в (m+2)-й строке записываем коэффициенты при М. Сначала проверяем условие для последней (пятой) строчки. Тут есть отрицательные числа: и .

Перебегаем к новенькому опорному плану по методу симплекс-метода. Для этого исключим вектор P7 из базиса, а вектор P3 введем заместо Симплексный метод решения задач ЛП. него. В предстоящем искусственный вектор P7 не имеет смысла вводить в базис, потому столбец P7 исключаем из таблицы.

Потому что все искусственные векторы исключены из базиса то нет смысла включать в таблицу и (m+2)-ю (пятую для нашей задачки) строчку.

Потому новенькая таблица имеет четыре строчки и 6 столбцов:

I Симплексный метод решения задач ЛП. Базис Сб P0 –3 bi/aij
P1 P2 P3 P4 P5 P6
P4 –1
P5 –1 2/2 p.стр.
P3 1/2 –1/2 –1/2
-4
р.ст.

Приобретенное опорное решение Х=(0;0;5;34;2;0) не является хорошим; т.к. Δ6<0.

Далее итерационный процесс ведется по (m+1)-й строке до получения рационального решения либо установления неразрешимости задачки.

Вводим в базис P6 заместо P5 и Симплексный метод решения задач ЛП. перебегаем к новейшей таблице:

I Базис Сб P0 –3 bi/aij
P1 P2 P3 P4 P5 P6
P4 5/2 1/2
P6 –1/2 1/2
P3 11/2 ¼ 1/2 1/4

Т.к. все , то приобретенный опорный план – лучший. .

Личные задания. Решить задачку ЛП способом искусственного базиса. Варианты заданий взять из личных заданий пт 1.1.


simbat.html
simbioz-v-mire-zhivotnih-referat.html
simbirskie-izvestiya-zakon-nuzhdaetsya-v-reklame-12.html