Основы исследования операций (стр. 10 )

в принципе и доход будет чуть больше (раньше был равен ).

7.4. Добавление нового ограничения

В рассмотренной задаче введем дополнительное ограничение: суммарное количество краски П1 и П2, выпускаемое цехом за сутки, должно быть не меньше 5т. Это ограничение запишется следующим образом:

Проверим, удовлетворяется ли это ограничение на прежнем оптимальном плане:

Это ограничение не удовлетворяется, т. е. прежнее решение не является оптимальным для новой задачи.

Введением дополнительной переменной x7 приведем это ограничение-неравенство к уравнению

и присоединим к основной задаче, сменив в последнем равенстве знаки.

Решим полученную задачу двойственным симплекс-методом. Однако в новой дополнительной строке (ограничений) нужно исключить базисные переменные (оставить только свободные).

В результате, используя последнюю симплекс-таблицу, получим следующее:

		3	2	0	0	0	0	0
	БП	x1	x2	x3	x4	x5	x6	x7
2	x2	0	1	2/3	–1/3	0	0	0	4/3
3	x1	1	0	–1/3	2/3	0	0	0	10/3
0	x5	0	0	–5/3	1/3	1	0	0	5/3
0	x6	0	0	–2/3	1/3	0	1	0	2/3
0	x7	0	0	1/3	1/3	0	0	1	–1/3
	F	0	0	1/3	4/3	0	0	0	38/3

В последней строке таблицы нет отрицательных оценок, следовательно, если бы в столбце вектора не было отрицательных чисел, то в таблице был бы записан оптимальный план. Поскольку в указанной таблице есть такое число (в последней строке), необходимо перейти к новой симплекс-таблице. Однако в строке x7нет отрицательных чисел, следовательно поставленная задача не имеет решения.

Рассмотрим другое дополнительное ограничение к модели исходной задачи (6.1–6.3). Пусть объем производства краски П1 должен быть не менее 3.5т. В математической модели появится новое ограничение

Прежнее оптимальное решение не удовлетворяет этому ограничению. Преобразуем его к виду равенства

Заменим базисную переменную x1через свободные из прежней оптимальной симплекс-таблицы получим

Сменив знаки левой и правой частей, добавляем уравнение к прежней оптимальной симплекс-таблице.

		3	2	0	0	0	0	0
	БП	x1	x2	x3	x4	x5	x6	x7
2	x2	0	1	2/3	–1/3	0	0	0	4/3
3	x1	1	0	–1/3	2/3	0	0	0	10/3
0	x5	0	0	–5/3	1/3	1	0	0	5/3
0	x6	0	0	–2/3	1/3	0	1	0	2/3
0	x7	0	0	–1/3	2/3	0	0	1	–1/6
	F	0	0	1/3	4/3	0	0	0	38/3

Получили псевдооптимальный план. Решаем задачу далее двойственным симплекс-методом, выводя из базисных переменную x7 и вводя x3.

		3	2	0	0	0	0	0
	БП	x1	x2	x3	x4	x5	x6	x7
	x2	0	1	0	1	0	0	2	1
	x1	1	0	0	0	0	0	–1	7/2
	x5	0	0	0	–3	1	0	–5	5/2
	x6	0	0	0	–1	0	1	–2	1
	x3	0	0	1	–2	0	0	–3	1/2
	F	0	0	0	2	0	0	1	25/2

На следующей итерации получили оптимальное решение с доходом F=12.5 тыс. руб.

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

8. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Управление заключается в сборе информации, ее переработке и выводе управляющей информации для изменения хода процесса.

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

Одной из задач управления предприятием является задача определения оптимального плана производства изделий, обеспечивающего заданный спрос продукции при минимизации затрат на производство и хранение продукции. Это задача оптимального управления запасами. Теория управления запасами позволяет определять уровни запасов материалов, полуфабрикатов, производственных мощностей и других ресурсов в зависимости от спроса на них.

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

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

8.1 Качественное описание

Предприятие разрабатывает календарный план выпуска изделий на плановый период, состоящий из нескольких этапов. Текущая деятельность предприятия характеризуется следующими параметрами: