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

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

В математическую модель входят три составляющие:

1. ЦФ – целевая функция или критерий оптимизации, показывает в каком смысле решение должно быть оптимальным. Целевая функция может стремиться к max или min. При ограничении на сырье целевая функция будет стремиться к min, то есть необходимо определить такой выпуск продукции, при котором расход сырья был бы min. Если назначить ограничение на прибыль, то целевая функции будет стремится к max, то есть необходимо определить такой выпуск продукции, при котором прибыль была бы максимальной.

2. ОГР – ограничения, устанавливающие зависимости между переменными.

3. ГРУ – граничные условия, показывающие, в каких пределах могут быть искомые переменные.

Решение задачи, удовлетворяющее всем граничным условиям и всем ограничениям, называется - допустимым. Если математическая модель задачи составлена правильно, то задача имеет целый ряд допустимых решений. Критерий выбирается человеком, который принимает решение. С помощью критерия можно оценивать качества желательные (прибыль, производительность) и не желательные (затраты, расход материалов). Тогда в первом случае ЦФ – max, а во втором случае ЦФ – min.

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

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

Наиболее распространенным методом решения задач линейного программирования является так называемый симплекс-метод. В простейшем случае, когда число переменных равно двум, удобен простой и наглядный графический метод. На ЭВМ задачи линейного программирования решаются в системах поддержки принятия решений (СППР). СППР, использующие экономико-математические методы, реализованы в специальных программах (Mathcad, Excel).

 

Решение задачи планирования производства

Рассмотрим следующую задачу планирования производства.

Небольшая фабрика выпускает два типа красок: для внутренних (I) и наружных (Е) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно. Расходы продуктов А и В на 1 т соответствующих красок приведены в табл. 4.10.1. Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3000 руб. для краски Е и 2000 руб. для краски I. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Таблица 4.10.1. Исходные данные задачи

Исходный продукт	Расход исходных продуктов на тонну краски, т	Максимально возможный запас, т
краска Е	Краска I
А В

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

1. Для определения, каких величин строится модель (т.е. каковы переменные модели)?

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

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

Задача планирования производства в общем виде записывается следующим образом:

;

;

dj <= Xj <= Dj;

i=1,m; j=1,n;

где F – целевая функция; C _j - прибыль получаемая от реализации единицы продукции j-го типа, Х _j – количество выпускаемой продукции j – го типа, - норма расхода i- ресурса для выпуска единицы продукции j-го типа, -количество располагаемого ресурса i – го вида, Dj – максимально возможный выпуск j- вида продукции, dj – минимально возможный выпуск продукции j- вида.

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

X_I — суточный объем производства краски I и X_E — суточный объем производства краски Е. Суммарная суточная прибыль от производства X_Iкраски I и X_E краски Е равна

Z = 3000*X_E + 2000*X_I.

Целью фабрики является определение среди всех допустимых значений X_E и X_I таких, которые максимизируют суммарную прибыль, т. е. целевую функцию Z.

Перейдем к ограничениям, которые налагаются на X_E и X_I. Объем производства красок не может быть отрицательным, следовательно:

X_E, X_I >=0

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

X_E +2 X_I <=6,

2 X_E + X_I <=8.

Кроме того, ограничения на величину спроса на краски таковы:

X_I - X_E <=1,

X_I <=2.

Таким образом, математическая модель данной задачи имеет следующий вид:

Максимизировать

Z=3000* X_E +2000* X_I

При следующих ограничениях:

X_E +2* X_I <=6,

2* X_E + X_I <=8,

X_I - X_E <=1,

X_I <=2,

X_I, X_E >=0

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

На листе книги создадим таблицу Исходные данные и отведем диапазон ячеек под решение.(рисунок 4.10.1).

В ячейку D13 введем функцию цели =E4*C11+E5*D11

В ячейки D16: D19 соответственно:

=C11+C4*D11

=B5*C11+D11

=D11-C11

=D11

В ячейки С11, D11 введем начальные значения, т.е. нулевые значения.

После этого выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver), как показано на рисунке 4.10.2.

Рисунок 4.10.1 - Диапазоны, отведенные под исходные данные

 

Рис. 4.10.2 - Диалоговое окно Поиск решения задачи о планировании производства красок

После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (Solver Results), которое сообщает, что решение найдено (рисунок 4.10.3).

Результаты расчета нашей задачи (оптимальный план производства и соответствующая ему прибыль) представлены на рисунке 1.1. Как видно из рисунка, оптимальным является производство 3,33 т краски Е и 1,33 т. краски I в сутки. Этот объем производства принесет фабрике 12666,66 тыс. руб. прибыли.

 

Рисунок 4.10.3 - Диалоговое окно Результаты поиска решения

 

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

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

В поле Изменяя ячейки указываются ячейки, которые должны изменяться в процессе поиска решения задачи, т. е. ячейки отведенные под переменные задачи. В нашем случае в поле Изменяя ячейки введем диапазон C11:D11.

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

Рисунок 4.10.4 - Диалоговое окно Добавление ограничений

В поле Ссылка на ячейку введите левую часть ограничения D16, а в поле Ограничение -правую часть, в нашем примере D4. с помощью раскрывающегося списка вводится тип соотношения между левой и правой частями ограничения. В нашем примере это >=.Таким образом, требование неотрицательности переменных задано.

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

Теперь нажмите Параметры в диалоговом окне Поиск решения, для того чтобы проверить, какие параметры заданы для поиска решений (рисунок 4.10.5).

Рисунок 4.10.5 - Диалоговое окно Параметры поиска решения

Рассмотрим элементы этого окна:

· Поле Максимальное время (Max Time) служит для ограничения времени, отпускаемого на поиск решения задачи

· Поле Предельное число итераций (Iteration) служит для ограничения числа промежуточных вычислений

· Поля Относительная погрешность (Precision) и Допустимое отклонение

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

· Флажок Линейная модель (Assume Linear model) служит для поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. В случае нелинейной задачи этот флажок должен быть сброшен, в случае линейной задачи — установлен, т. к. в противном случае возможно получение неверного результата

· Флажок Показывать результаты итераций (Show Iteration Results) служит для приостановки поиска решения и просмотра результатов отдельных итераций.

· Флажок Автоматическое масштабирование (Use Automatic Scaling) служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, например, при максимизации прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

· Группа Оценка (Estimates) служит для выбора метода экстраполяции.

· Группа Производные (Derivatives) служит для выбора метода численного дифференцирования.

· Группа Метод (Search) служит для выбора алгоритма оптимизации.