Автор: Пользователь скрыл имя, 02 Мая 2012 в 22:11, контрольная работа
Задание 1
Для выпуска двух видов продукции требуются затраты сырья, рабочего времени и оборудования. Исходные данные в таблице:
Найдите оптимальный план выпуска продукции по критерию «максимум прибыли».
Определите остатки каждого вида сырья.
1) Составьте математическую модель задачи.
2) Решите задачу симплекс-методом.
3) Решите задачу графическим методом. Покажите соответствие опорных решений, полученных при решении симплекс-методом, и угловых точек – вершин допустимой области.
4) Найдите решение двойственной задачи, используя теоремы двойственности.
Разрешающий элемент в ячейке (1;2) -2/3. Выводим из базиса переменную x2 и вводим х1.
| -1 | -1 | -1 |
| ||
Базис | С | План | X1 | X2 | X3 | Q |
X2 | -1 | 18,25 | 0 | 1 | -3/4 |
|
X1 | -1 | 33,5 | 1 | 0 | 1,5 |
|
F=-51,75 |
| ∆ | 0 | 0 | 3/4 |
|
Т.к. оценок ∆ нет отрицательных, то полученный план (25,75;18,5; 0) оптимальный, но не целочисленный.
L(x1,x2)= 33,5+18,25=51,75 (min).
Строим сечение методом Гомори:
x1+1 ½ x3=33 ½
x1+x3-25=1/2-1/2x3
½-1/2x3<=0
Сечение ½-1/2x3+x4=0 x4>=0
| -1 | -1 | -1 | 0 |
| ||
Базис | С | План | X1 | X2 | X3 | X4 | Q |
X2 | -1 | 18,25 | 0 | 1 | -3/4 | 0 |
|
X1 | -1 | 33,5 | 1 | 0 | 3/2 | 0 |
|
X4 | 0 | -1/2 | 0 | 0 | -1/2 | 1 |
|
F=-51,75 |
| ∆ | 0 | 0 | 1/4 | 0 |
|
Разрешающий элемент в ячейке (3;3) -1/2. Выводим из базиса переменную x4 и вводим х3.
| -1 | -1 | -1 | 0 |
| ||
Базис | С | План | X1 | X2 | X3 | X4 | Q |
X2 | -1 | 19 | 0 | 1 | 0 | -3/2 |
|
X1 | -1 | 32 | 1 | 0 | 0 | 3 |
|
X3 | -1 | 1 | 0 | 0 | 1 | -2 |
|
F=-52 |
|
| 0 | 0 | 0 | 0,5 |
|
Т.к. оценок ∆ нет отрицательных, то полученный план (32; 19; 1) оптимальный, целочисленный L=52.
Задание 4
Предприятие может выпускать три вида продукции А1, А2, А3, получая прибыль, зависящую от спроса на эту продукцию. Спрос, в свою очередь, может принимать одно из четырех состояний В1, В2, В3, В4. В матрице элементы аij характеризуют прибыль, которую получает предприятие при выпуске продукции Аi и состоянии спроса Вj:
Определите оптимальные пропорции выпускаемой продукции, считая состояние спроса полностью неопределенным, гарантируя при этом среднюю величину прибыли при любом состоянии спроса.
Указание.
1) Представьте задачу как матричную игру двух лиц (предприятие - спрос) с нулевой суммой, исключив заведомо невыгодные стратегии игроков.
2) Найдите оптимальные стратегии и цену игры сведением игры к паре симметричных двойственных задач линейного программирования.
3) Определите оптимальные пропорции в выпускаемой продукции.
Решение
Если сравнить элементы второй и первой строки, то можно заметить, что все элементы первой строки не превышают соответствующих элементов второй строки. Значит первая стратегия для нас, желающих выиграть, заведомо невыгодна. Вычеркивая первую строку, приведем матрицу к более простому виду.
Если сравнить элементы первого и второго столбца, то можно заметить, что все элементы первого столбца не превышают элементов второго. Вычеркиваем второй столбец.
Находим цену игры V
V=minmax=7 =maxmin=6
, значит седловой точки нет, решение будем искать в смешанных стратегиях.
Составим систему
8q1+6q2+7q3<=1
q1+7q2+2q3<=1
q1, q2 ,q3>=0
F=q1+q2+q3 (max)
Приведем к канонической форме:
8q1+6q2+7q3+q4=1
q1+7q2+2q3+q5=1
q1, q2 ,q3,q4,q5>=0
F=q1+q2+q3 (max)
| 1 | 1 | 1 | 0 | 0 |
| ||
Базис | С | План | q1 | q2 | q3 | q4 | q5 | Q |
q4 | 0 | 1 | 8 | 6 | 7 | 1 | 0 | 1/8 |
q5 | 0 | 1 | 1 | 7 | 2 | 0 | 1 | 1 |
F=0 |
| ∆ | -1 | -1 | -1 | 0 | 0 |
|
Т.к. среди оценок ∆ есть отрицательные, то исходный опорный план не оптимальный.
Разрешающий элемент в ячейке (1;1) равен 8. Выводим из базиса переменную q4 и вводим q1.
| 1 | 1 | 1 | 0 | 0 |
| ||
Базис | С | План | q1 | q2 | q3 | q4 | q5 | Q |
q1 | 1 | 0,125 | 1 | 0,75 | 0,875 | 0,125 | 0 | 0,167 |
q5 | 0 | 0,875 | 0 | 6,25 | 1,125 | -0,125 | 1 | 0,14 |
F=0,125 |
| ∆ | 0 | -0,25 | -0,125 | 0,125 | 0 |
|