Выполнение
Составим систему уравнений в стандартной форме записи задачи ЛП, преобразовав все неравенства в равенства с неотрицательной правой частью.
x1+S1=500
x2+S2=700;
12*x1+8*x2+S3=7500.
Запишем функцию Z: Z = 60*x1+35*x2+0*S1+0*S2+0*S3
Обозначения:
|
- Решение |
|
|
|
- Ведущая строка |
|
|
|
- Ведущий столбец |
|
|
|
- Ведущий элемент |
Составим симплекс-таблицу согласно условиям:
с |
z |
x1 |
x2 |
s1 |
s2 |
s3 |
решение |
z |
1 |
-60 |
-35 |
0 |
0 |
0 |
0 |
s1 |
0 |
12 |
8 |
1 |
0 |
0 |
7500 |
s2 |
0 |
1 |
0 |
0 |
1 |
0 |
500 |
s3 |
0 |
1 |
0 |
0 |
0 |
1 |
700 |
Как видно x1 – ведущий столбец, а S2- ведущая строка. Внесем x1 в базис и выполним вычисления согласно симплекс-методу.
с |
z |
x1 |
x2 |
s1 |
s2 |
s3 |
решение |
z |
1 |
0 |
-35 |
0 |
60 |
0 |
30000 |
x1 |
0 |
1 |
0 |
0 |
1 |
0 |
500 |
s1 |
0 |
0 |
8 |
1 |
-12 |
0 |
1500 |
s3 |
0 |
0 |
0 |
0 |
-1 |
1 |
200 |
В полученной симплекс-таблице x2 – ведущий столбец, S1 примем за ведущую строку. Внесем x2 в базис и выполним вычисления согласно симплекс-методу.
с |
z |
x1 |
x2 |
s1 |
s2 |
s3 |
решение |
z |
1 |
0 |
0 |
4,375 |
7,5 |
0 |
36562,5 |
x2 |
0 |
0 |
1 |
0,125 |
-1,5 |
0 |
187,5 |
x1 |
0 |
1 |
0 |
0 |
1 |
0 |
500 |
s3 |
0 |
0 |
0 |
0 |
-1 |
1 |
200 |
Z – строка не имеет отрицательных коэффициентов, соответствующих небазисным переменным, можем прекратить вычисления, полученное решение оптимально.
Исходя из конечной таблицы, можем записать, что:
x1 = 500
x2 = 187,5
Z = 36562,5
Учитывая что ограничение линии по производству двигателей не может быть дробным числом выполним округление:
x1 = 500
x2 = 187
Z = 36562
Симплекс-методом было найдено, что оптимальное ограничение линии по производству двигателей первого типа равняется 187 и второго 500. Максимальный доход при этом будет равен 36562 $.
Вывод
В ходе решения обязательного домашнего задания были получены решения данной задачи графическим и симплекс-методом, которые совпадают:
Графический метод:
,5
36562,5
Симплекс-метод:
x1 = 500
x2 = 187,5
Z = 36562,5