Для изготовления трех видов продукции P₁, P₂ и P₃ используют три вида ресурсов S₁, S₂, S₃ . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице:

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

На основе проведенного анализа определить:

1. Ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.

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

3. Суммарную стоимостную оценку ресурсов, используемых при производстве единицы каждого изделия.

4. На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

5. На сколько можно снизить запас каждого из ресурсов, чтобы это не привело к уменьшению прибыли?

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

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

8. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас ресурса вида S₁ увеличить на 4 ед., а вида S₃ и Р₄ уменьшить на 71,4 ед.?

9. Целесообразно ли включать в план продукцию Р₄ с прибылью на единицу продукции 10ед., если нормы затрат сырья для ее производства составляют 0,3; 0,4; и 0,8ед. соответственно?

Теоретические сведения

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

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

Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.

Допустимым решением (планом) задачи линейного программирования называется вектор

удовлетворяющий системе ограничений.

Множество допустимых решений образует область допустимых решений (ОДР).

Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования и обозначается Х_опт.

Математическая модель линейного программирования может быть канонической и неканонической.

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

Если хотя бы одно ограничение является неравенством, то модель задачи линейного программирования является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную x_n+i. Если знак неравенства меньше либо равно, то балансовая переменная вводится со знаком плюс, если знак неравенства больше либо равно, то - минус. В целевую функцию балансовые переменные не вводятся. Чтобы составить математическую модель задачи линейного программирования, необходимо:

- Ввести обозначения переменных;

- Исходя из цели экономических исследований, составить целевую функцию;

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

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

Максимизировать (минимизировать) функцию

(2.1.1)

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

(2.1.2)

(2.1.3)

(2.1.4)

где - x _j, j=1,n управляющие переменные или решения задачи (2.1) - (2,4),

b _i ,a _ij , i=1,m, j=1,n- параметры

f-целевая функция или критерий эффективности задачи.

Функция (2.1.1)-линейная, ограничения (2.1.2) - (2.1.4) - линейные. Задача содержит n переменных и m ограничений. Решить задачу линейного программирования - это значит найти значения управляющих переменных x_j, j=1,n удовлетворяющих ограничениям (2.1.2) - (2.1.4), при которых целевая функция (2.1.1) принимает минимальное или максимальное значение.

Построение модели

Прямая задача.

За переменные возьмем число виды изделий - обозначим их как р1, р2, и р3 для первого, второго и третьего вида изделий соответственно.

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

Максимизировать функцию

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

Система ограничений:

Двойственная задача.

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

Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитные (т. е. полностью используемые ресурсы) получают ненулевые оценки, а недефицитные - нулевые оценки.

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

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

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

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

Каждому ограничению ставим в соответствие переменную двойственной задачи .

Каждой переменной прямой задачи ставится в соответствие ограничение двойственной задачи. Знак неравенства в ограничениях прямой задачи меняется на противоположный для двойственной.

В правые части ограничений записываются коэффициенты целевой функции прямой задачи. Матрица коэффициентов прямой задачи преобразуется в транспонированную.

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

Минимизировать функцию

Построение математической модели

1) Цель - получение максимальной прибыли.

2) Параметрами являются все числовые данные, приведенные в условии задачи.

3) Управляющие переменные:

P₁ - число единиц ресурсов затрачиваемых на изготовление первой продукции

P₂ - число единиц ресурсов затрачиваемых на изготовление второй продукции

P₃ - число единиц ресурсов затрачиваемых на изготовление третьей продукции

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

5) Критерий оптимальности:

- max

где f суммарная прибыль.

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

В произвольной форме линейная математическая модель или задача линейного программирования имеет вид (2.1.1) - (2.1.4).

Наиболее распространенный метод ее решения - симплекс метод. Для применения симплекс метода задачу следует записать в канонической форме.

В канонической форме записи все переменные неотрицательны, ограничениями являются уравнения, и требуется найти такие значения x _j, j=1,n, при которых целевая функция имеет максимум.

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

1) Если требуется найти минимум f, то, заменяя f на -f, переходят к задаче максимизации, так как min f= -max(-f).

2) Если ограничение содержит неравенство со знаком <=, то от него переходят к уравнению, добавляя в левую часть ограничения дополнительную неотрицательную переменную.

3) Если ограничение содержит неравенство со знаком >=, то от него переходят к уравнению, вычитая из левой части дополнительную неотрицательную переменную.

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

В нашей задаче используется первый случай:

Аналитическое решение

В настоящее время симплекс-метод используется для компьютерных расчетов, однако несложные примеры с применением симплекс-метода можно решать и вручную.

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

Следовательно, алгоритм поиска должен отвечать условиям:

при переходе от одного решения к другому должна сохраняться не отрицательность переменных;

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

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

Строим первую симплекс-таблицу.

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

Выбираем максимальное по модулю число из f строки, соответствующая переменная вводится в базис(p₂). Чтобы определить переменную, которую необходимо вывести из базиса, нужно найти отношения элемента b столбца к соответствующему элементу разрешающего столбца. Из всех отношений выбирают минимальное, соответствующая строка будет разрешающей(s₂).

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

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

.

Новую симплекс-таблицу проверяем на оптимальность. Так как в f строке есть отрицательный элемент, данный план не является оптимальным. Строим третью симплекс-таблицу по тому же правилу, что и вторую.

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

Из полученного плана следует, что для получения максимальной прибыли (1940 д.е.) необходимо производить 166 единиц второй продукции и 102 - первой продукции. Производство третьей продукции нерентабельно.

Анализ чувствительности решения

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

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

В опции параметры должен стоять флажок у линейной модели.

Рассмотрим решение нашей задачи. Ввод исходных данных показан на рис.1

Последовательность действий такова. Вводятся исходные данные и зависимости из математической модели. Эти зависимости представляют собой левые части ограничений и целевую функцию. Данная операция выполняется с помощью функции СУММПРОИЗ, где в первый массив вводятся коэффициенты соответствующего ограничения, а во второй - массив переменных.

Из меню Сервис откроем окно Поиск решений рис.2

.

В поле Установить целевую ячейку введем $Е$46.

Из группы Равной выберем переключатель - максимальному значению.

В поле области, Изменяя ячейки, введем ячейки с первоначальным значениями переменных - ($В$46:$D$46).

Нажав кнопку Добавить, откроем диалоговое окно Добавление ограничения (рис.3).

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

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

После нажатия кнопки ОК вновь появится диалоговое окно Поиск решения.

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

Если решение не найдено, окно выведет соответствующее сообщение.

Если решение найдено, выделим три типа отчетов, нажмем ОК, и результат решения задачи - на экране.

Анализ результатов и выводы

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

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

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

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

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

Список литературы