МИНИСТЕРСТВО ОБРАЗОВАНИЯ ИНАУКИ УКРАИНЫ
БЕРДЯНСКИЙ УНИВЕРСИТЕТМЕНЕДЖМЕНТА И БИЗНЕСА
КАФЕДРА МАТЕМАТИКИ ТАМАТЕМАТИЧНИХ МЕТ0ДИВ
КУРСОВАЯ РАБОТА
по дисциплине
«Математические методыисследования операций»
на тему
Решение и постоптимальныйанализ задачи линейного программирования
Вариант № 3 / 4
1.Теоретические сведения
1.1 Симплекс-метод
Теорема (фундаментальная). Если ЗЛПимеет оптимальное решение (в ограниченной области всегда, а в неограниченной — в зависимости от ограниченности целевой функции Z), то оно совпадает, по крайней мере, содним из допустимых базисных решений (ДБР) системы ограничений.
Согласно фундаментальной теореме вместо исследования бесконечногомножества допустимых решений, необходимо исследовать лишь конечное число ДБР.Таким образом, принципиальная схема решения ЗЛП такова:
найти все ДБР;
вычислить для каждого из них соответствующее значение ЦФ z;
сравнить и определить наилучшее.
Но, в общем случае при больших значениях п и т количествоДБР может быть огромным (порядка С пт) ипрактическое осуществление перебора всех ДБР станет невозможным. Эти трудностиобусловлены тем, что указанная принципиальная схема связана с беспорядочнымперебором ДБР, без учета, насколько новое проверяемое ДБР изменяет ЦФ z и приближает ли оно нас к искомомуоптимуму. Если же указанный перебор ДБР производить целеустремленно, добиваясьна каждом шаге монотонного изменения ЦФ z, т.е. чтобы каждое следующее ДБР былолучше предыдущего (или по крайней мере не хуже), то число анализируемых ДБРможно резко сократить.
Основной метод решения ЗЛП — симплекс-метод — базируется на идеепоследовательного улучшения решения. Очевидно, что для реализации этой идеиметод должен включать три основных элемента:
> способ определения исходного ДБР;
> правило перехода к следующему «лучшему» ДБР;
> критерий, по которому можно определить оптимальность найденногорешения или необходимость его дальнейшего улучшения.
Табличный симплекс-метод
Пусть для исходной ЗЛП задано начальное ДБР, базис которогообразуют первые т столбцов матрицы А. Введем новую переменную z и с помощью элементарных преобразованийЖордана-Гаусса преобразуем расширенную систему к диагональной формеотносительно переменных z,x1,x2,...,xm:
Даннойдиагональной форме в дальнейшем будем ставить в соответствие следующую таблицу:
В дальнейшем второй столбец будем опускать!
Построенная таблица называется симплекс-таблицей. Онасодержит всю информацию, необходимую для осуществления одной итерациисимплекс-метода. Реализация симплекс-метода с помощью симплекс-таблицыназывается табличным симплекс-методом. По сути симплекс-метод итабличный симплекс-метод соотносятся между собой как метод и алгоритм.
Схема табличного симплекс-метода.
Шаг . Начальный шаг.
Пусть задано ДБР х° исходной задачи. Построимсоответствующую этому ДБР х° симплекс-таблицу.
Шаг 1. Проверка условияоптимальности.
Если коэффициенты z-строки d0J, j= 1,mнеотрицательные, топрекратить вычисления: текущей симплекс-таблице соответствует оптимальное ДБР.
Шаг 2. Выбор ведущего столбца.
Среди коэффициентов dj,j= 1,nвыбрать отрицательный. Пустьмы выбрали dp. Тогда р-й столбец будет ведущим.Переменная хрбудет вводиться во множество базисныхпеременных.
Шаг 3. Выбор ведущей строки.
Если коэффициенты aip,i= 1,mнеположительные, топрекратить вычисления:
целевая функция не ограничена сверху, иначе выбрать q-ую строку, для которой q-ая строка называется ведущей.
Элемент таблицы aqpна пересечении ведущихстроки и столбца называется ведущим элементом.
Шаг 4. Переход к новойсимплекс-таблице.
Используя преобразования Жордана-Гаусса над СЛАУ, всимплекс-таблице сделать ведущий элемент равным единице, а все остальныекоэффициенты ведущего столбца равными нулю. Слева от таблицы в q-ой строке запишем переменную хр.
Перейти на шаг 1.
1.2 Постоптимальный анализ
Постоптимальныйанализ (анализ моделей начувствительность) – это процесс, реализуемый после того, какоптимальное решение задачи получено. В рамках такого анализа выявляетсячувствительность оптимального решения к определенным изменениям исходной модели. Иными словами,анализируется влияние возможных изменений исходных условий на полученное ранееоптимальное решение. Важность этого анализа ЗЛП объясняется также ещё и тем,что большая часть параметров ЗЛП точно не известна, и на практике обычноберутся приближенные значения параметров.
Отсутствие методов, позволяющих выявить влияние возможныхизменений параметров модели на оптимальное решение, может привести к тому, чтополученное (статическое) решение устареет еще до своей реализации. Существуетдва способа постоптимального анализа: графический метод и аналитический.
В постоптимальном анализе исследуются три класса параметров:
1. Компоненты вектора ограничений bt
После нахождения оптимального решения.представляется вполнелогичным выяснить, как отразится на оптимальном решении изменение запасовресурсов. Отметим, что неравенства модели типа "" обычномогут быть интерпретированы, как ограничения на использование лимитированногоресурса. А ограничения типа ">" могут бытьинтерпретированы, как некоторые требования к моделируемому процессу.
При анализе изменений запасов ресурсов особенно важны дваследующих аспекта:
> На сколько можно увеличить (уменьшить) запаснекоторого ресурса для улучшения полученного оптимального значенияцелевой функции z?
> На сколько можно снизить (увеличить) запас некоторогоресурса при сохранении полученного оптимального значения целевой функцииz?
2. Коэффициенты ЦФ Cj
Определяется пределы допустимых изменений коэффициентов целевойфункции.
> Каков диапазон изменения (увеличения или уменьшения) того илииного коэффициента целевой функции, при котором не происходит изменениеоптимального решения?
> Насколько следует изменить тот или иной коэффициент целевойфункции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот,дефицитный ресурс сделать недефицитным?
1. Существует диапазон изменения А коэффициентов ЦФ как базисных,так и небазисных переменных, в которых текущее оптимальное решение остаетсяоптимальным.
— для небазисных переменных существует только нижняя или верхняяграница;
— для базисных — обычно существуют и нижняя и верхняя границы.
2. Изменение коэффициента ЦФ базисной переменной всегдаприводит к изменению значения ЦФ.
3. Эффект от изменения коэффициентов ЦФ может рассматриваться сдвух позиций:
— с точки зрения сбыта нас интересуют равновесныецены;
— с точкизрения производства нас интересует диапазон изменения коэффициента ЦФ, ' впределах которого текущий план производства остается оптимальным.
Нахождение диапазонов изменения запасов ресурсов
Недефицитные ресурсы
Если в оптимальном решении дополнительная переменная S i-ro ограничения базисная, тоэто ограничение является не связывающим (не активным в точке оптимума), аресурс — недефицитный. В этом случае значение дополнительной базиснойпеременной дает диапазон изменения, в котором соответствующая компонента diможет:
• Уменьшатся (в случае знака ограничения "")
• Увеличивается (в случае знака ограничения ">").
Пусть S0 — значение соответствующейдополнительной переменной в точке оптимума. Тогда решение остаётся допустимым иоптимальным в диапазоне bi+ ∆, где
Дефицитные ресурсы
Если в оптимальном решении некоторая дополнительная переменнаянебазисная, то существующее ' ей ограничение является связывающим (активным вточке оптимума), а ресурс — дефицитным.
Для ограничения типа "":
Для ограничения типа ">":
Изменение коэффициентов Ц.Ф.
Существует диапазон изменения коэффициентов ' целевой функции какбазисных так и не базисных переменных, в которых полученное решение остаётсяоптимальным. Изменение коэффициента базисной переменной в пределах этогодиапазона приводит к изменению значения целевой функции, так как Z = Ств*β, аодна из компонент вектора Св изменяется. Изменение коэффициента небазиснойпеременной не меняет значения задачи.
Для задачи на mах:
Базисные переменные:
Для базисной переменной диапазон устойчивости, в котором можетизменяться коэффициент Ci, оставляя текущее решение оптимальным, задаётсявыражением: Ci + ∆
где dj— относительная оценкапеременной xj в текущем оптимальном решении.
Eслиотсутствуют /> соответственно.
Не базисные переменные:
Для не базисной переменной диапазон устойчивости, в котором можетизменятся коэффициент Сi оставляя текущее решение оптимальным, задаётся выражением:
Для задачи на min: Базисные переменные:
Для базисной переменной диапазон устойчивости, в котором можетизменяться коэффициент Сi, оставляя текущее решение оптимальным, задаётся выражением: Сi + ∆
Heбазисные переменные:
Для не базисной переменной диапазон устойчивости, в котором можетизменятся коэффициент С; оставляя текущее решение оптимальным, задаётсявыражением:
(dN) ∆ ∞
2.Содержательная постановка задачи
Вариант 3/2
Транспортная компаниядля перевозки инжира из Багдада в Мекку использует мулов, одногорбых идвугорбых верблюдов. Двугорбый верблюд может перевезти — 1000 фунтов,одногорбый – 500 фунтов, а мул – 300 фунтов. За один переход двугорбый верблюдпотребляет 2 кипы сена и 40 галлонов воды. Одногорбый верблюд потребляет 2 кипысена и 30 галлонов воды. Мул – 1 кипу сена и 10 галлонов воды. Пункты снабжениякомпании, расположенные в различных оазисах вдоль пути, могут выдать не более900 галлонов воды и 35 кип сена. Верблюды и мулы арендуются у пастуха близБагдада, арендная плата равна 12 пиастрам за двугорбого верблюда, 5 пиастрам заодногорбого и 4 пиастрам за мула.
Если компания должнаперевести 8000 фунтов инжира из Багдада в Мекку, сколько надо использоватьверблюдов и мулов для минимизации арендной платы пастуху?
3.Математическая постановка задачи
Переменные:
Х1 — Двугорбый верблюд
Х2 — Одногорбый верблюд
Х3 – Мул
Целевая функция – минимизацияарендной платы.
Zmin= 12Х1+ 5Х2+ 4Х3
Ограничения:
Использованияресурса «вода» не более 900 галлонов:
40Х1 + 30Х2+ 10Х3 900
Использованияресурса «сено» не более 35 кип:
3Х1 + 2Х2+ Х3 35
Компания должнаперевести 8000 фунтов инжира:
1000Х1 + 500Х2 + 300Х3=8000
Все переменные должныбыть не отрицательны:
Х1, Х2, Х3 >0
4. Решения задачи симплекс-методом
ЦФ:
Zmin = 12X1 + 5X2 + 4X3
Ограничения:
/> 40X1 + 30X2 + 10X3 900
3X1 + 2X2 + X3 35
1000X1 + 500X2 + 300X3 = 8000
X1, X2, X3 > 0
Приведемзадачу к канонической форме и введём искусственные переменные:
/>Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – MR1
40X1 + 30X2 + 10X3 + 0S1 = 900
3X1 + 2X2 + X3 + 0S2 = 35
1000X1 + 500X2 + 300X3 + R1 = 8000
X1, X2, X3 > 0
R1 = – 1000X1 – 500X2 – 300X3 + 8000
Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – M (– 1000X1 – 500X2 – 300X3 + 8000) = (12 + 1000M) X1 + (5 + 500M) X2 + (4 + 300M) X3 – 8000M
Z + (–12 – 1000M) X1 + (–5 – 500M) X2 + (–4 – 300M) X3 = – 8000M
Составляем симплекс таблицу:Шаг 0 БП X 1 X2 X3 S1 S2 R1 решение S1 40 30 10 1 900 S2 3 2 1 1 35 R1 1000 500 300 1 8000 Z -1000M+12 -500M+5 -300M+4 -8000M Шаг 1 S1 10 -2 1 -1/25 580 S2 1/2 1/10 1 -3/1000 11 X1 1 1/2 3/10 1/1000 8 Z -1 2/5 M-3/250 -96 Шаг 2 S1 -20 -8 1 -3/50 420 S2 -1 -1/5 1 -1/250 3 X2 2 1 3/5 1/500 16 Z 2 1 M-1/100 -80
В итоге: Z= 80, X1 = 0, X2 = 16, X3 = 0
5. Постоптимальный анализ решения
5.1 Определения статуса и ценности ресурсов
/>Zmin = 12X1 + 5X2 + 4X3
40X1 + 30X2 + 10X3 + S1 = 900
3X1 + 2X2 + X3 + S2 = 35
1000X1 + 500X2 + 300X3 = 8000
Двойственнаязадача имеет вид:
ω max = 900Y1 + 35Y2 + 8000Y3
/> 40Y1 + 3Y2 + 1000Y3 12 (X1)
30Y1 + 2Y2 + 500Y3 5 (X2)
10Y1 + 1Y2 + 300Y3 4 (X3)
Y1 0 (S1)
Y2 0 (S2)
Воптимальной таблице прямой задачи базисными переменными являются S1, S2 и X2. Согласно с соотношениями дополняющейнежесткости соответствующие этим переменным ограничения – неравенствадвойственной задачи в точке оптимума выполняются как равенства. Таким образом,получаем следующую систему линейных равенств.
/>/>30Y1 + 2Y2 + 500Y3 = 5 Y1 = 0
Y1 = 0 Y2 = 0
Y2 = 0 Y3 = 0,01
Решенияполученной системы линейных уравнений:
Y1 = 0; Y2 = 0; Y3 = 0,01
По основнойтеореме двойственности решения прямой и двойственной задачи должны совпадать:
ω = 900*0 + 35*0 + 8000*0.01 = 80 => ω = Z
5.2 Ценности ресурсов
№ ресурса Наименования Статус Ценность 1-й Вода Недефицитный 2-й Сено Недефицитный 3-й Соотношение Дефицитный 0,01
Согласнотеории двойственности, двойственная переменная Yi (і = 1,2,3) определяет ценность і-горесурса – величину, на которую изменится значения целевой функции приувеличении на единицу уровня запаса соответствующего ресурса.
Такимобразом, при изменении в некоторых границах уровней запасов ресурсов имеем:
— приувеличении на 1 единицу ресурса «вода» не приведут к изменению
— при увеличениина 1 единицу ресурса «сено» не приведут к изменению
— приувеличении на 1 фунта перевозки, повысится арендная плата на 0,01 пиастров.
5.3 Определения допустимых диапазонов изменения уровней запасовресурсов
Недефицитныересурсы:
Переменная S1 – базисная, ресурс «вода»недефицитный.
Ограниченияимеет знак « »
-420 ∆1
Абсолютныйдиапазон изменения:
480 b1
Переменная S2 – базисная, ресурс «сено»недефицитный.
Ограниченияимеет знак « »
-3 ∆2
Абсолютныйдиапазон изменения:
32 b2
Дефицитныересурсы:
ПеременнаяR1 – не базисная, ресурс дефицитный.
-8000 ∆3 750
Абсолютныйдиапазон изменения:
0 b3 8750
5.4 Определение допустимых диапазонов изменения коэффициентовцелевой функции
Базисныепеременные:
Переменная X2 –базисная:
-∞ 1
Абсолютныйдиапазон изменения коэффициента ЦФ:
-∞ 13
Не базисныепеременные:
ПеременнаяХ1 – не базисная:
2 ∆1
Абсолютныйдиапазон изменения коэффициента ЦФ:
14 C1
ПеременнаяХ3 – не базисная:
1 ∆3
Абсолютныйдиапазон изменения коэффициента ЦФ:
5 C3
6. Ответ
Оптимальноерешения задачи:
— использование «двугорбый верблюд» — 0
— использование «одногорбый верблюд» — 16
— использования «мул» — 0
При этомоптимум = 80 пиастрам
Диапазонизменения уровня запасов:
— запасыводы -420 ∆1
— запасысена -3 ∆2
— соотношение -8000 ∆3 750
Абсолютныедиапазоны изменения уровней запасов:
— запасыводы 480 b1
— запасысена 32 b2
— соотношение 0 b3 8750
Ценностьресурсов:
— приувеличении на 1 единицу ресурса «вода» не приведут к изменению
- приувеличении на 1 единицу ресурса «сено» не приведут к изменению
- приувеличении на 1 фунта перевозки, повысится арендная плата на 0,01 пиастров.
Диапазонизменения коэффициентов:
— двугорбыйверблюд 2 ∆1
— одногорбый верблюд ∞ 1
— мул 1 ∆3
Абсолютныедиапазоны изменения:
— двугорбыйверблюд 14 C1
— одногорбый верблюд -∞ 13
— мул 5 C3
7. Задание на применения графического способа решения задач линейногопрограммирования
№ 28
Z = 2X1 + X2 → min
X1 — X2 > 4 (1)
X1 + X2 > 4 (2)
4X1 — X2 16 (3)
7X1 + X2 14 (4)
X1, X2 > 0
Ответ: Нетрешений
№ 58
Z = -X1 + 3X2 → max
-2X1 + X2 2 (1)
X1 + 2X2 > 6 (2)
X1 > 2 (3)
3X1 + 4X2 24 (4)
X1, X2 > 0
Ответ: X1 = 2
X2 = 4.5
Z = 11.5
СПИСОКЛИТЕРАТУРЫ
1. Исследованиеопераций. В 2-ух томах. Методологические основы и математические методы. / Подред. Дж. Моудера, С. Элмаграби. — М.: Мир, 1981. Т. 1.-712 с.
2. МуртафБ. Современное линейное программирование. Теория и практика -М.: Мир, 1984.-224 с. Т.
3. ТахаX. Введение в исследование операций:В 2-ух томах. — М.: Мир, 1985. Т. 1.-325с.
4. КалихманИ.Л. Линейная алгебра и программирование. — М.: Высшая школа, 1967.-428 с.
5. Конспектлекций.