MATMEDECONOM (1)
.rtf
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 4x1 + 5x2 при следующих условиях-ограничений.
- x1 + 2x2≤10
3x1 + 5x2≤47
4x1 - 3x2≤24
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
-1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 10
3x1 + 5x2 + 0x3 + 1x4 + 0x5 = 47
4x1-3x2 + 0x3 + 0x4 + 1x5 = 24
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,10,47,24)
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
10 |
-1 |
2 |
1 |
0 |
0 |
x4 |
47 |
3 |
5 |
0 |
1 |
0 |
x5 |
24 |
4 |
-3 |
0 |
0 |
1 |
F(X0) |
0 |
-4 |
-5 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (10 : 2 , 47 : 5 , - ) = 5
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
x3 |
10 |
-1 |
2 |
1 |
0 |
0 |
5 |
x4 |
47 |
3 |
5 |
0 |
1 |
0 |
92/5 |
x5 |
24 |
4 |
-3 |
0 |
0 |
1 |
- |
F(X1) |
0 |
-4 |
-5 |
0 |
0 |
0 |
0 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x2 |
5 |
-1/2 |
1 |
1/2 |
0 |
0 |
x4 |
22 |
51/2 |
0 |
-21/2 |
1 |
0 |
x5 |
39 |
21/2 |
0 |
11/2 |
0 |
1 |
F(X1) |
25 |
-61/2 |
0 |
21/2 |
0 |
0 |
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (- , 22 : 51/2 , 39 : 21/2 ) = 4
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (51/2) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
x2 |
5 |
-1/2 |
1 |
1/2 |
0 |
0 |
- |
x4 |
22 |
51/2 |
0 |
-21/2 |
1 |
0 |
4 |
x5 |
39 |
21/2 |
0 |
11/2 |
0 |
1 |
153/5 |
F(X2) |
25 |
-61/2 |
0 |
21/2 |
0 |
0 |
0 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x2 |
7 |
0 |
1 |
3/11 |
1/11 |
0 |
x1 |
4 |
1 |
0 |
-5/11 |
2/11 |
0 |
x5 |
29 |
0 |
0 |
27/11 |
-5/11 |
1 |
F(X2) |
51 |
0 |
0 |
-5/11 |
12/11 |
0 |
Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (7 : 3/11 , - , 29 : 27/11 ) = 11
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (27/11) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
x2 |
7 |
0 |
1 |
3/11 |
1/11 |
0 |
252/3 |
x1 |
4 |
1 |
0 |
-5/11 |
2/11 |
0 |
- |
x5 |
29 |
0 |
0 |
27/11 |
-5/11 |
1 |
11 |
F(X3) |
51 |
0 |
0 |
-5/11 |
12/11 |
0 |
0 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x2 |
4 |
0 |
1 |
0 |
4/29 |
-3/29 |
x1 |
9 |
1 |
0 |
0 |
3/29 |
5/29 |
x3 |
11 |
0 |
0 |
1 |
-5/29 |
11/29 |
F(X3) |
56 |
0 |
0 |
0 |
13/29 |
5/29 |
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x2 |
4 |
0 |
1 |
0 |
4/29 |
-3/29 |
x1 |
9 |
1 |
0 |
0 |
3/29 |
5/29 |
x3 |
11 |
0 |
0 |
1 |
-5/29 |
11/29 |
F(X4) |
56 |
0 |
0 |
0 |
13/29 |
5/29 |
Оптимальный план можно записать так:
x2 = 4
x1 = 9
x3 = 11
F(X) = 5•4 + 4•9 + 0•11 = 56
Решение было получено и оформлено с помощью сервиса:
Симплекс-метод
Вместе с этой задачей решают также:
Графический метод решения задач линейного программирования
Двойственный симплекс-метод
Двойственная задача линейного программирования
Метод Гомори
Транспортная задача