Этап 4. Нахождение оптимального решения.

Этап 1. Ввод исходных данных и необходимых формул.

Организуйте данные на листе MS Excel так, как это показано на Рисунке 1.

Рисунок 1. Форма представления условий задачи определения оптимального плана выпуска продукции.

В столбце F в ячейки введите формулы для подсчета значений целевой функции, а также подсчета расхода ресурсов каждого вида при изменении объемов выпуска продукции. В ячейку F 3 введите формулу, используя математическую функцию СУММАПРОИЗВ, которая позволяет вычислять значение целевой функции

Z = 34*X₁+32*X₂ +28*Х₃ +36*Х₄

представляющей общую прибыль, которую получит предприятие при продаже X₁ изделий первого вида, X₂ - второго, Х₃ – третьего и Х₄ – четвертого вида.

В ячейки F5, F6, F7 - введите формулы для вычисления общего расход ресурсов R₁, R₂, R₃  при выпуске X₁ изделий первого вида, X₂ - второго, Х₃ – третьего и Х₄ – четвертого вида,  используя математическую функцию СУММАПРОИЗВ,.

Ресурс 1                          3*X₁+5*X₂ +0*Х₃ +6*Х₄

Ресурс 2                          2*X₁+1*X₂ +1*Х₃ +2*Х₄

Ресурс 3                          1*X₁+4*X₂ +2*Х₃ +3*Х₄

После ввода всех формул условия будут выглядеть так, как показано на Рисунке 2

Рисунок 2. Постановка задачи определения оптимального плана выпуска продукции.

 

Этап 2. Задание целевой функции и изменяемых ячеек.

· Выберите в меню Сервис пункт– Поиск Решения. Появится диалоговое окно Поиск решения (Рисунок 3).

· В поле окна “Установить целевую ячейку” отметьте ячейку F3 (щелкните сначала по полю окна, а затем по ячейке F3).

· Установите флажок на отметке “Равной максимальному значению”.

· В поле окна “Изменяя ячейки” отметьте ячейки В2 –Е2.

 

 

Рисунок 3. Задание целевой ячейки и изменяемых ячеек.

 

Этап 3. Введение ограничений и определение параметров Поиска решений

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

Для введения ограничения по объему первого ресурса в поле Ссылка на ячейку укажите ячейку $F$4 (для этого достаточно щелкнуть на соответствующей ячейке), а затем в поле Ограничение укажите ячейку $G$4. Таким образом, Вы ввели ограничение по первому ресурсу 3*X₁+5*X₂ +0*Х₃ +6*Х₄

Введите последовательно все ограничения, щелкая по кнопке “Добавить” (как показано на Рисунке 4).

Рисунок 4. Введение ограничений по объемам ресурсов

 

После введения последнего ограничения в диалоговом окне Добавление ограничения нажмите на кнопку ОК. Введенные условия задачи будут представлены так, как показано на Рисунке 5

Рисунок 5. Представление условий задачи оптимального планирования в диалоговом окне Поиск решения

 

После введения всех условий задачи следует открыть диалоговое окно Параметры (Рисунок 6). В этом окне необходимо установить флажки Линейная модель и Неотрицательные значения. (В обычных задачах линейного программирования можно не изменять значения всех остальных параметров, установленных в данном окне по умолчанию. Менять установки параметров: Максимальное время, Предельное число итераций, Относительная погрешность следует, например, при решении линейных задач с дополнительными условиями целочисленности.)

 

Рисунок 6. Настройка Параметров Поиска решения для задач линейного программирования

Этап 4. Нахождение оптимального решения.

После того, как введены все условия и установлены параметры для получения оптимального решения достаточно в диалоговом окне Поиск решения щелкнуть на кнопке Выполнить Полученное оптимальное решение представлено на рисунке 7.

Рисунок 7. Оптимальное решение.

 

В ячейке F3 приведено оптимальное значение целевой функции. При соблюдении всех ограничений максимальная прибыль может составить 2760. Оптимальные объемы выпуска изделий указаны в ячейках B2:Е2 :X₁ =40, X₂ = 0, X₃ =50, X₄ = 0.

Отметим, что в оптимальный план выпуска входит Продукт 3 с наименьшей удельной прибылью, и не входят Продукты 2 и 4.

В ячейках F4, F5, F6 содержатся объемы ресурсов, которые будут необходимы для реализации найденного оптимального плана. При этом можно заметить, что ресурсы второго и третьего вида будут израсходованы полностью, а для ресурса первого вида останется неиспользованный запас (избыток) в 24 единицы.

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

 

Анализ устойчивости оптимального решения задачи линейного программирования. Применение средств MS Excel для исследования влияния возможных изменений в исходных условиях задачи на оптимальное решение

Поскольку вопросы, связанные с пост оптимизационным анализом распространены достаточно широко, то соответствующие инструменты включены в набор стандартных средств решения задач линейного программирования. Если ввести все ограничения и в Окне «Параметры» установить флажок «Линейная модель», то после нажатия кнопки “Выполнить”, будет не только получено оптимальное решение исходной задачи, но и предложено несколько типов отчетов (Рисунок 7). Отчеты размешаются на отдельных листах Рабочей книги.

