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

Решения задач методом линейного программирования
при помощи средств MS Excel симплекс-методом.
Двойственная задача.

Нижняя часть отчета содержит анализ ограничений. Аналогично верхней части таблицы столбцы «Окончательное Значение» и «Ограничение Правая сторона» содержат результат расчета модели и исходные данные соответственно, столбцы с увеличением и уменьшением показывают диапазон изменения правых сторон ограничений при котором данное решение сохраняется.

Как видно из таблицы «Сырье 2» находится в избытке, поэтому при добавлении сколь угодно много данного ресурса решение не изменится.

Результаты расчета теневых цен двойственной задачи показывает столбец «Тень
Цена». Как видно из данного примера наиболее ценным является единица
«Сырья 3», при увеличении запаса этого вида сырья на одну единицу, целевая функция возрастет на 6 ден. ед., при добавлении единицы первого сырья только на 4 ден. единицы, а поскольку второй вид сырья в избытке, то теневая цена этого ресурса равна 0.

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

Транспортная задача
Общий вид транспортной задачи представлен в таблице.
Модель содержит n пунктов отправления и m пунктов назначения. c ij представляет собой тариф по которому одна единица груза может быть перевезена из пункта отправления i в пункт назначения j. Переменные X
ij
–
показывают количество перевезенного груза из пункта отправления i в пункт назначения j.
Пункты отправления
Пункты назначения
Предложения
D
1
D
2
…
D
m
S
1
c
11
X
11
c
12
X
12
…
c
1m
X
1m
L
1
S
2
c
2
X
21
c
22
X
22
…
c
2m
X
2m
L
2
…
…
…
…
…
S
n c
n1
X
n1
c n2
X
n2
…
c nm
X
nm
L
n
Потребности
O
1
O
2
…
O
m

Транспортная задача
Очевидно, что целевая функция будет представлять собой сумму произведений объемов перевозки на тарифы и будет стремиться к минимуму в случае минимизации издержек на перевозку.
Ограничениями модели являются объемы потребностей и предложений, представленные в последнем столбце и строке таблицы.
Пункты отправления
Пункты назначения
Предложения
D
1
D
2
…
D
m
S
1
c
11
X
11
c
12
X
12
…
c
1m
X
1m
L
1
S
2
c
2
X
21
c
22
X
22
…
c
2m
X
2m
L
2
…
…
…
…
…
S
n c
n1
X
n1
c n2
X
n2
…
c nm
X
nm
L
n
Потребности
O
1
O
2
…
O
m

Транспортная задача
Существует два основных осложнения транспортных задач (1):

Несбалансированность.
Транспортная задача называется сбалансированной или закрытой, если совокупный объем потребностей равен совокупному объему предложения.
෍
????=1
????
????
????
= ෍
????=1
????
????
????
,
В случае отсутствия равенства задача считается несбалансированной или открытой.

В этом случае в модель вводится фиктивный пункт отправления или назначения.

Объем предложения или потребности фиктивного пункта равен модулю разницы между совокупным объемом потребности и предложения.

Тарифы на перевозку фиктивного пункта равны нулю, в случае минимизации целевой функции.

При расчете оптимального плана, потребность/предложение фиктивного пункта будет закрыто в первую очередь, что выведет излишки из дальнейшего расчета модели.

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

Транспортная задача
Решение транспортной задачи осуществляется в два этапа:
1. Заполнение опорного плана транспортной задачи.
Опорный план является аналогом допустимого решения в классической задаче линейного программирования и определяет решение, которое соответствует всем ограничениям модели, но не удовлетворяет условию оптимальности.
Для получения опорного плана могут быть использованы различные методы: северо-западного угла, минимального элемента, метод аппроксимации Фогеля.
2. Нахождение оптимального решения: при помощи специальных методов
(метод потенциалов, венгерский метод) состоит в итерационном переходе от опорного плана к оптимальному.

Решение транспортной задачи при помощи средств MS
Excel
Пример
У фирмы имеется четыре филиала и получает продукцию от трех поставщиков.
Известны: спрос на продукцию в каждом филиале, и наличие продукции у каждого из поставщиков. Также известны расходы на перевозку от каждого из поставщиков в каждый из филиалов (таблица). Требуется определить сколько продукции от каждого из поставщиков нужно перевезти в каждый из филиалов для минимизации транспортных расходов.
Поставщики
Потребители
Объем возможных поставок
А
B
C
D
Р
10 2
20 11 15
Q
12 7
9 20 25
R
4 14 16 18 10
Спрос у потребителя
5 15 15 15
Задача является сбалансированной совокупный возможных поставок равен совокупному спросу и составляет 50 ед.
Запрещенных маршрутов также нет, поэтому дополнительные преобразования модели не нужны.

Решение транспортной задачи при помощи средств MS
Excel
Организация исходных данных представлена на рисунке. Данные организованы в виде двух таблиц, в верхней представлены исходные данные с тарифами.
В нижней – переменные и целевая функция.

Решение транспортной задачи при помощи средств MS
Excel
В окне надстройки «Поиск решения» добавлены ссылки на переменные, ограничения и целевую функцию (рис.).

Решение транспортной задачи при помощи средств MS
Excel

Результат расчета представлен на рисунке.

В результате решения в нижней таблице появились объемы перевозок и целевая функция, значение которой составит 435 ден. ед.

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