Симплекс метод

Автор: Пользователь скрыл имя, 02 Мая 2012 в 22:11, контрольная работа

Описание работы

Задание 1
Для выпуска двух видов продукции требуются затраты сырья, рабочего времени и оборудования. Исходные данные в таблице:
Найдите оптимальный план выпуска продукции по критерию «максимум прибыли».
Определите остатки каждого вида сырья.
1) Составьте математическую модель задачи.
2) Решите задачу симплекс-методом.
3) Решите задачу графическим методом. Покажите соответствие опорных решений, полученных при решении симплекс-методом, и угловых точек – вершин допустимой области.
4) Найдите решение двойственной задачи, используя теоремы двойственности.

Работа содержит 1 файл

Вариант 2.doc

— 344.00 Кб (Скачать)

Разрешающий  элемент в ячейке (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

 

Информация о работе Симплекс метод