Рассмотрим дополнительную информацию, которую можно получить из Отчета по устойчивости, представленного на рисунке 8.

 

Рисунок 8. Отчет по устойчивости оптимального решения задачи, представленного на Рисунке 7.

 

Информация в Отчете по устойчивости представлена в виде двух блоков.

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

Информация в строке 5 относится к Продукту 1, который входит в оптимальный план.

В столбце Целевой коэффициент расположено число 34 – удельная прибыль для данного продукта (см. условие Пример 1 – Рисунок 1).

В столбце Результ. Значение расположено число 40 –объем выпуска Продукта 1 в соответствии с найденным оптимальным планом.

В столбце Допустимое увеличение расположено число 16, которое показывает, что при увеличении цены (удельной прибыли) на Продукт 1 не более чем на 16, оптимальный план выпуска будет оставаться неизменным, но при этом максимальная общая прибыль будет увеличиваться. /Если цена на Продукт 1 вырастет больше, чем на 16, то следует внести изменения в условия исходной задачи и решить ее/.

В столбце Допустимое уменьшение расположено число 20, которое показывает, что при уменьшении цены (удельной прибыли) на Продукт 1 не более чем на 20, оптимальный план выпуска будет оставаться неизменным, но при этом максимальная общая прибыль будет уменьшаться. /Если цена на Продукт 1 уменьшится больше, чем на 20, то следует внести изменения в условия исходной задачи и решить ее/.

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

 

Информация в строке 6 относится к Продукту 2, который не входит в оптимальный план.

В столбце Целевой коэффициент расположено число 32 – удельная прибыль для данного продукта (см. условие Пример 1 – Рисунок 1).

В столбце Результ. Значение расположено число 0 –объем выпуска Продукта 2 в соответствии с найденным оптимальным планом.

В столбце Допустимое увеличение расположено число 10,67, которое показывает, что при увеличении цены (удельной прибыли) на Продукт 2 не более чем на 10,67 оптимальный план выпуска будет оставаться неизменным, при этом максимальная общая прибыль не будет изменяться. /Если цена на Продукт 2 вырастет больше, чем на 10,67, то следует внести изменения в условия исходной задачи и решить ее/.

В столбце Допустимое уменьшение расположено число 1Е+30, которое показывает, что при любом (неограниченном) уменьшении цены (удельной прибыли) на Продукт 2, оптимальный план выпуска будет оставаться неизменным, при этом максимальная общая прибыль не будет изменяться.

В столбце Нормир. стоимость расположено число – 10,67, которое показывает, что если компания по каким-либо соображениям намерена включать в план выпуска Продукт 2 без изменения существующей цены (удельной прибыли), то на каждую единицу Продукта 2 максимальная общая прибыль не будет уменьшаться на 10,67.

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

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

· С какой точностью на этапе планирования следует задавать (прогнозировать) уровень цен (удельной прибыли) на различные виды продукции компании. /Рассмотренный пример показывает, что оптимальное решение остается неизменным (устойчивым) при довольно широких колебаниях цен/.

· На какую величину необходимо снизить удельные затраты/повысить удельную прибыль для того, чтобы стало выгодным включить в оптимальный план выпуска продукт, который рассматривался как убыточный, по сравнению с другими продуктами компании.

Второй блок Отчета по устойчивости (в нашем примере строки 10 - 15) содержит информацию о возможном влиянии изменений объемов ресурсов на оптимальный план выпуска и размер максимальной общей прибыли. Интерпретация представленной в Отчете по устойчивости информации несколько отличается для ресурсов, которые должны быть полностью использованы в соответствии с оптимальным планом выпуска, и тех ресурсов, для которых есть резервы (остатки) в соответствии с оптимальным планом.

Информация в строке 14 относится к Ресурсу 2, который в соответствии с оптимальным планом используется полностью.

В столбце Ограничение Правая часть расположено число 130 – допустимый объем Ресурса 2 (см. условие Пример 1 – Рисунок 1).

В столбце Результ. Значение расположено число 130 – фактический расход Ресурса 2 в соответствии с найденным оптимальным планом.

В столбце Допустимое увеличение расположено число 12, которое показывает, что при увеличении объема Ресурса 2 не более чем на 12 структура оптимального плана выпуска будет оставаться неизменной.

В столбце Допустимое уменьшение расположено число 60, которое показывает, что при уменьшении объема Ресурса 2 не более чем на 60 структура оптимального плана выпуска будет оставаться неизменной.

	Неизменная структура оптимального плана выпуска Ресурсы 2 и 3 остаются дефицитными Ресурс 1остается избыточным Продукты 1 и 3 входят в оптимальный план выпуска (при этом возможны изменения объемов выпуска этих продуктов) Продукты 2 и 4 по-прежнему не входят в оптимальный план

