Решение задач симплекс-методом
ЗАДАНИЕ 1
Для приведенной ниже задачи составить
математическую модель, подставив данные своего варианта из таблицы 1. Решить
задачу симплекс методом и графически, показать соответствие опорных решений и
вершин допустимой области, проверить полученные значения на компьютере.
Сельскохозяйственное предприятие снабжает своей
продукцией перерабатывающие предприятия региона. Для производства двух видов
сельскохозяйственной продукции с пастбищ и сенокосов (П1, П2 ), требуется три
вида ресурсов Р1 , Р2 , Р3 , где Р1 - трудовые ресурсы, Р2 - минеральные
удобрения, Р3 - оросительная вода. При получении 1т продукции с пастбищ первый
ресурс используется tп1 чел- час, второй ресурс - tп2 кг,
третий ресурс -tп3 м 3 . При получении 1 т продукции с сенокосов
первый ресурс используется tс1 чел- час, второй ресурс - tс2
кг, третий ресурс - tс3 м3 . Запасы ресурсов ограничены и
не может превышать для первого вида продукции T1 чел-час, для второго - T2 кг,
для третьего - T3 м3 . При реализации 1 т продукции с пастбищ
предприятие получает прибыль С1 рублей, а при реализации 1 т продукции с
сенокосов - С2 рублей. Найти оптимальный план выпуска продукции каждого вида,
дающий максимальную прибыль от реализации всей продукции.
№
|
tп1
|
tп2
|
tп3
|
tс1
|
tс2
|
tс3
|
T1
|
T2
|
T3
|
С1
|
С2
|
3
|
5
|
3
|
1
|
3
|
2
|
0
|
259
|
162
|
39
|
18
|
11
|
Решение:
Обозначим за X1
- объем в тоннах продукции с пастбищ, за X2
- объем в тоннах продукции с сенокосов
Составим математическую модель
Ограничение на трудовые ресурсы:
x1+3x2≤259
Ограничение на минеральные удобрения
x1+2x2≤162
Ограничения на оросительную воду:
1≤39
При этом заметим, что объем продукции не должен
быть отрицательным
1,
x2≥0
Целевая функция будет иметь вид:
= 18x1+11x2 → max
Решим задачу графически:
Построим уравнение 5x1+3x2
= 259 по двум точкам.
1
= 0 =>x2 = 86.33.2 = 0 => x1 = 51.8.
Определим полуплоскость, задаваемую
неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:
5 • 0 + 3 • 0 - 259 ≤ 0, т.е. 5x1+3x2 - 259≤
0 в полуплоскости ниже прямой.
Построим уравнение 3x1+2x2
= 162 по двум точкам.
1
= 0 => x2 = 81.2 = 0 => x1 = 54.
Определим полуплоскость, задаваемую
неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:
3 • 0 + 2 • 0 - 162 ≤ 0, т.е. 3x1+2x2 - 162≤
0 в полуплоскости ниже прямой.
Построим уравнение x1 = 39.
Эта прямая проходит через точку x1 =
39 параллельно оси OX2. Выбрав точку (0; 0), определим знак неравенства в
полуплоскости: 1 • 0 - 39 ≤ 0, т.е. x1 - 39≤ 0 в
полуплоскости левее прямой.
Построим прямую, отвечающую значению функции F =
0: F = 18x1+11x2 = 0. Вектор-градиент, составленный из
коэффициентов целевой функции, указывает направление максимизации F(X). Начало
вектора - точка (0; 0), конец - точка (18; 11).
Прямая F(x) = const пересекает область в точке
C, полученная в результате пересечения прямых:
x1+3x2=259
x1+2x2=162
Решив систему уравнений, получим: x1
= 32, x2 = 33
Откуда найдем максимальное значение целевой
функции:(X) = 18*32 + 11*33 = 939
Решим задачу симплекс методом
переход к канонической форме
В 1-м неравенстве смысла (≤) вводим
базисную переменную x3. В 2-м неравенстве смысла (≤) вводим
базисную переменную x4. В 3-м неравенстве смысла (≤) вводим
базисную переменную x5.
x1 + 3x2 + 1x3
+ 0x4 + 0x5 = 259
x1 + 2x2 + 0x3
+ 1x4 + 0x5 = 162
x1 + 0x2 + 0x3
+ 0x4 + 1x5 = 39
Б
|
1
|
x1
|
x2
|
Q
|
x3
|
259
|
5
|
3
|
514/5
|
x4
|
162
|
3
|
2
|
54
|
x5
|
39
|
1
|
0
|
39
|
F
|
0
|
-18
|
-11
|
0
|
Данное решение X=(0;0)
соответствует точке A на графике
Б1x2x5Q
|
|
|
|
|
x3
|
64
|
3
|
-5
|
211/3
|
x4
|
45
|
2
|
-3
|
221/2
|
x1
|
39
|
0
|
1
|
-
|
F
|
702
|
-11
|
18
|
0
|
Данное решение X=(39;0)
соответствует точке D на графике
Б1x3x5Q
|
|
|
|
|
x2
|
211/3
|
1/3
|
-12/3
|
-
|
x4
|
21/3
|
-2/3
|
1/3
|
7
|
x1
|
39
|
0
|
1
|
39
|
F
|
9362/3
|
32/3
|
-1/3
|
0
|
Данное решение X=(39;
211/3) соответствует точке E
на графике
Б
|
1
|
x3
|
x4
|
Q
|
x2
|
33
|
-3
|
5
|
|
x5
|
7
|
-2
|
3
|
|
x1
|
32
|
2
|
-3
|
|
F
|
939
|
3
|
1
|
|
Данное решение X=(32;
33) соответствует точке C
на графике
При решении задачи на компьютере получаем
следующую модель:
Формулы имеют следующий вид:
Математическая модель
В результате получаем
ЗАДАНИЕ 2
Решить симплексным методом с искусственным
базисом каноническую задачу линейного программирования:
Z
= c1x1
+ c2x2
+ c3x3
+ c4x4
+ c5x5
→ max
При условиях:
Выполнить проверку оптимальности найденного
решения, используя теорию двойственности. Найти оптимальное решение
двойственной задачи.
Решение
(X) = 2x1 - 2x2
- 3x3 - 2x4 - 2x5 ->max
3x1 + 3x2 - x3
- x5≤131 + 3x2 - x4 - 3x5≤1
2x1 + x2 + x3 -
3x4 + x5≤8
переход к канонической форме
В 1-м неравенстве смысла (≤) вводим
базисную переменную x6. В 2-м неравенстве смысла (≤) вводим
базисную переменную x7. В 3-м неравенстве смысла (≤) вводим
базисную переменную x8.
x1 + 3x2-1x3 +
0x4-1x5 + 1x6 + 0x7 + 0x8
= 13
x1 + 3x2 + 0x3-1x4-3x5
+ 0x6 + 1x7 + 0x8 = 1
x1 + 1x2 + 1x3-3x4
+ 1x5 + 0x6 + 0x7 + 1x8 = 8
решение задача математический
симплексный
Б
|
1
|
x1
|
x2
|
x3
|
x4
|
x5
|
Q
|
x6
|
13
|
3
|
3
|
-1
|
0
|
-1
|
41/3
|
x7
|
1
|
1
|
3
|
0
|
-1
|
-3
|
1
|
x8
|
8
|
-2
|
1
|
1
|
-3
|
1
|
-
|
F
|
0
|
-2
|
2
|
3
|
2
|
2
|
0
|
Б1x2x3x4x5x7Q
|
|
|
|
|
|
|
|
x6
|
10
|
-6
|
-1
|
3
|
8
|
-3
|
11/4
|
x1
|
1
|
3
|
0
|
-1
|
-3
|
1
|
-
|
x8
|
10
|
7
|
1
|
-5
|
-5
|
2
|
-
|
F
|
2
|
8
|
3
|
0
|
-4
|
2
|
0
|
Б
|
1
|
x2
|
x3
|
x4
|
x6
|
x7
|
Q
|
x5
|
5/4
|
-3/4
|
-1/8
|
3/8
|
1/8
|
-3/8
|
|
x1
|
19/4
|
3/4
|
-3/8
|
1/8
|
3/8
|
-1/8
|
|
x8
|
65/4
|
13/4
|
3/8
|
-25/8
|
5/8
|
1/8
|
|
F
|
7
|
5
|
5/2
|
3/2
|
1/2
|
1/2
|
|
Оптимальный план можно записать так:
X =( 43/4;0;0;0;
11/4)(X) = -2•11/4 + 2•43/4
= 7
Составим двойственную задачу:
Исходная задача I
|
|
Двойственная задача II
|
2x1 - 2x2 - 3x3
- 2x4 - 2x5 → max
|
↔
|
13y1 + y2 + 8y3
→ min
|
3x1 + 3x2 - x3
- x5≤13
|
↔
|
y1 ≥ 0
|
x1 + 3x2 - x4
- 3x5≤1
|
↔
|
y2 ≥ 0
|
- 2x1 + x2 + x3
- 3x4 + x5≤8
|
↔
|
y3 ≥ 0
|
x1 ≥ 0
|
↔
|
3y1 + y2 - 2y3≥2
|
x2 ≥ 0
|
↔
|
3y1 + 3y2 + y3≥-2
|
x3 ≥ 0
|
↔
|
- y1 + y3≥-3
|
x4 ≥ 0
|
↔
|
- y2 - 3y3≥-2
|
x5 ≥ 0
|
↔
|
- y1 - 3y2 + y3≥-2
|
Подставим оптимальный план прямой задачи в
систему ограниченной математической модели:
*43/4 + 3*0 + (-1)*0 + 0*0
+ (-1)*11/4 = 13 = 13 => y1
≥ 0
*43/4 + 3*0 + 0*0 + (-1)*0
+ (-3)*11/4 = 1 = 1 => y2
≥ 0
*43/4 + 1*0 + 1*0 + (-3)*0
+ 1*11/4 = -81/4 < 8 => y3
= 0
x1
≥ 0=>3y1
+ y2
- 2y3=2
x5
≥ 0=>- y1
- 3y2
+ y3=-2
Получаем систему из двух уравнений:
Получаем, что1 = 1/22
= 1/23 = 0(Y) = 13*1/2+1*1/2+8*0
= 7
Так как Z(Y)=F(X),
значит полученный план является оптимальным
ЗАДАНИЕ 3
ai/bj
|
200
|
400
|
100
|
200
|
100
|
200
|
1
|
7
|
12
|
2
|
5
|
100
|
2
|
3
|
8
|
4
|
7
|
200
|
5
|
4
|
6
|
9
|
200
|
4
|
4
|
3
|
8
|
2
|
300
|
5
|
3
|
7
|
10
|
1
|
Решение:
Проверим необходимое и достаточное условие
разрешимости задачи.
∑a = 200 + 100 + 200 + 200 + 300 = 1000
∑b = 200 + 400 + 100 + 200 + 100 = 1000
Условие баланса соблюдается. Запасы равны
потребностям. Следовательно, модель транспортной задачи является закрытой.
Используя метод наименьшей стоимости, построим
первый опорный план транспортной задачи.
21
= min(100,200) = 100.11 = min(200,100) = 100.55 =
min(300,100) = 100.14 = min(100,200) = 100.43 =
min(200,100) = 100.52 = min(200,400) = 200.42 =
min(100,200) = 100.32 = min(200,100) = 100.34 =
min(100,100) = 100.
|
v1=1
|
v2=1
|
v3=0
|
v4=2
|
v5=-1
|
|
u1=0
|
1 100
[-]
|
7
|
12
|
2 100
[+]
|
5
|
200
|
u2=1
|
2 100
|
3
|
8
|
4
|
7
|
100
|
u3=4
|
3 [+]
|
5 100
|
4
|
6 100
[-]
|
9
|
200
|
u4=3
|
4
|
4 100
|
3 100
|
8
|
2
|
200
|
u5=2
|
5
|
3 200
|
7
|
10
|
1 100
|
300
|
|
200
|
400
|
100
|
200
|
100
|
|
+ n - 1 = 9.
Следовательно, опорный план является
невырожденным.
Значение целевой функции для этого опорного
плана равно:(x) = 1*100 + 2*100 + 2*100 + 5*100 + 6*100 + 4*100 + 3*100 + 3*200
+ 1*100 = 3000
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы ui, vj. по занятым клеткам
таблицы, в которых ui + vj = cij, полагая, что
u1 = 0.
1
+ v1 = 1; 0 + v1 = 1; v1 = 12 + v1
= 2; 1 + u2 = 2; u2 = 11 + v4 = 2;
0 + v4 = 2; v4 = 23 + v4 = 6; 2 + u3
= 6; u3 = 43 + v2 = 5; 4 + v2 = 5;
v2 = 14 + v2 = 4; 1 + u4 = 4; u4
= 34 + v3 = 3; 3 + v3 = 3; v3 = 05
+ v2 = 3; 1 + u5 = 3; u5 = 25 + v5
= 1; 2 + v5 = 1; v5 = -1
Опорный план не является оптимальным, так как
существуют оценки свободных клеток, для которых ui + vj
> cij
(3;1): 4 + 1 > 3; ∆31 = 4 +
1 - 3 = 2
Выбираем максимальную оценку свободной клетки
(3;1): 3
Цикл приведен в таблице (3,1 → 3,4 →
1,4 → 1,1).
|
v1=-1
|
v2=1
|
v3=0
|
v4=2
|
v5=-1
|
|
u1=0
|
1
|
7
|
12
|
2 200
|
5
|
200
|
u2=3
|
2 100
[-]
|
3 [+]
|
8
|
4
|
7
|
100
|
u3=4
|
3 100
[+]
|
5 100
[-]
|
4
|
6 0
|
9
|
200
|
u4=3
|
4
|
4 100
|
3 100
|
8
|
2
|
200
|
u5=2
|
5
|
3 200
|
7
|
10
|
1 100
|
300
|
|
200
|
400
|
100
|
200
|
100
|
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы ui, vj. по занятым клеткам
таблицы, в которых ui + vj = cij, полагая, что
u1 = 0.
1
+ v4 = 2; 0 + v4 = 2; v4 = 23 + v4
= 6; 2 + u3 = 6; u3 = 43 + v1 = 3;
4 + v1 = 3; v1 = -12 + v1 = 2; -1 +
u2 = 2; u2 = 33 + v2 = 5; 4 + v2
= 5; v2 = 14 + v2 = 4; 1 + u4 = 4;
u4 = 34 + v3 = 3; 3 + v3 = 3; v3
= 05 + v2 = 3; 1 + u5 = 3; u5 = 25
+ v5 = 1; 2 + v5 = 1; v5 = -1
Опорный план не является оптимальным, так как
существуют оценки свободных клеток, для которых ui + vj
> cij
(2;2): 3 + 1 > 3; ∆22 = 3 +
1 - 3 = 1
(2;4): 3 + 2 > 4; ∆24 = 3 +
2 - 4 = 1(1,1) = 1
Выбираем максимальную оценку свободной клетки
(2;2): 3
Цикл приведен в таблице (2,2 → 2,1 →
3,1 → 3,2).
|
v1=-1
|
v2=1
|
v3=0
|
v4=2
|
v5=-1
|
|
u1=0
|
1
|
7
|
12
|
2 200
|
5
|
200
|
u2=2
|
2
|
3 100
|
8
|
4
|
7
|
100
|
u3=4
|
3 200
|
5 0
|
4
|
6 0
|
9
|
200
|
u4=3
|
4
|
4 100
|
3 100
|
8
|
2
|
200
|
u5=2
|
5
|
3 200
|
7
|
10
|
1 100
|
300
|
|
200
|
400
|
100
|
200
|
100
|
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы ui, vj. по занятым клеткам
таблицы, в которых ui + vj = cij, полагая, что
u1 = 0.
1
+ v4 = 2; 0 + v4 = 2; v4 = 23 + v4
= 6; 2 + u3 = 6; u3 = 43 + v1 = 3;
4 + v1 = 3; v1 = -13 + v2 = 5; 4 +
v2 = 5; v2 = 12 + v2 = 3; 1 + u2
= 3; u2 = 24 + v2 = 4; 1 + u4 = 4;
u4 = 34 + v3 = 3; 3 + v3 = 3; v3
= 05 + v2 = 3; 1 + u5 = 3; u5 = 25
+ v5 = 1; 2 + v5 = 1; v5 = -1
Опорный план является оптимальным, так все
оценки свободных клеток удовлетворяют условию ui + vj ≤
cij.
Минимальные затраты составят: F(x) = 2*200 +
3*100 + 3*200 + 4*100 + 3*100 + 3*200 + 1*100 = 2700