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

Приведем исходную задачу к каноническому виду:

 

 

 

 

 

 

 

 

 

 

 

 

 

Дополнительные  переменные y_i есть остатки ресурсов каждого вида. Т.е. y₁ – это остаток молока натурального, y₂ – остаток молока сухого и т.д.

 

 

 

 

Составим двойственную задачу:

 

 

 

 

 

 

 

 

 

Двойственные  переменные z_i - это оценки ресурсов задачи (теневые цены).

В двойственной задаче приведем ограничения к виду равенства, вычитая из левых частей ограничений дополнительные переменные:

 

 

 

 

 

 

 

 

 

 

Дополнительные  двойственные переменные v_j есть потери при производстве единицы продукции j-го типа.

Решим данную задачу с помощью надстройки MS Excel “Поиск решения”.

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

Ячейка, которая  содержит формулу вычисления значения целевой функции, называется целевой.

 

1. Подготовка исходных данных задачи на листе Excel. Оформление исходных данных для надстройки “Поиск решения” показано на рисунке 1.

Изменяемыми ячейками будут ячейки A3:D3, которые отведены под значения переменных. В них введены начальные значения переменных (нулевые).

 

 

 

 

 

 

 

 

 

Рисунок 1- Лист Excel с исходными данными и формулами для решения задачи с

помощью надстройки “Поиск решения”

Целевой ячейкой будет являться ячейка Е5, которая содержит формулу вычисления значения целевой функции (т.е, прибыль от продажи мороженого всех видов). При большом числе переменных эту формулу удобно задавать с помощью стандартной функции Excel СУММПРОИЗВ(). Выбрав ее название в меню, заполняем окно параметров. При этом Массив 1 – это диапазон коэффициентов целевой функции, а Массив 2 – диапазон изменяемых ячеек (в нашем примере A3:D3). Функция СУММПРОИЗВ() соответствующие ячейки диапазонов перемножает и находит сумму этих произведений. Например, формула в ячейке Е5 записана в виде CУММПРОИЗВ(A5:D5;A3:D3), что соответствует формуле расчета прибыли 315x₁+278x₂+573x₃+370x₄.

 В ячейки E7:E14 введены формулы вычисления левых частей ограничений (расход ресурса каждого вида).  Они также заданы с помощью функции СУММПРОИЗВ().

2.  Вызов надстройки “Поиск решения” выполняется командой Сервис/Поиск решения.

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

 

 

 

 Пример заполнения  полей окна “Поиск решения”  показан на рисунке 2.

 

 

 

 

 

 

 

 

 

 

Рисунок 2- Окно “Поиск решения” для задачи планирования производства

мороженого

Поскольку все  ограничения по ресурсам имеют одинаковый знак,  то их можно задать одновременно: E7:E14<=F7:F14 (рисунок 3). C помощью кнопок Добавить, Изменить, Удалить в окне “Поиск решения” можно редактировать введенное ограничение.

 

 

 

 

 

Рисунок 3- Окно “Добавление ограничения”

4. Задание параметров поиска. Нажав кнопку Параметры, устанавливаем параметры алгоритма поиска (рисунок 4).

 

 

 

 

 

 

 

 

 

 

 

Рисунок 4- Окно “Параметры поиска решения”

Все параметры оставляем по умолчанию, устанавливаем только два флажка:

• флажок Линейная модель;
• флажок Неотрицательные значения.

5 . Запуск процесса решения. Нажатие кнопки Выполнить активизирует процесс поиска решения.   По окончании поиска  на экране появляется окно “Результаты поиска решения“ (рисунок 5).

 

 

 

 

 

 

Рисунок 5- Окно “Результаты поиска решения”

Задача успешно решена и в окне появляется сообщение “Решение найдено. Все ограничения и условия оптимальности выполнены”.  Устанавливаем переключатель в положение Сохранить найденное решение, в списке “Тип отчета” выделяем все названия отчетов, а затем нажимаем кнопку OK. На листе Excel с условием задачи зафиксирован результат решения (изменяемые ячейки получат оптимальные значения, а также изменится результат в ячейках с формулами), а на отдельных листах сформированы отчеты по результатам, по устойчивости и по пределам.

6. Интерпретация результатов решения. Лист Excel с результатами решения показан на рисунке 6. Из него следует, что оптимальные значения переменных следующие: =0, =25,37, =103,39, =16. Таким образом, следует производить 25,37 тон сливочного мороженого II вида, 103,39 тон мороженого пломбир I вида и 16 тон мороженого пломбир II вида. При этом общая прибыль составит 72213,54 денежных единиц. Левые части ограничений представляют собой расход ресурса при оптимальном плане производства, а правые – имеющийся запас ресурсов. Сравнение этих данных показывает, что ресурсы «молоко натуральное», «молоко сгущенное» и «молоко сгущенное обезжиренное» будут израсходованы полностью (первое, шестое и седьмое ограничение).

Имеются следующие  остатки по ресурсам:

• «молоко сухое» (второе ограничение) (4800-3149) 1651 кг.;
• «молоко сухое обезжиренное» (третье ограничение) (5200-4596) 604 кг.;
• «масло сливочное» (четвертое ограничение) (22360-19131) 3229 кг.;
• «сахар» (пятое ограничение) (26240-20717) 5523 кг.;
• «затраты оборудования» (восьмое ограничение) – 69 машино/ч.

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 6- Результаты решения задачи планирования производства мороженого

