Решение задач линейного программирования и анализ чувствительности с помощью MS Excel

Лабораторная работа №1

Тема: Решение задач линейного программирования и анализ чувствительности с помощью MS Excel.

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

Порядок выполнения работы:

1. Изучение теории и примера.
2. Построение математической модели проблемы в виде задачи линейного программирования.
3. Решение задачи с использованием надстройки Поиск решения пакета MS Excel.
4. Анализ чувствительности решения с использованием сценариев.
5. Составление отчёта по лабораторной работе, в котором представляется:

• формулировка индивидуального задания;

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

 

Теория

 

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

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

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

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

IV. Анализ математического решения проблемы и формирование управленческого решения. На этом этапе анализируется полученное математическое решение (выполняется так называемый анализ чувствительности), и затем на основе этого математического решения формируется управленческое решение.

После выполнения этих этапов следует этап реализации принятого решения.

 

I. Рассмотрим первый этап процесса принятия решения: анализ проблемы и формализация исходной проблемы. Этот этап можно рассматривать как первую стадию перехода от реального мира к компьютерному представлению проблемы.

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

♦ сформулировать проблему, по возможности максимально четко;

♦ сформулировать цели, которые должны быть достигнуты в результате реализации найденного решения;

♦ указать, что считать решением проблемы (решение должно гарантировать достижение целей);

♦ выявить и описать возможности достижения целей;

♦ выявить и описать факторы, от которых может зависеть решение проблемы;

♦ выявить и описать ограничения, препятствующие достижению целей;

♦ описать возможные альтернативные способы решения проблемы.

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

 

Пусть некий лакокрасочный завод «Олимп», в связи с изменившейся конъюнктурой рынка хочет разработать новый производственный план для выпуска краски типов А и Б, не трогая пока производство другой продукции. Допустим, что «Олимп» имеет месячный цикл производства. Таким образом, нужно определить, сколько в месяц следует производить краски типа А и сколько — типа Б. Ответ вроде бы простой: чем больше, тем лучше, конечно, с учетом производственных возможностей. Итак, вот первая цель — увеличить до максимума производство как продукции А, так и продукции Б. Допустим, производственные мощности позволяют выпускать в месяц суммарно 500 т краски всех типов. Вот появилось первое ограничение — общее количество краски типов А и Б не должно превышать 500 т.

Как видно, первую цель достичь можно, однако проблема остается плохо поставленной, поскольку дает неоднозначное решение. Поэтому вспомним, что всякое производство должно приносить прибыль. Теперь можно сформулировать вторую цель — производственный план должен приносить максимальную прибыль. Пусть одна тонна краски А приносит в среднем 2000 руб. прибыли, а одна тонна краски Б — 2500 руб. Здесь величины удельной прибыли (т.е. прибыли на одну тонну краски) являются факторами, которые влияют на конечную цель.

На этом шаге мы сделали огромное упрощение реальной ситуации, т. к. удельная прибыль любого производимого изделия зависит от многих факторов (конъюнктуры рынка, стоимости исходных материалов, себестоимости производства, уровня рентабельности и т. д.) и не является величиной постоянной даже на протяжении относительно небольшого временного промежутка. Тем более сложно предсказать и трудоемко подсчитать ее значение на будущий более-менее продолжительный период времени. Можно только оценить будущую удельную прибыль, да и то с определенной степенью точности. Пусть в нашем примере получены оценки будущей удельной прибыли производства краски типа А: от 1500 до 2300 руб., а краски типа Б: от 2100 до 3000 руб. Приведенные выше величины удельных прибылей 2000 и 2500 руб. являются наиболее вероятными ожидаемыми значениями. Далее именно эти величины примем за значения удельных прибылей, а возможные последствия от их неточного задания рассмотрим при проведении анализа полученного решения.

Очевидно, что для достижения второй цели надо производить только краску типа Б и забыть о краске типа А. Однако отдел маркетинга требует, чтобы краски типа А производилось не менее 200 т в месяц, поскольку есть договоры на такое количество, а краску типа Б нельзя производить более 150 т, поскольку большее количество трудно реализовать. Итак, имеем еще два ограничения: произведенное количество краски А должно быть не меньше 200 т, а краски Б — не более 150 т.