В столбце Теневая цена расположено число – 13,33, которое показывает, что если объем Ресурса 2 по отношению к исходному значению 130 увеличится на 1 (уменьшится на 1), то максимальная общая прибыль увеличится на 13.33 (уменьшится на 13,33). При этом могут измениться объемы выпуска Продуктов 1 и 3, и остаток Ресурса 1. Если предполагаемое изменение объема Ресурса 2 (Δ b 2) не выходит за границы диапазона, заданного Допустимым увеличением и Допустимым уменьшением, то для оценки влияния предполагаемого изменения на максимальную общую прибыль достаточно умножить Δ b 2 на Теневую цену Ресурса 2 (=13,33).

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

Информация в строке 13 относится к Ресурсу 1, который в соответствии с оптимальным планом не используется полностью.

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

В столбце Результ. Значение расположено число 120 – фактический расход Ресурса 1 в соответствии с найденным оптимальным планом. Из сопоставления этих чисел (144 и 120) можно сделать вывод, что Ресурс 1 не является дефицитным.

В столбце Допустимое увеличение расположено число 1Е + 30, которое показывает, что при любом (неограниченном) увеличении объема Ресурса 1 никаких изменений в оптимальном плане происходить не будет.

В столбце Допустимое уменьшение расположено число 24, которое показывает, что при уменьшении объема Ресурса 1 не более чем на 24 никаких изменений в оптимальном плане происходить не будет.

В столбце Теневая цена расположено число – 0, которое показывает, что если предполагаемое изменение объема Ресурса 1 по отношению к исходному значению 144не выходит за границы диапазона, заданного Допустимым увеличением и Допустимым уменьшением, то на максимальную общую прибыль эти изменения никак не повлияют.

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

Для многих задач планирования и управления при сведении их к задачам линейного программирования необходимо учитывать, что все или часть переменных могут принимать только целочисленные значения. На первый взгляд может показаться, что для нахождения оптимального целочисленного решения в задаче линейного программирования достаточно поступить следующим образом: 1) решить исходную задачу без явного учета условий целочисленности; 2) если полученное оптимальное решение окажется полностью целочисленным, то процесс решения можно закончить; 3) если же оптимальное решение окажется нецелочисленным, то найденные значения переменных можно округлить до целых. Метод округления в некоторых случаях может привести к искомому оптимальному целочисленному решению, но его нельзя считать универсальным, так как получаемое при округлении решение может выходить за область допустимых значений, или существенно отличаться от подлинного оптимального целочисленного решения.

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

Рисунок 9 Добавление условий целочисленности.

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

Пример 2 Условия комплектности в задачах производственного планирования.

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

В Примере 1 рассматривалась задача нахождения оптимального плана выпуска продукции на предприятии, которое использует три вида ресурсов для выпуска четырех видов продуктов. На Рисунке 1 представлены исходные данные, а на Рисунке 7. оптимальный план выпуска.

Предположим, что всю продукцию предприятия готова закупать крупная компания, которая занимается оптовой торговлей. Но эта компания будет закупать изделия в строго определенных пропорциях, т.е. комплектами. Комплект К1 должен включать М1 изделий первого вида и М4 изделий четвертого вида (в пропорциях М1 / М4 = 4 / 5). Комплект К2 должен включать М2 изделий второго вида и М3 изделий третьего вида (в пропорциях М2 / М3 = 2 / 3). Сформулируем задачу нахождения оптимального плана выпуска комплектной продукции (с учетом того, что количество продаваемых комплектов должно быть целым числом).

Преобразуем соотношение Х1 / Х4 = 4 / 5 в уравнение 5*Х1 = 4*Х4, а соотношение Х2 / Х3 = 2 / 3 в уравнение 3*Х2 = 2*Х3.

Такие преобразования целесообразно сделать по двум причинам:

· соотношение Х1 / Х4 = 4 / 5 является нелинейным, а уравнение 5*Х1 = 4*Х4 - линейным

· если оставить в условии задачи соотношение Х1 / Х4 = 4 / 5, то в ходе решения будет выдаваться сообщение об ошибке - «Деление на 0»

Запишем соответствующие выражения в ячейках под исходной системой условий

B 7 = B 2*5, C 7 = C 2*3,    D 7 = D 2*2,        E 7 = E 2*4

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

Рисунок 10. Введение дополнительных ограничений комплектности

После этого найдем оптимальное решение с помощью средств Поиск решения MS Excel. Найденное оптимальное решение с дополнительными условиями комплектности представлено на рисунке 11. Это решение не удовлетворяет условию целочисленности.

Рисунок 11. Оптимальное решение о выпуске комплектной продукции без учета условий целочисленности

Введение дополнительных условий целочисленности представлено на рисунке 12.

Рисунок12. Введение дополнительных ограничений целочисленности.

Рисунок 13. Оптимальное решение задачи о комплектном выпуске продукции с учетом ограничений целочисленности.

Окончательный вариант оптимального решения задачи производственного планирования из Примера 1 с условием комплектности и целочисленности: Х1 = 8, Х2 = 12, Х3 = 18, Х4 = 10. При этом будет сформировано два комплекта К1 и шесть комплектов К2. Максимальное значение целевой функции Z, соответствующей такому решению, будет равно 1520.

 

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

Вариант 1.

Тип