Линейные модели оптимизации в управлении

Линейные модели оптимизации в управлении

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

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

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

Общая задача линейной оптимизации заключается в нахождении максимума (минимума) линейной целевой функции

,                     (2.1)

при ограничениях

     ,                     (2.2)

  ,                               (2.3)

Рекомендуемые материалы

.                                  (2.4)       

Функция  называется целевой функцией, критерием оптимальности или линейной формой.

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

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

При решении ряда оптимизационных задач требуется, чтобы значения неизвестных выражались в целых числах. Естественно, к задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д. и т.п.). Такие задачи относятся к задачам целочисленной оптимизации. Математическая модель задачи линейной целочисленной оптимизации также определяется формулами (2.1)-(2.4), но в данном случае налагается дополнительное требование целочисленности всех (или части) неизвестных. Если требование целочисленности распространяется лишь на часть неизвестных величин задачи, то такая задача называется частично целочисленной. 

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

· Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные задачи?

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

· В чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?

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

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

Эффективным средством решения задач линейной оптимизации является MS Excel. Входящий в состав данного программного продукта пакет Поиск решения (Solver) позволяет проводить решения задач подобного рода с большим (свыше 200) числом переменных и ограничений.

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

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

Пример 1. Определение оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции П1 и П2 , которая поступает в оптовую продажу. Для производства используются два вида сырья  и . Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции приведен в таблице.   

Таблица 2.1

Маркетинговые исследования показали, что суточный спрос на продукцию П1 не превышает спрос на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию  П2 не превышает 2 единиц в сутки.

Оптовые цены единицы продукции равны для П1 3 д.е., для П2- 4 д.е. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?

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

        

         Доход от реализации продукции (целевая функция) составит . Таким образом, данная простая задача сводится к максимизации целевой функции  при учете вышеприведенных ограничений.

Проведем решение задачи в Excel.

Введем данные на рабочий лист так, как показано на Рис 2.1.

Искомые значения переменных  будут располагаться в ячейках A10 и B10 соответственно, целевая функция – в ячейке E10.   

Рис. 2.1.

В ячейки A3, A4 введем левые части функций – ограничений:  =2*A10+3*B10 и  = 3*A10+2*B10 соответственно. В ячейку C10 введем левую часть третьей функции-ограничения: =A10-B10.

Далее, запускаем пакет Поиск решения (Сервис ® Поиск решения) и устанавливаем целевую и изменяемые ячейки, а также вводим ограничения (Рис.2.2):

        

Рис. 2.2. Окно диалога Поиск решения.

Поиск решения дает ответ   

Пример 2 .Использование мощностей оборудования.

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

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

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

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

Ограничение по заданному количеству продукции имеет вид:

.

Задача решается на минимум затрат на производство:

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

Проведем решение задачи в Excel.         Введем данные на рабочий лист так, как показано на Рис 2.3.

Рис. 2.3. Данные для решения примера 2.

В ячейки B7:E7 введем формулы для ограничений по объему выпускаемой продукции (), в диапазон ячеек F19:F21 – формулы для ограничений по времени работы машин (). В качестве целевой ячейки выберем H11 и введем в нее формулу минимизируемой функции.

         С помощью Поиска решения получим следующий ответ:

Искомое значение минимальных затрат на производство составляет 725,32 д.е.

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

Пример 3. Оптимизация производственной программы.

Автомобилестроительный завод выпускает три модели автомобилей, которые изготавливаются последовательно в трех цехах. Мощность цехов составляет 300, 250 и 200 человеко-дней в декаду. В первом цехе для сборки одного автомобиля первой модели требуется 6 человеко-дней, второй модели – 4 и третьей модели – 2 человеко-дня в неделю соответственно. Во втором цехе трудоемкость равна 3, 4 и 5 человеко-дней соответственно, в третьем – по 3 человеко-дня на каждую модель. Прибыль, получаемая от продажи автомобиля каждой модели, составляет соответственно 15, 13 и 10 тыс. д.е. Требуется построить модель оптимального плана и определить оптимальные количества моделей каждого типа, т.е. такие, при которых прибыль завода будет максимальной.

Решение. Пусть  - количество выпускаемых автомобилей  -й модели в течение декады (). Модель может быть описана следующей целевой функцией и системами ограничений:

                               (2.5)

Решение.

Введем данные на рабочий лист так, как показано на Рис. 2.4.

Искомые значения переменных  будут размещаться в ячейках A10:B10, целевая функция – в ячейке E10.  

В ячейки A3:A5 введем левые части функций – ограничений, соответствующих второму, третьему и четвертому соотношению из (n.5).

С помощью Поиска решения получим ответ   

Рис. 2.4. Данные для решения примера 3.

Пример 4. Размещение проектов на предприятиях.

Имеется  инвестиционных возможностей (вариантов проектов), которые можно реализовать на (предприятиях). Эффективность реализации каждой инвестиции на каждом из  объектов  задана в таблице 2.2.

                                      Таблица 2.2.

Целевой функцией, подлежащей оптимизации, является функция:

                            ,

где  - искомые распределения инвестиций по объектам.

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

                                      ,

означающие, что на каждом объекте может быть реализован лишь один проект, и

                                      ,

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

Решение. Введем данные на рабочий лист (Рис.2.5.).

В ячейку B17 введем формулу =СУММ(B12:B16) и скопируем эту формулу в диапазон C17:F17. Аналогично, введем формулу  =СУММ(B12:F12) в ячейку G12 и скопируем ее в диапазон G13:G16. Введем в ячейку для целевой функции (I13) формулу

Рекомендуем посмотреть лекцию "Казахские бии".

                    =СУММПРОИЗВ(B4:F8;B12:F16).

Рис. 2.5. Данные для решения примера 4.

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

Поиск решения дает ответ  (остальные ), .