При таких ограничениях даже начальник производства составит план: надо производить 350 т краски А и 150 т краски Б. Этот план учитывает только ограничения по производственным мощностям и маркетинговые ограничения. Но для производства любой продукции нужны еще исходные материалы. Пусть на изготовление красок А и Б необходимо сырье трех видов согласно следующей таблице.

 

	Краска А, кг	Краска Б, кг	Месячный запас, т
Сырье 1	50	100	50
Сырье 2	70	80	30
Сырье 3	40	70	25

 

В этой таблице показано, сколько и какого сырья необходимо для производства одной тонны краски А и одной тонны краски Б, а также величины месячных запасов этого сырья. Очевидно, что общее количество сырья, используемого для производства краски, не должно превышать их месячные запасы. Таким образом, имеем еще три ограничения — по одному для каждого типа сырья. С учетом этих ограничений производственный план «на пальцах» уже не подсчитаешь.

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

Итак, что же мы имеем после небольшого анализа проблемы.

 

♦ Постановка проблемы: разработать производственный план, который максимизировал бы прибыль с учетом всех видов ограничений.

♦ Цель: максимизировать прибыль.

♦ Решение: количество тонн краски А и Б, производимых в месяц.

♦ Факторы, от которых зависит решение: значения удельной прибыли каждого типа краски, предельное число производимой краски, предельные числа производимых красок типов А и Б (маркетинговые ограничения), количества сырья (необходимых для производства одной тонны краски), значения запасов сырья (всего 14 факторов).

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

♦ Ограничения: на предельное общее количество производимой краски, на предельные количества производимых красок А и Б в отдельности, на предельные количества используемого сырья (всего 6 ограничений).

 

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

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

 

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

1. Переменные, значения которых необходимо вычислить (это переменные решения из формальной модели).

2. Целевая функция — это цель, записанная математически в виде функции от переменных. Обязательно указывается, что необходимо сделать с этой функцией для решения проблемы: найти ее максимум, минимум или конкретное заданное значение.

3. Ограничения — записанные математически ограничения из формальной модели.

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

В нашем примере обозначим через х1 и х2 переменные, которые определяют месячные объемы производства краски (в тоннах) типа А и Б соответственно. Напомним, что 1 тонна краски А приносит прибыль 2000 руб., а 1 тонна краски Б — 2500 руб. Тогда суммарная прибыль z при производстве х1 тонн краски А и х2 тонн краски Б составит

 

z = 2000*х1 + 2500*х2 (руб.)

 

Это и есть целевая функция, которую необходимо максимизировать.

Теперь запишем ограничения. Первое ограничение говорит о том, что суммарный объем производства краски обоих типов не должен превышать 500 т. Это запишется так: х1 + х2 £ 500. Маркетинговые ограничения записываются просто: х1 ³ 200 и х2 £ 150. Теперь надо записать ограничения па сырье. Напомним, что сырья 1 на производство 1 т краски А расходуется 0,05 т (50 кг) и 0,1 т (100 кг) на производство 1 т краски Б. Таким образом, всего на производство x1, тонн краски А и x2 тонн краски Б потребуется 0,05*х1 + 0,1*х2 тонн сырья 1. Эта величина не должна превышать 50 т. Отсюда получаем ограничение: 0,05*х1 + 0,1*х2 £ 50. Подобным способом получаем еще два ограничения на сырье 2 и сырье 3: 0,07*x1 + 0,08*x2 £ 30 и 0,04*x1 + 0,07*x2 £ 25. Еще одно неявное ограничение состоит в том, что переменные х1 и х2 должны быть неотрицательными (если не вдаваться в мистику, то отрицательные объемы производства физически просто невозможны). Это ограничение называется условием неотрицательности переменных и записывается так: х1 ³ 0 и х2 ³ 0. Однако заметим, что условие неотрицательности для переменной х1 здесь излишне, поскольку имеем более сильное ограничение х1 ³ 200. Поэтому неравенство х1 ³ 0 исключаем из списка ограничений.

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

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