|
|
|
|
|
|
Превышение затрат на ресурсы над
ценой реал. (возможный убыток от производства продукции)
|
Объективно обусловленные оценки
ресурсов (теневые, условные, скрытые цены ресурсов)
|
Компоненты оптимального решения
ДЗЛП
|
Экономический смысл переменных:
x1*,
x2*,
x3*-основные
переменные - оптимальный план производства;
x4*,x5,
x6*-
дополнительные переменные - остатки ресурсов;
y1,y2,y3-основные
переменные - скрытые цены;
y4,y5,y6-дополнительные
переменны - превышение затрат на ресурсы над ценой реализации (возможный убыток
от производства продукции).
Анализ решения ПЗЛП
Подставим оптимальные значения переменных x*в
исходную систему ограничений ПЗЛП:
) 3×х1 + 3×х2
+ 2×х3£
3
×0+ 3×1
+ 2×0
= 3
=3, следовательно, х4 = 0, ресурс Р1
используется полностью;
) 2×х1 + 4×х2
+ х3£ 10
×0+ 4×1
+ 1×0
= 4
< 10, следовательно, х5 = 6,
ресурс Р2 используется не полностью;
) 3×х1 + х2
+ 2×х3£
4
×0 + 1×1
+ 2×0
= 1
< 4, следовательно, х4 = 3, ресурс
Р3 используется не полностью.
Анализ решения ДЗЛП
Подставим оптимальные значения переменных у*в
исходную систему ограничений ПЗЛП:
1) 3×у1 + 2×у2
+ 3×у3³
3
3×(4/3) + 2×0
+ 3×0
= 4
³ 3, на 1, следовательно, у4 = 1,
убытки от производства первого вида продукции П1, которая не вошла в
оптимальный план производства, в случае ее производства будут составлять 1 ден.
ед. с каждого изделия первого вида;
) 3×у1 + 4×у2
+ у3³ 4
×(4/3) + 4×0
+ 1×0
= 4
= 4, следовательно, у5 = 0, убытки от
производства второго вида продукции П2, которая вошла в оптимальный
план производства отсутствуют;
) 2×у1 + у2
+ 2×у3³
1
×(4/3) + 1×0
+ 2×0
= 8/3
/3 ³ 1 на 5/3,
следовательно, у6 = 5/3, убытки от производства третьего вида продукции
П3, которая не вошла в оптимальный план производства, в случае ее
производства будут составлять 5/3 ден. ед. с каждого изделия третьего вида.
Рассчитаем границы изменения дефицитных
ресурсов, в пределах которых не изменится структура оптимального плана.
Ресурсы, которые используются полностью, называются дефицитными. Признаком
дефицитности ресурсов является отличие от нуля соответствующей данному ресурсу
двойственной переменной и равенство нулю соответствующей дополнительной
переменной.
В рассматриваемом случае дефицитным является
ресурс Р1.
Для исследования границ изменения первого вида
ресурса Р1 из последней симплекс-таблицы составляют систему
неравенств для базисных переменных ПЗЛП, используя элементы из столбца
свободных членов bi
и столбца, соответствующего переменной у1. Коэффициенты из столбца
«у1» умножают на искомое изменение Db1запаса
ресурса Р1:
Þ.
Учитывая, что b1 = 3,
допустимый интервал изменения границ первого вида ресурса составит или .
Проверим границы с помощью
вычислительного эксперимента:
Зададим b1 = 7,48:
Рисунок 1 - Прямая задача линейного программирования
Структура ПЗЛП не изменилась
Рисунок 2 - Двойственная задача линейного
программирования
Структура ДЗЛП не изменилась.
Зададим b1
=
0,02:
Рисунок 3 - Прямая задача линейного
программирования
Структура решения ПЗЛП не изменилась
Рисунок 4 - Двойственная задача линейного
программирования
Структура ДЗЛП не изменилась.
Зададим b1
=
7,51:
Рисунок 5 - Прямая задача линейного
программирования
Получили новую структуру оптимального плана
прямой задачи: (х1=0,01; х2=2,5; x3=0)
Рисунок 6 - Двойственная задача линейного
программирования
Получили новую структуру оптимального плана
ДЗЛП.
Можно сделать вывод о правильности установленных
границ изменения ресурса Р1: 0≤ b2
≤
15/2.
Значение остатка недефицитных ресурсов
определяется значением соответствующей дополнительной переменной.
В рассматриваемом случае не
дефицитными являются ресурсы Р2 и Р3. Оптимальный план
производства не изменится при .
Проверим границы с помощью
вычислительного эксперимента:
Зададим b2 = 3,98:
Рисунок 7 - Двойственная задача
линейного программирования
Получили новый оптимальный план
решения ДЗЛП.
Зададим b2 = 4,02:
Рисунок 8 - Прямая задача линейного
программирования
Оптимальный план решения ПЗЛП не изменился
Рисунок 9 - Двойственная задача линейного
программирования
Оптимальный план решения ДЗЛП не изменился.
Можно сделать вывод о правильности установления
границы изменения ресурса Р2: b2
≥
4.
Оптимальный план производства для не
дефицитного ресурса Р3 не изменится при .
Проверим границы с помощью
вычислительного эксперимента:
Зададим b3 = 0,98:
Рисунок 10 - Двойственная задача
линейного программирования
Получили новый оптимальный план
решения ДЗЛП.
Рисунок 11 - Прямая задача линейного
программирования
Оптимальный план решения ПЗЛП не изменился.
Рисунок 12 - Двойственная задача линейного
программирования
Оптимальный план решения ДЗЛП не изменился.
Можно сделать вывод о правильности установления
границы изменения ресурса Р3: b3
≥
1.
Рассчитаем границы изменения цены изделия,
попавших в оптимальный план производства, в пределах которых оптимальный план
не изменится.
В план производства вошел второй вид продукции П2.
Для второго вида продукции П2,
которая попала в план производства, из последней симплекс-таблицы составляют
систему неравенств для базисных переменных ДЗЛП (они соответствуют свободным
переменным ПЗЛП), используя элементы из строки Dj
и строки, соответствующей переменной х2. Коэффициенты из строки «х2»
умножают на искомое изменение Dс1цены продукции П2
Þ.
Учитывая цену второго вида продукции
с2 = 4, интервал устойчивости изменения цен составит или .
Проверим границы с помощью
вычислительного эксперимента:
Зададим c2
=
2,98:
Рисунок 13 - Прямая задача линейного
программирования
Получили новый оптимальный план решения ПЗЛП.
Зададим c2
=
3,02:
Рисунок 14 - Прямая задача линейного
программирования
Структура оптимального плана решения ПЗЛП не
изменилась.
Рисунок 15 - Двойственная задача линейного
программирования
Структура решения ДЗЛП не изменилась.
Можно сделать вывод о правильности
определения границы изменения цены с2: с2 3.
Для видов продукции, не попавших в
оптимальный план производства, исследование допустимых границ изменения цен не
проводится.
Определим величины ∆bs ресурса Рs,
введением которого в производство можно компенсировать убыток и сохранить
максимальный доход на прежнем уровне (ресурсы предполагаются взаимно
заменяемыми), получаемый при исключении из производства ∆br единиц
ресурса Рr.
В рассматриваемом случае: r = 1; ∆br = 0,2; s = 2.
Для взаимозаменяемых ресурсов
(коэффициент взаимозаменяемости >0, но отличен от бесконечности)
количество ресурса ∆biвида i,
необходимое для замены выбывающего количества ∆bkресурса k,
определяется по формуле:
.
Таким образом, .
Следовательно, замена первого ресурса невозможна.
Оценим целесообразность приобретения
∆bk единиц
ресурса Рk по цене сk за единицу.
Для оценки целесообразности приобретения дополнительного количества ресурса ∆biвида i по цене сk необходимо
сравнить предлагаемую цену с рассчитанной ранее теневой ценой этого ресурса .
Приобретение дополнительного количества ресурса целесообразно, если выполняется
условие непревышения новой цены над теневой ценой
сk£.
В противном случае приобретение
дополнительного количества ресурса нецелесообразно.
В рассматриваемом случае: ∆bk = 0,2; k = 3, ck = 15.
Поскольку < 15, то
приобретение дополнительного количества ресурса не целесообразно.
Оценим целесообразность выпуска
нового изделия П4, на единицу которого ресурсы Р1, Р2,
Р3 расходуются в количествах a14, a24, a34 единиц, а
цена единицы изделия составляет с4 денежных единиц. Включение
дополнительного вида продукции n+1 в план производства
целесообразно, если соотношение дополнительных затрат и цены реализации
дополнительного вида продукции удовлетворяет следующему условию
.
Расчет затрат осуществим по формуле
ден. ед.
Учитывая, что затраты на ресурсы для
производства продукции третьего вида меньше цены реализации с4 = 35
ден. ед., то включение ее в план производства целесообразно.
Решим прямую и двойственную задачу
линейного программирования в среде MicrosoftExсel. Решение
задач линейного программирования с помощью программы MicrosoftExcel
осуществляется через меню Сервис и вкладку Поиск решения. Если данная вкладка
не установлена, то ее установка осуществляется следующими действиями:
. Войти в меню Сервис.
. Выбрать команду Надстройки.
. В появившемся диалоговом окне
Надстройки установить флажок напротив строки Поиск решения и нажать кнопку ОК.
После произведенных действий в меню
Сервис появится команда Поиск решения.
Прежде чем начать выполнение команды
Поиск решения следует провести подготовительные действия по введению данных
задания в таблицу.
Выбираем ячейку для введения целевой
функции (например, ячейку А1). При записи целевой функции в ячейку А1 вместо
значений переменной хi подставляют
названия пустых ячеек, в которых хотим получить искомые значения х1,
х2, х3, например, С1, С2, С3. Тогда запись целевой
функции в ячейке А1 будет иметь вид = 3*С1+4*С2+С3. После введения целевой
функции в ячейку А1 нажимаем клавишу «Enter», в ячейке
А1 отобразится 0.
Условия ограничений вписываем в
ячейки столбца В. В выбранные ячейки записываются только левые части неравенств
в следующем виде:
Ячейка В1: =3*С1+3*С2+2*С3 «Enter»
Ячейка В2: =2*С1+4*С2+С3 «Enter»
Ячейка В3: =3*С1+С2+2*С3 «Enter»
Ячейка В4: =С1 «Enter»
Ячейка В5: =С2 «Enter»
Ячейка В6: =С3 «Enter»
Через меню Сервис/Поиск решения
открыть окно поиска решения:
Рисунок 16 - Решение задачи в среде MicrosoftExсel
В поле ввода Установить целевую ячейку вводим
ссылку на ячейку А1.
В поле ввода Изменяя ячейки укажем ссылки на
ячейки С1:С3.
Данная операция осуществляется следующими
действиями:
.Щелкнуть левой кнопкой мыши в поле ввода
Изменяя ячейки.
. Выделить при помощи левой кнопки мыши ячейки,
начиная с С1 и до ячейки С3(поле ввода изменения ячейки должно автоматически
заполниться).
В поле ввода Ограничения введем ограничения,
соответствующие ячейкам В1, В2, В3. Ввод значений осуществляется в следующем
порядке:
.Нажать кнопку Добавить. Появится диалоговое
окно Добавление ограничения.
. Для каждого логического выражения, находящихся
в ячейках В1, В2, В3 вводим свое условие и свое ограничение, последовательно
нажимая кнопку Добавить. По окончании нажать кнопку ОК.
Рисунок 17 - Решение задачи в среде MicrosoftExсel
. Должен появиться следующий результат:
Рисунок 18 - Результат решения задачи в среде MicrosoftExсel
Для поиска максимального значения устанавливаем
флажок.
Для осуществления вычислений нажмем кнопку
Выполнить. Откроется окно диалога Результаты поиска решения. В окне Тип отчета
выберем строку Результаты и нажмем кнопку ОК. Получим следующие результаты:
В ячейке А1отражено максимально возможное
значение функции при заданных условиях 4.
В столбце В отражены значения логических
выражений, удовлетворяющих исходным ограничениям.
х1 + 3х2 +2х3 =
3
х1 + 4х2 + х3 =
4
х1 + х2 + 2х3 =
1
В столбце С отражены значения переменных, при
которых значение функции принимает максимальную величину:
х1 = 0; х2 = 1; х3
= 0.
На листе «Отчет по результатам» появится
следующая информация, отражающая результаты расчета:
Рисунок 19 - Результат решения задачи в среде MicrosoftExсel
все действия для двойственной задачи, получим
следующий отчет по результатам:
Рисунок 20 - Результат решения задачи в среде MicrosoftExсel
симплекс-метод
. Выражение базисных переменных ПЗЛП и ДЗЛП
через свободные.
Выразим базисные переменные ПЗЛП и ДЗЛП через
свободные:
.Определение исходного решения
прямой и двойственной задач и проверка его на оптимальность.
Для этого заполняют симплекс-таблицу
двойственного симплекс-метода. Таблица имеет два входа: по переменным прямой
задачи xjи по
переменным двойственной задачи yi. Базисные
переменные ПЗЛП записывают в столбце xбаз, а
свободные переменные в строке xсв со знаком «-». Базисные переменные ДЗЛП
записывают в строке убаз, а свободные переменные в столбце усв.
Строки таблицы 1-го шага (верхние
части клеток) заполняют по данным системы ограничений и целевой функции прямой
задачи. Столбцы таблицы 1-го шага (верхние части клеток) заполняют по данным
системы ограничений и целевой функции двойственной задачи. Значение целевой
функции равно нулю, поскольку базисные переменные не входят в выражение целевой
функции.
Решение является оптимальным, если в
строке и столбце bi нет
отрицательных элементов. В противном случае следует провести изменения в
базисных переменных.
Симплексная таблица двойственного
симплекс-метода для варианта 40 имеет следующий вид:
Таблица 12 - Шаг двойственного симплекс-метода
Решение ПЗЛП выписывается по
строкам, значения базисных переменных берутся из столбца bi, если
переменная с соответствующим индексом не входит в базис, то ее значение равно
нулю: = (0, 0, 0,
3, 10, 4), = 0.
Решение ДЗЛП выписывается по
столбцам, значения базисных переменных берутся из строки cj, если
переменная с соответствующим индексом не входит в базис, то ее значение равно
нулю: = (0, 0, 0,
-3, -4, -1), = 0.
Данное решение не является
оптимальным, поскольку решение не допустимое (не выполнено условие
неотрицательности переменных), ему соответствуют отрицательные элементы в
строке . Поэтому
следует провести замену переменных в базисе.
Для выбора разрешающей строки
находят отрицательный элемент в строке .В столбце над этим найденным
элементом выбирают любой положительный элемент, эта строка - разрешающая.
Если в столбце над найденным
элементом нет положительных элементов, то ПЗЛП не имеет смысла (целевая функция
не ограничена в области допустимых решений), а ДЗЛП не имеет решения.
В рассматриваемом примере в строке три
отрицательных элемента.
Таблица 13 - Шаг двойственного симплекс-метода
Можно выбрать любой из них, поэтому выбираем «-1»,
а над ним выбираем элемент из второй строки «2». Следовательно, первая строка -
разрешающая (выделена жирным шрифтом).
Выберем разрешающий столбец.
Элементы строкиделят на
соответствующие элементы разрешающей строки под переменными. Из полученных
отношений выбирают максимальное отрицательное отношение, этот столбец -
разрешающий (максимальным из отрицательных отношений может быть отношение -
отрицательный ноль).
Если среди полученных отношений нет
отрицательных, то ПЗЛП не имеет решения, ДЗЛП не имеет смысла или решения.
На пересечении разрешающей строки и
разрешающего столбца находится разрешающий элемент.
В рассматриваемом примере
максимальным среди отношений элементов из строкии элементов разрешающей строки
является отношение в третьем столбце . В качестве разрешающего выберем
третий столбец (выделен жирным шрифтом).
Таблица 14 - Шаг двойственного симплекс-метода
Разрешающим элементом является элемент «2»,
который стоит на пересечении первой строки и третьего столбца.
Под разрешающим элементом всегда ставят «1».
Остальные элементы разрешающей строки переписываются без изменений, а остальные
элементы разрешающего столбца переписываются с противоположным знаком.
Заполнение нижних частей клеток для разрешающей
строки и разрешающего столбца варианта 44:
Таблица 15 - Шаг двойственного симплекс-метода
Остальные элементы таблицы в нижних частях
клеток находят по правилу прямоугольника: для искомого элемента из нижней части
клетки элемент из верхней части этой же клетки умножают на разрешающий элемент
и из этого произведения вычитают произведение элементов, расположенных на
противоположной диагонали прямоугольника, образуемого искомым и разрешающим
элементами (все элементы из верхних клеток).
Заполнение нижних частей для остальных клеток
варианта 44:
на пересечении второй строки и первого столбца:
Рис. 2×2 -
3×1
= 1;
клетка на пересечении третьей строки и первого
столбца:
Рис. 2×3 -
2×3
= 0;
клетка на пересечении четвертой строки и первого
столбца:
Рис. - 3×2
-
3×(-1)
= -3;
клетка на пересечении второй строки и второго
столбца:
Рис. 4×2 -
3×1
= 5;
клетка на пересечении третьей строки и второго
столбца:
Рис. 2×1 -
3×2
= -4;
клетка на пересечении четвертой строки и второго
столбца:
-4×2 -
(-1)×3
= -5;
клетка на пересечении второй строки и четвертого
столбца:
Рис.×10 -
1×3
= 17;
клетка на пересечении третьей строки и
четвертого столбца:
Рис.×4 -
2×3
= 2;
клетка на пересечении четвертой строки и
четвертого столбца:
Рис. 0×2 -
(-1)×3=
3.
Таким образом, получаем следующую таблицу:
Таблица 16 - Шаг двойственного симплекс-метода
Изменяют базисные переменные: меняют местами
переменные из разрешающей строки и разрешающего столбца. Элементы из нижних
клеток предыдущей симплекс-таблицы делят на верхний разрешающий элемент и
записывают на соответствующие места в верхние клетки новой симплекс-таблицы.
Если в новой таблице в строке есть
отрицательные элементы, то следует сделать следующий шаг симплекс-метода.
(Нецелесообразно выбирать за разрешающую строку - те же строки, что и на
предыдущих шагах).
Если в новой таблице в строке нет отрицательных
элементов, а в столбце свободных членов остались отрицательные элементы, то
строка с отрицательным значением выбирается за разрешающую, и
выполняется следующий шаг симплекс-метода.
Если в строке есть
нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для
нахождения альтернативного решения выполняется еще один шаг симплекс-метода:
Столбец с нулевым элементом в строке выбирается за разрешающий. Находят
неотрицательные отношения столбца свободных членов к соответствующим элементам
разрешающего столбца. Из полученных отношений выбирают минимальное
неотрицательное отношение - это разрешающая строка, разрешающий элемент найден.
Затем выполняют еще один шаг симплекс-метода.
Если в столбце есть
нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для
нахождения альтернативного решения выполняется еще один шаг симплекс-метода.
При этом строка с нулевым элементом в столбце выбирается за разрешающую.
Переходим к следующей
симплекс-таблице. При этом в первую строку включается пара переменных х3,
у6, соответствующих разрешающему столбцу, а в третий столбец
вводится пара переменных х4, у1, соответствующая
разрешающей строке. Верхние части клеток заполняются элементами, полученными в
результате деления соответствующих (стоящих на аналогичном месте) элементов из
предыдущей таблицы в нижних частях клеток на разрешающий элемент «2»:
Таблица 17 - Шаг двойственного
симплекс-метода
Решение ПЗЛП на втором шаге
двойственного симплекс-метода также выписывается по строкам: = (0, 0,
3/2, 0, 17/2, 1), = 3/2,
решение ДЗЛП выписывается по столбцам: = (1/2, 0, 0, -3/2, -5/2, 0), = 3/2.
Данное решение также не оптимальное, поскольку в строке еще
остались отрицательные элементы. Необходимо продолжить поиск оптимального
решения.
В строке выбираем
отрицательный элемент «-3/2». Над
ним выбираем положительный, предпочтительнее «3/2», следовательно, первая
строка - разрешающая (выделена жирным шрифтом):
Таблица 18 - Шаг двойственного симплекс-метода
Находим максимальное отношение среди
отношений элементов в строке целевой функции к соответствующим элементам
разрешающей строки
. Разрешающий столбец - первый,
поскольку максимальное отношение соответствует ему.
Разрешающий элемент «3/2» находится
на пересечении разрешающей строки и разрешающего столбца.
Заполнение нижних частей клеток
осуществляется аналогично рассмотренному выше. Получаем следующую таблицу:
Таблица 19 - Шаг двойственного
симплекс-метода
Переходим к следующей симплекс-таблице. При этом
в первую строку включается пара переменных х1, у4,
соответствующих разрешающему столбцу, а в первый столбец вводится пара
переменных х3, у6, соответствующая разрешающей строке.
Верхние части клеток заполняются элементами, полученными в результате деления
соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы
в нижних частях клеток на разрешающий элемент «3/2»:
Таблица 20 - Шаг двойственного симплекс-метода
Решение ПЗЛП на третьем шаге
двойственного симплекс-метода также выписывается по строкам: = (1, 0, 0,
0, 8, 1), = 3, решение
ДЗЛП выписывается по столбцам: = (1, 0, 0, 0, -1, 1), = 3. Данное
решение также не оптимальное, поскольку в строке еще остался отрицательный элемент.
Необходимо продолжить поиск оптимального решения.
В строке выбираем
отрицательный элемент «-1». Над ним
выбираем положительный, предпочтительнее «1», следовательно, первая строка -
разрешающая (выделена жирным шрифтом):
Таблица 21 - Шаг двойственного симплекс-метода
Находим максимальное отношение среди
отношений элементов в строке целевой функции к соответствующим элементам
разрешающей строки. Разрешающий столбец - второй, поскольку максимальное
отношение соответствует ему.
Разрешающий элемент «1» находится на
пересечении разрешающей строки и разрешающего столбца.
Заполнение нижних частей клеток
осуществляется аналогично рассмотренному выше. Получаем следующую таблицу:
Таблица 22 - Шаг двойственного
симплекс-метода
Перейдем к следующей
симплекс-таблице. При этом в первую строку включается пара переменных х2,
у5, соответствующих разрешающему столбцу, а во второй столбец
вводится пара переменных х1, у4, соответствующая
разрешающей строке. Клетки следующей таблицы заполняются элементами,
полученными в результате деления соответствующих элементов из предыдущей
таблицы в нижних частях клеток на разрешающий элемент «1». Поскольку в нижних
частях клеток таблицы все элементы положительные и разрешающий элемент также
положительный, то в следующей таблице будет получено оптимальное решение и нет
необходимости делить на две части клетки в последней таблице.
Таблица 23 - Шаг двойственного
симплекс-метода
Оптимальное решение ПЗЛП: = (0, 1, 0,
0, 6, 3), = 4,
оптимальное решение ДЗЛП: = (4/3, 0,
0, 1, 0,5/3), = 4.
Данное решение аналогично решению,
полученному в соответствии с методом одновременного решения пары
взаимодвойственных задач для ПЗЛП и совпадает с решением ДЗЛП в отношении
значения целевой функции.
3. Метод потенциалов решения
транспортной задачи
Начальное решение транспортной задачи
Имеется 4 оптовых склада и 4 магазина.
A1, A2, A3,
A4 - склады.1
= 19, a2
= 19, a3
= 19, a4
= 19 - соответственно, запасы на складах.
B1,
B2,
B3,
B4
- магазины.
b1
= 15, b2
= 15, b3
= 23, b4
= 23 - соответственно, потребности магазинов.
Найдем исходное опорное решение по методу
минимальной стоимости. Для этого заполним распределительную таблицу:
Таблица 24 - Транспортная задача
Таблица 25 - Транспортная задача
Таким образом, все поставки распределены,
получено начальное решение транспортной задачи:
Рис.
fo(xo)
= 12·19 + 16·15 + 15·4 + 16·19 + 10·15 + 10·4 = 1022
Количество ненулевых элементов 6 < 7 ,
решение вырожденное. Введем значимый ноль (Õ).
Решение транспортной задачи методом потенциалов
Таблица 26 - Транспортная задача
Вычисляем оценки свободных клеток:
D11 = c11
-
u1
-v1
= 21- 0 - 13= 8 > 0,
D12
= c12- u1 - v2 = 17 - 0 -11 = 6 >0,
D14
= c14 - u1 - v4 = 24 - 0 - 11= 13 >0,
D22
= c22 - u2 - v2 = 19 - 3 - 11 = 5 > 0,
D24
= c24 - u2 - v4 = 19 - 3 -11 = 5 > 0,
D31
= c31 - u3 - v1 = 17 - 5 - 13= - 1< 0,
D32
= c32 - u3 - v2 = 15 - 5 - 11= -1< 0,
D33
= c33 - u3 - v3 = 24 - 5- 12 = 7 >0,
D41 = c41
-
u4
- v1
= 13+1-13 = 1 >0.
В распределительной таблице оценки клеток
проставлены в нижнем левом углу в скобках:
Таблица 27 - Транспортная задача
Переход к следующему опорному решению.
Выбираем клетку, от которой начнем
построение цикла перераспределения поставок, по правилу . У вершин
цикла с соответствующими значениями поставок по правилу чередования знаков
ставим знаки (+) и (-).У вершин со знаком (-) выбираем минимальный груз q = min[15,19] = 15.
Рис.
Проверка решения Х1 на оптимальность
выполняется аналогично предыдущему шагу.
Таблица 28 - Транспортная задача
У вершин со знаком (-) выбираем минимальный груз
q
= min[15,4,0] = 0.
Рис.
Проверка решения Х2 на оптимальность.
Результаты расчета представлены в
распределительной таблице:
Таблица 29 - Транспортная задача
Все оценки свободных клеток положительные,
следовательно, решение оптимально. Значение целевой функции:
F*(x2)
= 12·19 + 16·15 + 15·4 + 15·15 + 16·4 + 10·19 = 1007
Таким образом, решение транспортной задачи:
Рис.
Решение транспортной задачи в среде Microsoft
Exсel
Ввод исходных данных (в области C3:F6
- тарифы на перевозку продукции; в столбце G3:G6
- запасы; в ячейках С7, D7,
E7, F7
- потребности).
В области решения в ячейке G10
введите формулу стоимости перевозок:
=СУММПРОИЗВ(C12:F15;C3:F6).
Для этого необходимо нажать на значок f(x)
на панели инструментов, выбрать математическую функцию СУММПРОИЗВ и ввести два
массива C12:F15 и C3:F6.
Далее в области C12:F15
проставьте любое первоначальное решение (например, единицы)/
В ячейке С16 записывается формула: =СУММ(C12:C14),
т.е. сумма значений по столбцу (можно выделить значения столбца и нажать на
знак автосуммы Σ на панели
инструментов). Аналогично в D16,
E16, F16.
Автоматически суммируются значения по столбцам.
В ячейке G12
записывается формула: =СУММ(C12:F12),
т.е. сумма значений по строке (можно выделить значения строки и нажать на знак
автосуммы Σ на панели
инструментов). Аналогично в G13,
G14, G15.
Автоматически суммируются значения по строкам:
Рисунок 21 - Поиск оптимального решения
Далее выполняют команду Поиск решения (вкладка
Сервис или Данные).
Установить целевую ячейку G10,
равной минимальному значению.
В поле ввода Изменяя ячейки установить C12:F15
В поле ввода Ограничения установить C12:F15
>= 0
C16:E16
= C7:E7
G12:G15
= G3:G6
Рисунок 22 - Поиск оптимального решения
Вычисления производятся при нажатии кнопки Найти
решение. Получим решение задачи:
Рисунок 23 - Поиск оптимального решения
4. Решение игры
Рассмотрим игру, представленную платежной
матрицей:
a
¹ b.
Так как игра не имеет седловой
точки, то она не решается в чистых стратегиях.
Все элементы четвертого столбца не превышают
элементов первого столбца. Следовательно, стратегия, соответствующая первому
столбцу платежной матрицы заведомо невыгодна для второго игрока, и первый
столбец можно исключить. Все элементы второго столбца не превышают элементов
пятого столбца. Следовательно, стратегия, соответствующая пятому столбцу платежной
матрицы заведомо невыгодна для второго игрока, и пятый столбец можно исключить.
Получаем матрицу из трех столбцов:
Решим упрощенную игру с помощью
графического доминирования.
Рисунок 24 - Геометрическая
интерпретация исходной игры
хлебопекарный игра отрасль
С помощью геометрического доминирования исходная
игра сведена к игре размерности [2х2]
Решим
полученную игру аналитическим методом:
Проверка:
V(H)=x*HY*T=
ЗЛП для игрока 1:
min [ f0 (х)=х1+х2]
ЗЛП для игрока
2:
max [ g0(y)=y1+y2+y3+y4+y5]
Найдем решение задачи линейного программирования
для первого игрока с помощью программы Microsoft
Excel.
Введем целевую функцию в ячейку А1, ограничения
в ячейки В1 - В5, а искомые значения x
в ячейки С1 - С2. Далее с помощью поиска решений найдем оптимальное решения.
Получим следующее:
Рисунок 25 - Поиск оптимального решения
Найдем решение задачи линейного программирования
для второго игрока с помощью программы Microsoft
Excel.
Введем целевую функцию в ячейку А1, ограничения
в ячейки В1 - В2, а искомые значения y
в ячейки С1 - С5. Далее с помощью поиска решений найдем оптимальное решения.
Получим следующее:
Рисунок 26 - Поиск оптимального решения
X=(1/7; 1/7); Y=(0;
1/7; 0; 1/7; 0); ,
g0(y*)=f0(x*)=2/7.
Тогда
V(H)=1/(2/7)=7/2;
X*1=(1/7)/(2/7)=1/2;
X*2=(1/7)/(2/7)=1/2;
Y*1=0/(2/7)=0;
Y*2=(1/7)/(2/7)=1/2;
Y*3=0/(2/7)=0;
Y*4=(1/7)/(2/7)=1/2;
Y*5=0/(2/7)=0;
Следовательно:
Х= (1/2; 1/2),
Y= (0; 1/2; 0; 1/2;
0).
V(H)
= 7/2
5. Задача динамического
программирования
На развитие трех предприятий
выделено В млн. руб. Известна эффективность капитальных вложений xi в каждое j-е
предприятие, заданная таблично значением нелинейной функции fj(xi), где ,, n -
количество предприятий, m - количество возможных сумм
капитальных вложений.
Необходимо распределить выделенные
средства между предприятиями таким образом, чтобы получить максимальный
суммарный доход.
Таблица 30- Данные для решения задачи
динамического программирования
Объем капиталовложений Xi
(тыс. руб.)
|
Прирост выпуска продукции ѓі (Xi)
в зависимости от объема капиталовложений (тыс. руб.)
|
|
предприятие 1
|
предприятие 2
|
предприятие 3
|
0 100 200 300 400 500 600 700
|
0 30 50 90 100 160 170 210
|
0 50 80 90 150 190 210 220
|
0 40 50 110 120 180 220 240
|
Математическая модель задачи.
Определить х* = (,, …, , …, ),
обеспечивающий максимум целевой функции
и удовлетворяющий условиям
,
Математическая модель задачи :
при ограничениях:
,
.
Условная оптимизация.
Максимально возможный доход, который
может быть получен с предприятий (с k-го по n-е), определяется с помощью
функции Беллмана:
,
где Сk -
количество средств, инвестируемых вk-е
предприятие, 0≤ Сk≤ В.
На первом шаге условной оптимизации
при k = n функция Беллмана представляет собой прибыль только с n-го
предприятия. При этом на его инвестирование может остаться количество средств Сn,
0≤ Сn≤ В. Чтобы получить максимум прибыли с этого
предприятия, можно вложить в него все эти средства, т.е.
Fn(Сn) = fn(Сn)
и хn = Сn.
Для упрощения расчетов предполагаем, что
распределение средств осуществляется в целых числах xi =
{0,100,200,300,400,500, 600, 700} тыс. руб.
На первом шаге все капиталовложения идут на 1-е
предприятие (Таблица 31).
Таблица 31 - Первый шаг задачи динамического
программирования
В шапке таблицы отражены варианты значений
капиталовложений х1, которые могут быть предоставлены первому
предприятию. В столбце C1 отражены варианты значений
капиталовложений, которые могут быть выделены всем трем предприятиям в
совокупности.
Предположим, что все средства в количестве x1
= 700тыс. руб. отданы первому предприятию. В этом случае максимальный доход
составит f1(x1)
= 700 тыс. руб., следовательно: F1(C1) = f1(x1)
и x1= C1.
На втором шаге определяем оптимальную стратегию
при распределении денежных средств между вторым и первым предприятиями. При
этом рекуррентное соотношение Беллмана имеет вид:
.
Таблица 32 - Второй шаг задачи динамического
программирования
В шапке таблицы отражены варианты значений
капиталовложений х2, которые могут быть предоставлены второму
предприятию при условии, что часть средств выделяется первому предприятию. В
клетках таблицы первое слагаемое - это возможный прирост выпуска продукции
второго предприятия f2(х2)
в результате освоения капиталовложений х2; второе слагаемое -
значение функции Беллмана, полученной на предыдущем шаге F1(C2
- х2), т.е. возможный прирост выпуска продукции первого предприятия,
если ему будет выделена оставшаяся часть капиталовложений, определяемая как C2
- х2.
На третьем шаге определяем оптимальную стратегию
при распределении денежных средств между третьим и двумя другими предприятиями,
используя следующую формулу для расчета суммарного дохода:
,
В шапке таблицы отражены варианты
значений капиталовложений х1, которые могут быть предоставлены
третьему предприятию при условии, что часть средств выделяется второму и
первому предприятию. В клетках таблицы первое слагаемое - это возможный прирост
выпуска продукции первого предприятия f1(х1)
в результате освоения капиталовложений х1; второе слагаемое -
значение функции Беллмана, полученной на предыдущем шаге F2(C1-х1),
т.е. возможный прирост выпуска продукции второго и первого предприятий, если им
будет выделена оставшаяся часть капиталовложений, определяемая как C1 - х1.
Таблица 33 - Третий шаг задачи динамического
программирования
Значение функции Беллмана F1(С1)
представляет собой максимально возможный доход со всех предприятий, а значение , на котором
достигается максимум дохода, является оптимальным количеством средств,
вложенных в третье предприятие.
Следовательно, значение целевой функции равно Fmax(x*)
= 270 тыс. руб. Безусловная оптимизация.
Далее на этапе безусловной оптимизации для всех
последующих шагов вычисляется величина Сk = (Сk-1 - хk-1)
оптимальным управлением на k-м шаге является то значение хk, которое
обеспечивает максимум дохода при соответствующем состоянии системы Sk. Определяем
компоненты оптимальной стратегии. Для этого значения функций Беллмана и
соответствующие им оптимальные значения х вносим в итоговую таблицу 34.
Таблица 34 - Обратный ход
По данным из таблицы 34 максимальный доход при
распределении 700 тыс. руб. между тремя предприятиями составляет: C1
= 700, F3(700) = 270 тыс. руб.
Таким образом, возможный вариант оптимального
плана инвестирования предприятий:
х* = (0, 100, 600), который обеспечит
максимальный доход, равный
F(700) = f1
(0)
+ f2(100)
+ f3(600)
= 0 + 50 + 220 = 270 тыс. руб.;
Заключение
В первом разделе курсовой работы требовалось
найти оптимальный план выпуска изделий, который обеспечивал бы организации
максимальный доход. Оптимальный план выпуска = 4 единицы. Были найдены решения
В ДЗЛП И ПЗЛП: X* = (0, 1, 0, 0, 6, 3) и Y* =
(4/3;0;0;1;0;5/3). Следовало произвести расчет границ изменения дефицитных
ресурсов, в пределах которых не изменится структура оптимального плана. В
рассмотренном случае лишь один ресурс используется полностью, следовательно,
является дефицитным. Это ресурс Р1: 0 £
b1 +Db1 £
15/ 2. Также был произведен расчет границ изменения цены изделия, попавших в
оптимальный план производства, в пределах которых оптимальный план не
изменится.
В план производства вошел второй вид продукции П2
и цена на него устанавливается в размере 4 ден. ед. В курсовой работе
произведена оценка целесообразности приобретения дополнительного количества
ресурса и была доказано, что данная процедура не целесообразна. Произведена
оценка целесообразности выпуска нового изделия. Учитывая, что затраты на
ресурсы для производства продукции третьего вида меньше цены реализации с4
= 15 ден. ед., то включение ее в план производства целесообразно. В курсовой
работе был найден оптимальный план для хлебозавода, оптимальный план перевозки,
который равен 1007 денежным единицам, при котором общая стоимость перевозок
минимальна, была обоснована ценовая стратегия, цена игры равна 7/2 денежных
единиц, было произведено распределение ресурсов между проектами для того, чтобы
получить максимальный суммарный доход, который равен 270 тыс. руб.. Ко всем
расчетам мною были приложены решения в среде Microsoft Excel. Таким образом,
все поставленные задачи курсовой работы были выполнены, все методы и методики
решения были проанализированы на конкретном виде предприятия.
Список литературы
.
«Математические методы в программировании: Учебник» / Агальцов В.П. - М.:ИД
«ФОРУМ», 2013
.
«Динамическое программирование» / Окулов С.М., Пестов О.А. - М.: БИНОМ.
Лаборатория знаний, 2012
.
«Компьютерное моделирование математических задач: учебное пособие» / Сулейманов
Р.Р. - М.: БИНОМ. Лаборатория знаний, 2012
.
«Введение в математическое моделирование: учебное пособие» / Под ред. Трусова
П.В. - М.: Университетская книга, Логос, 2007
.
«Математические методы и модели в управлении» / Шикин Е. В., Чхартишвили А. Г.
- М: Дело, 2002
.
«Математические методы и модели исследования операций»: Учебное пособие /
Кутузов А. Л. - издательство СПб ГПУ, 2005
.
«Математические методы: Учебник» / Партика Т. Л., Попов И. И. - М: ФОРУМ:
ИНФРА, 2005
.
«Математическое программирование» / Костевич Л., издательство «Новое знание»,
2003
.
«Экономико-математическое моделирование: практическое пособие по решению задач»
/ Мадера А. Г. - М: ИЭУП, 2004