Файл: Теория и методы принятия управленческих решенийСавченко Яна Валерьевна.pdf

Пример решения задачи методом линейного
программирования. Графический способ.
Для построения области допустимых решений необходимо неравенства заменить на равенства, провести прямые.
Затем необходимо определить необходимую полуплоскость: каждое неравенство делит плоскость на две полуплоскости, которые располагаются по обе стороны от прямой. Точки одной полуплоскости удовлетворяют неравенству, образуя допустимое пространство.
Как правило, используется какая-то «тестовая» точка, например, точка (0,0).
Проверяется удовлетворяет ли данная точка неравенству, если да – полуплоскость с тестовой точкой входит в искомую полуплоскость, если нет – допустимому пространству соответствует вторая полуплоскость.
Например, для графического отображения полуплоскости первого неравенства
3,5????
1
+ 1????
2
≤ 350, следует заменить его равенством 3,5????
1
+ 1????
2
= 350, которому на графике соответствует прямая.
На рисунке (предыдущий слайд) допустимые полуплоскости показаны стрелками.
Подобным образом строится вся система ограничений. Область допустимых решений, удовлетворяющая всей системе неравенств, выделена штриховкой.

Пример решения задачи методом линейного
программирования. Графический способ.
2. Поиск оптимального решения (1)
Для определения оптимального решения среди множества допустимых необходимо построить направляющий вектор (градиент), который показывает направление наибольшего возрастания целевой функции F(x). Как правило вектор строится из начала координат.
Вектор строится на основе значения переменных при целевой функции
????=(20, 10)
Линия уровня F(х)=С строится перпендикулярно градиенту. На рисунке линии уровня изображены линиями со штриховкой.
0 20 40 60 80 100 120 140 0
20 40 60 80 100 120 140 160 180 200
X2
X1 1
2 3
A

Пример решения задачи методом линейного
программирования. Графический способ.
2. Поиск оптимального решения (2)
Далее линия уровня перемещается параллельно самой себе по направлению градиента до тех пор, пока у неё не окажется одна общая точка с областью допустимых решений. Данная точка и будет решением модели.
В данном случае это точка A (80, 70).
Соответственно следует производить 80 т. краски для внутренних работ и 70 т. краски для наружных. При этом ежедневный доход составит, очевидно, 2300 ден. ед.
Подобное графическое решение очень трудно осуществить для модели с тремя переменными, поскольку область допустимых решений будет представлять собой многогранник в трехмерном пространстве.
0 20 40 60 80 100 120 140 0
50 100 150 200
X2
X1 1
2 3
A

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

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

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

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом
Исходные данные из формализованного описания задачи представлены на рисунке.
В ячейки, содержащие левые части системы неравенств ቐ
3,5????
1
+ 1????
2
≤ 350,
1????
1
+ 2????
2
≤ 240,
1????
1
+ 1????
2
≤ 150.
добавлены формулы.
Добавлена формула целевой функции
F(X) = 20 X
1
+10 X
2
→maх

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом

Решение осуществляется при помощи надстройки «Поиск решения», которая находится в пункте меню «Данные» (рис). В основном окне надстройки необходимо ввести ссылки на ячейки, содержащие целевую функцию, переменные решения, а также ввести ограничения.

При нажатии на кнопку «Найти решение» запускается алгоритм вычислений, итогом работы которого является окно «Результаты поиска решения».

В окне может содержаться одно из следующих сообщений: «Решение найдено. Все ограничения и условия оптимальности выполнены» либо
«Значения целевой ячейки не сходятся» или «Поиск не может найти решения» или «Условия линейной модели не выполняются».

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

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом.
Двойственная задача.

Для принятия управленческих решений, провести анализ полученных результатов не менее важно, чем получить результат.

Анализ в основном касается изменения параметров модели с целью поиска путей совершенствования результата.

В основном анализ полученного решения основывается на
чувствительности полученного результата к неточностям в ограничениях и целевой функции.

Как видно из рисунка на месте пустых ячеек с переменной и целевой функцией появляются значения. Также появились значения расхода сырья на производство ресурсов.

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

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом.
Двойственная задача.

