Задачи линейного программирования 2 (стр. 2 из 5)
5x1 + 2x2 ≥ 20
x1 + 3x2 ≤ 15
x1, x2 ≥ 0
Вариант 19.
F = x1 + 3x2 
max
x1 + x2 ≥ 3
6x1 + x2 ≤ 42
2x1 – 3x2 ≥ 6
x1, x2 ≥ 0
Вариант 20.
F = x1 – 2x2 max
5x1 – 2x2 ≤ 3
x1 + x2 ≥ 1
–3x1 + x2 ≤ 3
x1, x2 ≥ 0
Вариант 21.
F = 8x1 + 2x2 max
x1 – 4x2 ≤ 4
–4x1 + x2 ≤ 4
x1 + x2 ≤ 6
x1, x2 ≥ 0
Вариант 22.
F = 2x1 + 3x2 min
x1 + 5x2 ≥ 16
3x1 + 2x2 ≥ 12
2x1 + 4x2 ≥ 16
x1 ≥ 1
x1, x2 ≥ 0
Вариант 23.
F = 3x1 + 3x2 max
x1 + x2 ≤ 4
3x1 + x2 ≥ 4
x1 + 5x2 ≥ 4
0 ≤ x1 ≤ 3
0 ≤ x2 ≤ 3
Вариант 24.
F = 7x1 – 2x2 max
x1 + x2 ≤ 5
2x1 – 3x2 ≤ 6
3x1 + x2 ≥ –3
x1, x2 ≥ 0
Вариант 25.
F = –7x1 + 2x2 min
x1 + x2 ≥ 1
5x1 + x2 ≥ 3
–3x1 + x2 ≤ 3
2x1 + x2 ≤ 4
x1, x2 ≥ 0
Вариант 26.
F = 2x1 – x2 max
3x1 + x2 ≥ 16
x1 + 2x2 ≤ 12
x1, x2 ≥ 0
Вариант 27.
F = 6x1 + 4x2 min
2x1 + x2 ≥ 3
x1 – 2x2 ≤ 2
3x1 + 2x2 ≥ 1
x1, x2 ≥ 0
Вариант 28.
F = –x1 – 2x2 min
5x1 – 2x2 ≤ 4
–x1 + 2x2 ≤ 4
x1 + x2 ≥ 4
x1, x2 ≥ 0
Вариант 29.
F = x1 + 2x2 min
5x1 – 2x2 ≤ 20
x1 – 2x2 ≥ –20
x1 + x2 ≥ 16
x1, x2 ≥ 0
Вариант 30.
F = x1 + x2 max
2x1 + x2 ≤ 18
x1 + 2x2 ≤ 16
x1, x2 ≥ 0
1.2. Симплексный метод решения задач ЛП.
Прежде чем решать задачу ЛП симплекс-методом ее необходимо привести к каноническому виду :
(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) элементов опорного плана равны нулю. Алгоритм симплекс-метода предполагает переход от одного опорного плана к другому с увеличением при этом значения целевой функции.
В некоторых случаях исходный опорный план можно легко определить. Это происходит тогда, когда среди векторов Pj
имеется m единичных. В этом случае соответствующие единичным векторам переменные в опорном плане будут отличны от нуля. Они называются базисными. Остальные переменные равны нулю; они называются свободными.Симплекс-преобразования продолжаются до тех пор, пока среди чисел
не будет отрицательных.Исходная симплекс-таблица в общем случае имеет вид
| i | Базис | Сб | P0 | C1 | C2 | … | Cm | Cm+1 | … | Cn |
| P1 | P2 | … | Pm | Pm+1 | … | Pn | ||||
| 1 | P1 | C1 | b1 | 1 | 0 | … | 0 | a1m+1 | … | a1n |
| 2 | P1 | C2 | b2 | 0 | 1 | … | 0 | a2m+1 | … | a2n |
| … | … | … | … | … | … | … | … | … | … | … |
| m | Pm | Cm | bm | 0 | 0 | … | 1 | amm+1 | … | amn |
| M+1 | F0 | 0 | 0 | … | 0 | Δm+1 | … | Δn |
В столбце Сб записываются коэффициенты целевой функции с теми же индексами, что и векторы базиса.
В столбце Р0 записываются положительные компоненты исходного опорного плана, в нем же в результате вычислений получают положительные компоненты оптимального плана. В столбцах Р1…Рn записаны коэффициенты ограничений при неизвестных.