Задача 3

Производственное объединение, в которое входят две мебельные фабрики, нуждается в обновлении парка станков, причем первой фабрике нужно заменить 3 станка, а второй – семь. Заказы на изготовление станков можно разместить на двух станкостроительных заводах. Первый завод может изготовить не более 6 станков, а второй согласен производить станки, если их будет заказано не менее трех. Цена станков первого завода равна 9 ед, а второго – 10 единицам. Стоимость доставки одного станка с первого завода на первую фабрику равна 2 ед., на вторую – 3 ед., со второго завода – соответственно 4 и 2 ед. Определить оптимальное размещение заказа и план перевозок.

Решение

Обозначим через х_ij - количество станков, доставляемых с завода i на фабрику j. Тогда, с учетом того, что общая стоимость станко будет складываться из стоимости изготовления и доставки станка, будем иметь:

	Фабрика 1		Фабрика 2		Цена станка	Ограничения заводов
Завод 1	2	х11	3	х12	9	6
Завод 2	4	х21	2	х13	10	3
Кол-во заменяемых станков	3		7

Ответ: х₁₁ = 3;

х₁₂ {0; 1; 2; 3};

x₂₁ = 0;

x₂₂ = 7 - x₁₂.

Рис. 4.11

В заключение раздела рассмотрим две задачи, в первой из которых оптимальное решение достигается в вершине, в которой количество активных ограничений превышает размерность задачи, а во второй оптимальные решения образуют бесконечное множество – достигаются на ребре многогранного множества.

З адача 4 (см. Рис. 4.12)

Как видно из рис. 4.12, оптимальная точка М(2;3) находится на пересечении трех граничных линий. Оптимальное значение целевой функции равно 26. Выпишем двойственную задачу и найдем ее решение.

.

Поскольку обе координаты в оптимальной точке прямой задачи не равны нулю, то в оптимальной точке двойственной задачи оба функциональных ограничения выполняются как равенства. Однако поскольку в оптимальной точке прямой задачи все функциональные ограничения активны, то для нахождения оптимального решения двойственной задачи нельзя ни одну из переменных считать равной нулю. Итак, имеем:

Как видим, двойственная задача имеет целый отрезок решений. Это проистекает от того, являются коэффициентами в разложении градиента целевой функции прямой задачи по градиентам активных ограничений. Вследствие того, что в оптимальной точке их три, такое разложение неоднозначно, т.е. имеет место целый набор разложений.

Найдем для проверки правильности вычислений значение целевой функции:

, что подтверждает правильность вычислений.