Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Стандартная форма записи задачи линейного программирования
|
|
1) Если в ограничении есть знак ≤, то мы прибавляем к левой части остаточную переменную
x 1 – 2 x 2 ≤ 5; x 1 – 2 x 2 + s 1 = 5; s 1 – остаточная переменная s 1 ≥ 0;
2 x 1 + 3 x 2 ≥ 10; 2 x 1 + 3 x 2 – s 2 = 10; s 2 – избыточная переменная s 2 ≥ 0.
2) max z = (– a) Û min (– z) = a.
Решение, полученное занулением n – m переменных называется базисным. Переменные не равные нулю называются базисными переменными, а равные нулю – небазисными.
шаг 0 начальное решение (xi = 0).
| базис | С | X опт | r | |||||
| x 1 | x 2 | s 1 | s 2 | s 3 | ||||
| s 1 | ||||||||
| s 2 | 30 | |||||||
| s 3 | ||||||||
| z | – 2 | – 3 |
z – строка оценок;
“С” ´ столб – (оценка в верхней строчке);
X опт = 0·120 + 0·300 + 0·600 – 0 = 0;
x 1: 0·2 + 0·3 + 0·8 – 2 = – 2 и т.д.
шаг 1
Если в строке нет отрицательных, то оптимальное решение получено. Столбец, в котором стоит наибольшая по модулю отрицательная оценка является разрешающим. Переменная этого столбца вводится в базис. x 2 – разрешающая; x 2 вводится в базис.
шаг 2
Находим отношение элементов столбца X опт к положительным элементам разрешающего столбца. Строка, в которой отношение наименьшее является разрешающей, соответствующая переменная выводится из базиса.
s 2 выводится из базиса, разрешающая.
На пересечении разрешающей строки и разрешающего столбца стоит главный элемент.
шаг 3
Пересчитываем коэффициенты таблицы с помощью преобразований Гаусса.
| базис | С | X опт | r | |||||
| x 1 | x 2 | s 1 | s 2 | s 3 | ||||
| s 1 | 
| 
| 
| |||||
| x 2 | 
| 
| ||||||
| s 3 | 
| 
| 
| |||||
| z | 
|
| ||||||
| s 1 | 
| |||||||
| x 2 |
| |||||||
| x 1 | 
| |||||||
| z | 
| 
| 
| |||||
| s 2 | 
| |||||||
| x 2 | 
| |||||||
| x 1 | 
| |||||||
| z | 
| 
| 
|
Особые случаи применения симплекс-метода
1. Вырождение решение
Одна из базисных переменных на некотором этапе равна 0. Графически это означает избыточное ограничение.
пример. max z = 3 x 1 + 9 x 2.
| Б | С | X опт | r | ||||
| x 1 | x 2 | s 1 | s 2 | ||||
| s 1 | 2; 
| ||||||
| s 2 | 2; 
| ||||||
| z | – 3 | – 9 | |||||
| s 1 | – 1 | – 2 | |||||
| x 2 | 
|
| |||||
| z | 
| 
|
x 2 = 2; s 1 = 0; x 1 = s 2 = 0; z = 18.
2. Альтернативное решение
пример. max z = 2 x 1 + 4 x 2.
АВ – множество решений
| Б | С | X опт | r | ||||
| x 1 | x 2 | s 1 | s 2 | ||||
| s 1 | 
| ||||||
| s 2 | |||||||
| z | – 2 | – 4 | |||||
| x 2 |
| 
|
| ||||
| s 2 | 
| 
| 
| ||||
| z | |||||||
| x 2 | – 1 | ||||||
| x 1 | – 1 | ||||||
| z |
Используем формулу: x = a ·α + b ·(1 – α); α Î [0; 1]
3. Неограниченное решение
пример. max z = 2 x 1 + x 2.
max z = ∞
| Б | С | X опт | r | ||||
| x 1 | x 2 | s 1 | s 2 | ||||
| s 1 | – 1 | ||||||
| s 2 | |||||||
| z | – 2 | – 1 |
Столбец x 2 не содержит положительных, значит сразу можно сделать вывод о неограниченности максимума.
max z = ∞