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

Т.к. среди оценок ∆ есть отрицательные, то полученный опорный план не оптимальный. Разрешающий  элемент в ячейке (2;2) равен 6,25. Выводим из базиса переменную q5  и вводим q2.

Т.к. среди оценок ∆ есть отрицательные, то полученный опорный план не оптимальный. Разрешающий  элемент в ячейке (2;2) равен 0.74. Выводим из базиса переменную q1  и вводим q3.

Т.к. оценок ∆ нет отрицательных, то полученный план (0,027; 0; 0.135;0; 0) оптимальный, F=0,162.

Определим цену игры V=1/F=1/0.162=6.18

Находим решение двойственной задачи

q1  ↔              p3=0.108

q2  ↔              p4=0

q3  ↔              p5=0

q4  ↔              p1=0.135

q5  ↔              p2=0.027

x1=V*p1=6.18*0.135=0.83

x2=V*p2=6.18*0.027=0.17

Значит, средняя величина прибыли 6.18 ед. гарантирована при выпуске 83% продукции вида А2 и 17% продукции вида А3. Продукцию вида А1 выпускать не выгодно (эту стратегию мы вычеркнули).

Задание 5

Проведите две итерации методом наискорейшего спуска в задаче нелинейного программирования без ограничений

Указание.

1) Начиная из исходной точки X0 = (x10, x20) = (0,1), найдите одномерные минимумы на каждой итерации аналитически, используя необходимое условие существование экстремума.

2) Покажите на графике направления спуска и последовательные приближения к точке минимума.

3) Вычислите значение целевой функции в исходной точке и последующих приближениях.

=x12 – 3x1x2 + 4x22 -3

Решение

Находим градиент функции

Строим первое приближение

Строим второе приближение

Линии уровня

x12 – 3x1x2 + 4x22 -3=С

Делаем замену переменных

1,8+3,2=С+3

Задание 6

На станции А1, А2, А3 поступил однородный груз, который надо отвезти заказчикам В1, В2, В3.

Потребности заказчиков (в условных единицах), количество грузов на каждой станции (в тех же единицах) и тарифы (стоимость перевозки единицы груза с данной станции данному заказчику в денежных единицах) указаны ниже. Требуется спланировать перевозки так, чтобы общая сумма стоимости перевозок была наименьшей.

Указания.

1) Установите, является ли модель транспортной задачи, открытой или закрытой. Если модель открыта, закройте ее, введя фиктивного поставщика или потребителя.

2) Постройте исходный опорный план транспортной задачи по правилу «северо-западного угла» и по правилу «минимального элемента».

3) Методом потенциалов проверьте, является ли опорный план, полученный по правилу «северо-западного угла», оптимальным, и если это не так, то составьте оптимальный план, обеспечивающий минимальную стоимость перевозок.

Решение

1) Определим, является ли модель транспортной задачи закрытой. Находим сумму запасов 100+200+80=380 и сравниваем с суммой потребностей 190+120+60=370. Т.к. они не равны, то модель открытая. Закроем ее, введя фиктивного потребителя В4 = 10.

2) Построим исходный опорный план задачи по методу «северо-западного угла»

F=4*100+2*90+5*110+7*10+6*60=1560

Проверим, оптимальный план или нет. Используем метод потенциалов.

Для свободных клеток определим значения оценок.

т.к. в матрице оценок есть отрицательные, то план не оптимальный

Будем перемещать груз в ячейку (1,2) min (110,100)=100