Методически большая часть ответов на подобные вопросы может быть получена через решение так называемой двойственной
задачи, которая является «зеркальным отражением» исходной задачи, которая часто называется прямой и может быть из неё получена.

При решении задачи симплекс-методом решаются обе задачи –
прямая и двойственная.

Переменные двойственной задачи называют «теневыми» ценами, симплексными мультипликаторами или двойственными оценками.

Теневая цена ресурса показывает на сколько измениться целевая функция при добавлении единицы ресурса. Другими словами, она показывает внутреннюю ценность ресурсов каждого вида.

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом.
Двойственная задача.

Содержательная формулировка двойственной задачи, полученная из прямой для нашего примера будет выглядеть следующим образом:

Вместо того, чтобы производить продукцию, руководство решает распродать сырье, используемое при производстве краски.
Какие цены на сырье следует назначить, чтобы продать его было не менее выгодно, чем производить краску. Какова минимальная сумма, полученная за сырье в этом случае.

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом.
Двойственная задача.
На основании содержательной формулировки можно выделить основные компоненты математической модели:
1.
Переменные решения.
Поскольку в задаче используются три типа сырья, то очевидно, что переменных будет тоже три – Y
1
, Y
2
, Y
3
. Это теневые цены ресурсов каждого вида.
2. Целевая функция.
Минимальная сумма, полученная за сырье, которая определяет нижнюю границу цен на ресурсы.
G(Y) = 350 Y
1
+240 Y
2
+150 Y
3
→min
3. Ограничения.
Набор сырья для производства тонны краски одного вида по условию должен принести не меньший доход, чем производство краски.
ቊ
3,5????
1
+ 1????
2
+ 1????
3
≥ 20,
1????
1
+ 2????
2
+ 1????
3
≥ 10.
При этом все переменные, как и в исходной задаче неотрицательны: ????
1
≥ 0, ????
2
≥ 0, ????
3
≥ 0.

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

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом.
Двойственная задача.

Двойственная задача может быть решена подобно прямой задаче. При использовании информационных систем сразу решаются обе задачи.

В частности, при использовании надстройки «Поиск решения» в
MS Eхcel решение двойственной задачи содержится в отчёте
«Устойчивость». Открытие отчета возможно при появлении окна
«Результаты поиска решения»
(рис).

Решения задач методом линейного программирования при помощи
средств MS Excel симплекс-методом. Двойственная задача.

Общий вид отчета для задачи примера представлен на рисунке. Отчет разделен на две части. Верхняя часть отчета позволяет провести анализ чувствительности целевой функции.

Столбец «Окончательное Значение» содержит результаты расчета математической модели.

Столбец «Приведенн. Стоимость» содержит 0 для переменных, значения которых являются не нулевыми в оптимальном решении, как в данном случае. Если данная переменная является нулевой в оптимальном решении (не входит в оптимальный план), то в этом столбце содержится отрицательная величина, на которую нужно увеличить коэффициент при целевой функции, чтобы переменная приобрела ненулевое значение в оптимальном плане.

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом.
Двойственная задача.

Например, по результатам решения задачи получен результат, из которого следует, что производить необходимо только краску для внутренних работ. А в столбце «Приведенн. Стоимость» в строке «Х2 Краска для наружных работ» содержится «-5». Это значит, что коэффициент целевой функции, в данном случае доход от производства краски для наружных работ должен быть увеличен как минимум на 5 ден. ед., что должно привести к пересмотру ценовой политики.

Столбец «Целевая функция Коэффициент» как следует из названия содержит коэффициенты целевой функции исходной математической модели.

Столбцы «Допустимое Увеличение» и «Допустимое Уменьшение» содержат возможные изменения коэффициента целевой функции, при котором полученное оптимальное решение сохраняется.

В данном случае при изменении дохода от продажи 1 тонны краски для внутренних работ в диапазоне (20-10; 20+15) полученный оптимальный план ежедневного производства сохраняется. То же верно для диапазона изменений коэффициента целевой функции X
2
при изменении в диапазоне (5,715; 20).