Содержимое  отчетов показано на рисунках 7 – 9.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 7 – Отчет по результатам

Отчет по результатам (рисунок 7) состоит из 3-х таблиц.

В первой таблице  приведены сведения о значении целевой функции. Для данного примера F^*=72213,54 – это максимальное значение прибыли, которое может быть достигнуто.

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

Третья таблица  показывает результаты оптимального решения  для ограничений и граничных условий. В графе формула приведены зависимости, которые были введены в диалоговое окно “Поиск решения”. В графе Значение находятся величины использованного ресурса, а в графе Разница показано количество неиспользованного ресурса (оптимальные значения дополнительных переменных y_i (i= )). Если ресурс используется полностью, то в графе Статус указывается связанное, в противном случае указывается не связанное. Остатки ресурсов имеют следующие оптимальные значения:

Отчет по устойчивости  (рисунок 8) состоит из 2-х таблиц.

В первой таблице  приведена информация по переменным:

• оптимальное значение переменных (j= );
• соответствующие значения нормированной стоимости, (j= );
• коэффициенты в целевой функции при переменных C_j (j= );
• допустимые приращения коэффициентов целевой функции ( и ), при которых не изменяется  оптимальное решение.

Из столбца  ”Нормированная стоимость” можно  выписать оптимальные значения дополнительных двойственных переменных:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 8– Отчет по устойчивости

Во второй таблице  показаны аналогичные значения для  ограничений:

• величины использованных ресурсов;
• теневые цены для каждого ресурса ;
• величины правых частей ограничений (запасы ресурсов) b_i (i= ) ;
• предельные приращения ресурсов Db_i⁺ и Db_i^- , при которых сохраняется структура решения.

Таким образом, из столбца ”теневая цена” второй таблицы отчета по устойчивости получаем оптимальные значения двойственных переменных: z₁^*=0,84; z₂^*=0; z₃^*=0;  z₄^*=0; z₅^*=0; z₆^*=5,64; z₇^*=1,76;  z₈^*=0.

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

 

 

 

 

 

 

 

 

 

 

Рисунок 9– Отчет по пределам

 

4 ОТВЕТЫ НА ВОПРОСЫ ЗАДАНИЯ

1. Какое количество мороженого каждого вида следует производить? Какая будет получена прибыль?

Следует производить  сливочное мороженое II вида 25,37 тон, мороженое пломбир I вида 103,39 тон и пломбир II вида 16 тон. При этом максимальная прибыль составит 72213,54 денежных единиц.

2. Полностью ли задействовано оборудование в оптимальном плане производства?  Имеются ли остатки сырья какого-либо вида?

В оптимальном плане  производства оборудование не задействовано  в полной мере и его остаток, согласно отчету по устойчивости (рис.8), составляет 69 машино/ч.

Согласно отчету по устойчивости (рис. 8), имеются следующие остатки по сырью: «молоко сухое» кг.; «молоко сухое обезжиренное» кг.; «масло сливочное» кг.; «сахар» кг.

3. Какое управленческое решение принесет большую прибыль: дополнительно ввести в производство 100 кг молока сгущенного, или увеличить количество молока натурального на 200 кг?

Согласно отчету по устойчивости (рис. 8) теневая цена молока сгущенного равна z₆^*=5,64 и допустимое увеличение равно 1115,02, поэтому при дополнительном вводе в производство 100 кг этого ресурса прибыль увеличится на DF=100× z₆^*=100×5,64=564 денежных единиц. Теневая цена молока натурального составляет z₁^*=0,84 и допустимое увеличение равно 11665,94, поэтому при увеличении количества молока натурального увеличение прибыли составит DF=200× z₁^*=200×0,84=168 денежных единиц. Поэтому управленческое решение дополнительного ввода в производство 100 кг молока сгущенного принесет большую прибыль.

4. К чему приведет плановое задание по выпуску 1 т сливочного мороженого 1 вида?

Согласно отчету по устойчивости (рис. 8) нормированная стоимость сливочного мороженого I вида составляет Плановое задание по выпуску 1 т мороженого этого вида приведет к уменьшению прибыли на DF=1× v₁^*=1×146=146 денежных единиц.

 

ЗАКЛЮЧЕНИЕ

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

В результате решения  задачи с помощью надстройки MS Excel “Поиск решения” было получено оптимальное решение поставленной задачи, в соответствии с которой следует производить мороженое сливочное II вида в количестве 25,37 тон, мороженого пломбир I вида - 103,39 тон и мороженое пломбир II вида – 16 тон, а производить мороженое сливочное I вида не выгодно. При этом будет достигнута максимальная  прибыль в размере 72213,54 денежных единиц. 

Была составлена  математическая модель задачи, математическая модель в канонической форме, модель двойственной задачи и модель двойственной задачи с ограничениями в форме равенства. Подробно описано решение задачи с помощью надстройки MS Excel “Поиск решения”. В виде рисунков 7-9 приведены отчеты по решенной задаче. Даны ответы на поставленные вопросы.

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

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