Вернуться к оглавлению
Экстримальные задачи непрерывного типа.
Устловие:
Считая, что все переменные являются положительными величинами, найти оптимальное решение симплекс-методом линейного
программирования приведенных ниже задач (предполагается, что все переменные не отрицательны).
Задание.
L(x)=x1+3x2-55x4
2x1+4x2+x3+224=308
-3x1+5x2-33x4+x5=330
4x1-2x2+88x4+x6=352
Решение.
1. Нахождение минимума функции L(X):
L(x)=x1+3x2-55x4->min
Ограничения:
2x1+4x2+x3+224=308 // X3 – базисная переменная
-3x1+5x2-33x4+x5=330 // X5 – базисная переменная
4x1-2x2+88x4+x6=352 // X6 – базисная переменная
При xi, i=1,2,3,4,5,6
Соответственно базис:
Хб=(0,0,308,0,330,352)Т
Решаем задачу поиска минимума функции L(X):
Таблица1.
| Xj0 |
B |
C |
| x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
| 1 |
3 |
0 |
-55 |
0 |
0 |
|
Bi/aij
|
| x3 |
308 |
0 |
2 |
4 |
1 |
22 |
0 |
0 |
14 |
| x5 |
330 |
0 |
-3 |
5 |
0 |
-33 |
1 |
0 |
|
| x6 |
352 |
0 |
4 |
-2 |
0 |
88 |
0 |
1 |
4 |
| L= 0 |
Dj |
-1 |
-3 |
0 |
55 |
0 |
0 |
|
Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
min(Bi/aij)={14,4}=4
3-я строка * 3/8 + 2-я строка и записываем во вторую строку.
3-я строка *(-1/4) + 1-я строка и записываем в первую строку.
3-ю строку делим на 88.
Получаем новую таблицу:
Таблица2.
| Xj0 |
B |
C |
| x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
| 1 |
3 |
0 |
-55 |
0 |
0 |
|
Bi/aij
|
| x3 |
220 |
0 |
1 |
9/2 |
1 |
0 |
0 |
-1/4 |
|
| x5 |
462 |
0 |
-3/2 |
17/4 |
0 |
0 |
1 |
3/8 |
|
| x4 |
4 |
-55 |
1/22 |
-1/44 |
0 |
1 |
0 |
1/88 |
|
| L= -220 |
Dj |
-7/2 |
-7/4 |
0 |
0 |
0 |
-5/8 |
|
Все маргиналы меньше или равны нулю. Оптимизация прошла успешно.
Lmin= -220
X=(0,0,220,4,462,0)T
2. Нахождение максимума функции L(X):
L(x)=x1+3x2-55x4->max
Или: L(x)=-x1-3x2+55x4->min
при Хб=(0,0,308,0,330,352)Т
Составим таблицу:
Таблица3.
| Xj0 |
B |
C |
| x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
| -1 |
-3 |
0 |
55 |
0 |
0 |
|
Bi/aij
|
| x3 |
308 |
0 |
2 |
4 |
1 |
22 |
0 |
0 |
77 |
| x5 |
330 |
0 |
-3 |
5 |
0 |
-33 |
1 |
0 |
66 |
| x6 |
352 |
0 |
4 |
-2 |
0 |
88 |
0 |
1 |
|
| L= 0 |
Dj |
1 |
3 |
0 |
-55 |
0 |
0 |
|
Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
min(Bi/aij)={66,77}=66
Сделаем стобец x2 базисом.
2-я строка * (-4/5) + 1-я строка и записываем в первую строку.
2-я строка * 2/5 + 3-я строка и записываем в третью строку.
2-ю строку делим на 5.
Таблица4.
| Xj0 |
B |
C |
| x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
| -1 |
-3 |
0 |
55 |
0 |
0 |
|
Bi/aij
|
| x3 |
44 |
0 |
22/5 |
0 |
1 |
242/5 |
-4/5 |
0 |
10 |
| x2 |
66 |
-3 |
-3/5 |
1 |
0 |
-33/5 |
1/5 |
0 |
|
| x6 |
484 |
0 |
14/5 |
0 |
0 |
374/5 |
2/5 |
1 |
1270/7 |
| L= -198 |
Dj |
14/5 |
0 |
0 |
-176/5 |
-3/5 |
0 |
|
Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
min(Bi/aij)={10,1210/7}=10
1-я строка * 3/22 + 2-я строка и записываем во вторую строку.
1-я строка * (-7/11) + 3-я строка и записываем в третью строку.
1-ю строку умножаем на 5/22.
Таблица5.
| Xj0 |
B |
C |
| x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
| -1 |
-3 |
0 |
55 |
0 |
0 |
|
Bi/aij
|
| x1 |
10 |
-1 |
1 |
0 |
5/22 |
11 |
-2/11 |
0 |
|
| x2 |
72 |
-3 |
0 |
1 |
3/22 |
0 |
1/11 |
0 |
|
| x6 |
456 |
0 |
0 |
0 |
-7/11 |
44 |
10/11 |
1 |
|
| L= -226 |
Dj |
0 |
0 |
-7/11 |
-66 |
-1/11 |
0 |
|
Все маргиналы меньше или равны нулю.
Оптимизация успешно завершена.
Найдено оптимальное решение:
X*=(10,72,0,0,0,456)T
Lmin=-226; Lmax=-Lmin=226.
|
