Глава3. Планирование производства на предприятии

3.1. Постановка задачи

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

На склад кондитерского предприятия ООО «ChocoYum» еженедельно поступает 700 кг. сахара сорта А и 440 кг сорта Б, различного качества и вида (сорт А – обычный сахар, высшего сорта, сорт Б – коричневый сахар, высшего сорта).

На изготовление данных видов товаров назначены 4 работника. С учетом 5 дневной рабочей недели и 2 сменным 10 часовым рабочим днём – 400 человеко-часов.

Нормы расхода сырья, трудоемкость производства продукции и прибыль от реализации единицы продукции показаны в таблице 3.1.

Таблица 3.1

Нормы расхода ресурсов от реализации единицы продукции

Изделия	Нормы расхода
Ресурсы	Карамель	Помадные конфеты	Зефир	Шоколадные изделия
Сахар 1 типа	2	3	2	4
Сахар 2 типа	4	5	2	3
Трудоемкость (чел.-час.)	3	4	4	5
Прибыль (руб.)	16	10	13	26

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

3.2. Описание симплекс-метода

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

Идея симплекс-метода состоит в следующем. Используя систему ограничений в виде системы m линейных уравнений с n переменными (m < n), находят её любое базисное решение, по возможности наиболее простое. Если первое же найденное базисное решение оказалось допустимым, то его проверяют на оптимальность. Если оно не оптимально, то переходят к другому допустимому базисному решению. Симплекс-метод гарантирует, что при этом новом решении линейная форма если и не достигнет оптимума (максимума или минимума), то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не найдено решение, которое является оптимальным.

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

Таким образом, применение симплекс-метода распадается на два этапа:

1) нахождение допустимого базисного решения системы ограничений;

2) нахождение оптимального решения.

При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Так как число базисных решений всегда ограничено, то ограничено и число шагов симплекс-метода [4].

3.3. Алгоритм решения задач параметрического линейного программирования

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

Процесс нахождения решения задачи включает следующие этапы:

Считая значение параметра λ равным некоторому числу принадлежащему промежутку [α, β], находим оптимальный план Х* или устанавливаем неразрешимость полученной задачи линейного программирования.

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

Полагают значение параметра λ равным некоторому возможному числу, принадлежавшему оставшейся части промежутка [α, β], и находят решение полученной задачи линейного программирования.

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