СКАЧАТЬ РАБОТУ БЕСПЛАТНО -
Рисунок 1. Область допустимых значений с вершинами ОАВСD.
Найдем координаты вершин ОАВСD области допустимых значений.
Координаты точек А(0;2) и D(2;0) уже известны. Найдем координаты точки В:
=-8, =-16, =-24.
=2, =3.
Найдем координаты точки С:
=12, =36, =18
=3, =1,5.
Найдем значение целевой функции в угловых точках области допустимых решений:
Координата
Координата
Прибыль
Точка О 0 0 0
Точка А 0 2 4
Точка B 2 3 8
Точка С 3,0 1,5 6,0
Точка D 2 0 2
Ответ: минимальное значение целевой функции достигается при =0, =0 и равно minF=0.
№2. Проверить симплекс-методом результат решения задачи, полученного геометрическим методом: Кирпичный завод выпускает кирпичи двух марок I и II. Для производства кирпича используется глина трех видов А, В и С. По месячному плану завод должен выпустить 10 условных единиц марки I и 15 усл. ед. марки II. В таблице указаны расход различных видов глины для производств 1 усл. ед. кирпича каждой марки и месячный запас глины. Какова наибольшая прибыль, если известно, что от реализации 1 усл. ед. кирпича марки I завод получает прибыль 4 ден. ед., а марки II – 7 ден. ед.
Марки кирпича Количество глины для производств 1 усл. ед. кирпича
А В С
I 1 0 1
II 0 2 2
Запас глины, усл. ед. 15 36 47
Решение:
Пусть предприятие будет производить условных единиц кирпича марки I, усл. ед. – кирпича марки II. Тогда задача примет вид:
Тогда максимальная прибыль будет вычисляться по функции
Система ограничений по запасам сырья имеет вид: ,
все переменные не отрицательны , .
1. Решим исходную задачу геометрическим методом.
Построим область ограничений:
15 0
15 20
0 18
20 18
0 23,5
47 0
Линии уровней целевой функции:
0 7,1
12,5 0
0 14,3
25,0 0
График:
Рисунок 1. Область допустимых значений с вершинами ОАВСD.
Найдем координаты вершин ОАВСD области допустимых значений.
Координаты точек А(0;18) и D(15;0) уже известны. Найдем координаты точки В:
=11, =18.
Найдем координаты точки С:
=15, =16.
Найдем значение целевой функции в угловых точках области допустимых решений:
Координата
Координата
Прибыль
Точка А 0 18 126
Точка B 11 18 170
Точка С 15 16 172
Точка D 15 0 60
Ответ: максимальная прибыль достигается при =15, =16 и равна maxF=172.
2.Решим задачу симплекс методом:
Приведем систему ограничений к каноническому виду: .
Расширенная целевая функция
Составим первую симплекс - таблицу:
Base X0 X1 X2 X3 X4 X5 отношения
X3 15 1 0 1 0 0 -
X4 36 0 2 0 1 0 18
X5 47 1 2 0 0 1 23 1/2
F max = 0 -4 -7 0 0 0
В качестве ключевого столбца выбираем с максимальной отрицательной оценкой целевой функции (это Х2).
В качестве ключевой строки выбираем строку с минимальным отношением (это Х4).
Рассчитываем новую симплекс таблицу:
Base X0 X1 X2 X3 X4 X5 отношения
X3 15 1 0 1 0 0 15
X2 18 0 1 0 1/2 0 -
X5 11 1 0 0 -1 1 11
F max = 126 -4 0 0 3 1/2 0
В качестве ключевого столбца выбираем с отрицательной оценкой целевой функции (это Х1).
В качестве ключевой строки выбираем строку с минимальным отношением (это Х5).
Рассчитываем новую симплекс таблицу:
Base X0 X1 X2 X3 X4 X5 отношения
X3 4 0 0 1 1 -1 4
X2 18 0 1 0 1/2 0 36
X1 11 1 0 0 -1 1 -11
F max = 170 0 0 0 - 1/2 4
В качестве ключевого столбца выбираем с отрицательной оценкой целевой функции (это Х4).
В качестве ключевой строки выбираем строку с минимальным отношением (это Х3).
Рассчитываем новую симплекс таблицу:
Base X0 X1 X2 X3 X4 X5
X4 4 0 0 1 1 -1
X2 16 0 1 - 1/2 0 1/2
X1 15 1 0 1 0 0
F max = 172 0 0 1/2 0 3 1/2
Так как в строке целевой функции нет отрицательных оценок, то получен оптимальный план.
Ответ: максимальная прибыль достигается при =15, =16 и равна maxF=172.
3. Ответы, полученные геометрическим методом и симплекс-методом, совпадают.
| 
