- •Лекция 5. Решение оптимизационных задач в электронной таблице Excel
- •Рассмотрим последовательность решения оптимизационной задачи на примере задачи получении оптимальной смеси, рассмотренной в предыдущей лекции.
- •Отчет по результатам
- •Вид итоговой таблицы, полученной в результате решения
- •Отчет по устойчивости
- •Решение, полученное после увеличения имеющегося объема ресурса 2 на 30 единиц
- •Решение модели после ввода в неё нового вида продукции
- •Отчет по пределам
- •Microsoft Excel 5.0 Отчет по пределам
- •Целочисленные линейные задачи оптимизации
- •Решение целочисленной линейной задачи
- •Целочисленные задачи с бинарными переменными
- •Исходные данные по инвестиционным проектам
- •Модель планирования капитальных вложений
- •Окончательный вид модели планирования капитальных вложений
- •Дальнейшее усложнение модели
- •Нормы времени по видам продукции
- •Усложнение модели определения производственной программы
- •Оптимальное решение усложненной модели определения производственной программы
- •Нелинейные задачи оптимизации
- •Построение нелинейной модели
- •Окончательный вид решения нелинейной модели
- •Новые понятия и термины
- •Вопросы для самопроверки
Окончательный вид модели планирования капитальных вложений
Бинарные переменные дают возможность использовать в модели различные логические условия. Так, если некоторые из рассматриваемых проектов (например, 1, 3 и 6) являются альтернативными, модель может быть дополнена следующим условием:
Это условие говорит о том, что из трех бинарных переменных X1, Х3 и Х6 только одна может иметь значение 1.
В случае, если проект 4 опирается на результаты проекта 5, и не может быть выполнен, если пятый проект не выполняется, то модель дополняется выражением:
Как нетрудно заметить, указанное выражение не выполняется только в одном случае - если выбирается 4 проект и не выбирается 5.
Дальнейшее усложнение модели
Дальнейшее усложнение модели. В рассмотренной выше постановке задачи целевая функция выражала требование максимизации прибыли (или минимизации затрат), связанное с выбором определенных видов продукции для производства (или определенных проектов для их финансирования). Однако часто выбор решения о производстве определенного вида продукции помимо связанных с объемом производства затрат требует также независящих от объема производства затрат, которые могут расходоваться
• на покупку или аренду определенного оборудования или транспортных средств;
• на переналадку существующего оборудования для производства указанного вида продукции;
• на разработку и изготовление определенного производственного оборудования, инструмента или приспособлений;
• на содержание дополнительного персонала.
Все эти расходы последуют только в том случае, если определенное решение (например, решение о производстве данного вида продукции) принято.
Рассмотренный ниже пример имеет целью прояснить формулировку и решение задачи учета постоянных расходов, связанных в выбором одной из бинарных переменных.
Допустим, что некоторая компания производит три вида продукции, используя для каждого из них три технологические операции: токарную, шлифовальную и сборочную. Нормы времени на проведение этих операций для одного изделия каждого вида помещены в Табл. 7.20. Здесь же помещены данные по имеющимся в компании производственным мощностям по каждому из трех видов работ.
Известно, что производство и реализация единицы продукции первого вида дает вклад в общую прибыль компании, равный 48 долл., а каждая единица продукции второго и третьего вида - 55 долл. и 50 долл., соответственно.
Таблица 7.20
Нормы времени по видам продукции
Операции |
Время на проведение операции |
Производ. мощности, час |
||||
|
Продукция 1, час |
Продукция 2, час |
Продукция 3, час |
|
||
Токарная Шлифовальная Сборочная |
2 6 5 |
3 3 6 |
6 4 2 |
600 300 400 |
Производство каждого вида продукции требует значительной переналадки поточной линии, что обходится для первого вида продукции в 1000 долл., для второго вида продукции - в 800 долл. и для третьего вида продукции - в 900 долл. Отдел маркетинга компании полагал, что вся произведенная продукция будет продана. Руководство же компании хочет определить наилучший набор выпуска продукции, который обеспечит ей максимальную прибыль.
В данном случае, несмотря на то, что у нас имеется только три вида продукции, нам потребуется шесть переменных, чтобы промоделировать данную задачу. Определим их следующим образом.
1. Xi - количество продукции вида i, которое должно быть произведено, i=1,2,3.
2. Yi= 1, если Хi 0, i=1,2,3;
Yi= 0, если Xi= 0, i=1,2,3.
Таким образом, мы имеем три обычные целочисленные управляемые переменные X1, Х2 и Х3, выражающие объем производимой продукции по ее видам. При этом каждая Xi имеет соответствующую бинарную переменную Yi, которая будет равняться 1, если соответствующая Xi будет иметь положительное значение и будет равна 0, если соответствующая Xi будет равна нулю. Дальше мы поясним это более подробно.
Используя введенные переменные построим целевую функцию задачи в следующем виде:
Как нетрудно заметить, первые три слагаемые построенной целевой функции вычисляют величину общей прибыли от производства всех трех видов продукции. Последние три компонента уменьшают общую прибыль на величину затрат, связанных с переналадкой производства для изготовления выбранных видов продукции.
Данная задача требует построения нескольких наборов ограничений на переменные модели. Первый из них связан с ограниченностью производственных мощностей данного предприятия-изготовителя. Производственные мощности по различным видам работ, очевидно, будут связаны с наличием на заводе определенного количества соответствующего оборудования, эффективным временем его работы и обеспеченностью кадрами. В приведенном ниже наборе ограничений по производственным мощностям правые части соответствующих неравенств будут выражать реально имеющийся в распоряжении предприятия фонд времени работы определенной группы оборудования или работников (например, рабочих-сборщиков).
2Х1 + 3Х2 + 6Х3 <= 600 ограничение по токарным операциям
6Х1 + ЗХ2 + 4Х3 <= 300 ограничение по шлифовальным операциям (7.2)
5X1 + 6X2 + 2X3 <= 400 ограничение по сборочным операциям
К этому набору ограничений следует добавить требование неотрицательности объемов производимой продукции:
Хi > = 0; i = 1, 2, 3.
Второй набор ограничений на переменные Yi, которые рассматриваются в рамках данной модели как бинарные, будет иметь вид:
Третий набор ограничений, определяющий связь между переменными Xi и Yi, может иметь следующий вид:
Хi=МiYi ; i=1, 2, 3;
где Mi - верхний предел объема производства продукции i-го вида (Xi).
Параметры Мi могут быть определены, исходя из следующих соображений. Посмотрим, какое максимально возможное число изделий первого вида по токарным операциям сможет выпустить предприятие, если второй и третий вид изделий вообще не будет выпускаться. Для этого положим в ограничении по токарным операциям Х2=Х3=0 и определим X1. Как нетрудно заметить, X1=600/2=300. Аналогично определим максимально возможную программу выпуска первого изделия по шлифовальным и сборочным операциям. Она составит 300/6=50 и 400/5=80, соответственно. Окончательно максимально возможный объем выпуска первого изделия будет определятся по самой трудоемкой операции и составит 50 единиц. Таким образом можно получить следующие выражения для вычисления параметров Mi:
Заметим, что данный метод применим только в случае, если все коэффициенты в ограничениях по производственным мощностям будут неотрицательными величинами.
Окончательно третий набор ограничений (назовем их ограничениями связи) будет иметь следующий вид:
Перенесем исходные данные модели, содержащиеся в целевой функции (7.1) и ограничениях (7.2-7.4), на текущий лист электронной таблицы (см. Табл. 7.21).
В приведенной модели ячейки B4:D4 зарезервированы для искомых величин объемов производства продукции по их видам X1,X2,X3, а ячейки B14:D14 - для значений бинарных переменных Y1, Y2 и Y3. Коэффициенты целевой функции помещены в ячейках B6:D7. Целевая функция находится в ячейке F7, имея вид следующей формулы:
=СУММПРОИЗВ(В6:D6,В4:D4) - СУММПРОИЗВ(В7:D7,В14:D14).
Таблица 7.21