Курсовая работа: Решение и постоптимальный анализ задачи линейного программирования

💣 👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

БЕРДЯНСКИЙ УНИВЕРСИТЕТ МЕНЕДЖМЕНТА И БИЗНЕСА

КАФЕДРА МАТЕМАТИКИ ТА МАТЕМАТИЧНИХ МЕТ0ДИВ

«Математические методы исследования операций»

Решение и постоптимальный анализ задачи линейного программирования


Теорема (фундаментальная).
Если ЗЛП имеет оптимальное решение (в ограниченной области всегда, а в неограниченной - в зависимости от ограниченности целевой функции Z), то оно совпадает, по крайней мере, с одним из допустимых базисных решений (ДБР) системы ограничений.
Согласно фундаментальной теореме вместо исследования бесконечного множества допустимых решений, необходимо исследовать лишь конечное число ДБР. Таким образом, принципиальная схема решения ЗЛП такова:
вычислить для каждого из них соответствующее значение ЦФ z;
Но, в общем случае при больших значениях п и т
количество ДБР может быть огромным (порядка С п
т
)
и практическое осуществление перебора всех ДБР станет невозможным. Эти трудности обусловлены тем, что указанная принципиальная схема связана с беспорядочным перебором ДБР, без учета, насколько новое проверяемое ДБР изменяет ЦФ z и приближает ли оно нас к искомому оптимуму. Если же указанный перебор ДБР производить целеустремленно, добиваясь на каждом шаге монотонного изменения ЦФ z, т.е. чтобы каждое следующее ДБР было лучше предыдущего (или по крайней мере не хуже), то число анализируемых ДБР можно резко сократить.
Основной метод решения ЗЛП - симплекс-метод - базируется на идее последовательного улучшения решения. Очевидно, что для реализации этой идеи метод должен включать три основных элемента:
> способ определения исходного ДБР;
> правило перехода к следующему "лучшему" ДБР;
> критерий, по которому можно определить оптимальность найденного решения или необходимость его дальнейшего улучшения.
Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые т
столбцов матрицы А.
Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расширенную систему к диагональной форме относительно переменных z
,
x
1

,
x
2

,...,
x m

:

Данной диагональной форме в дальнейшем будем ставить в соответствие следующую таблицу:
В дальнейшем второй столбец будем опускать!
Построенная таблица называется симплекс-таблицей.

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

По сути симплекс-метод и табличный симплекс-метод соотносятся между собой как метод и алгоритм.
Пусть задано ДБР х°
исходной задачи. Построим соответствующую этому ДБР х°
симплекс-таблицу.
Шаг
1. Проверка условия оптимальности.
Если коэффициенты z-строки d 0
J
, j
= 1,mнеотрицательные, то прекратить вычисления: текущей симплекс-таблице соответствует оптимальное ДБР.
Среди коэффициентов d
0

j
,
j
=
1,
n
выбрать отрицательный. Пусть мы выбрали d
0

p

.
Тогда р-й столбец будет ведущим. Переменная х р

будет вводиться во множество базисных переменных.
Если коэффициенты a ip

,
i
=
1,
m
неположительные, то прекратить вычисления:
целевая функция не ограничена сверху, иначе выбрать q-ую строку, для которой q-ая строка называется ведущей.
Элемент таблицы a qp

на пересечении ведущих строки и столбца называется ведущим элементом.
Шаг
4. Переход к новой симплекс-таблице.
Используя преобразования Жордана-Гаусса над СЛАУ, в симплекс-таблице сделать ведущий элемент равным единице, а все остальные коэффициенты ведущего столбца равными нулю. Слева от таблицы в q-ой строке запишем переменную х р
.

Постоптимальный анализ

(анализ моделей на чувствительность) – это процесс, реализуемый после

того, как оптимальное решение задачи получено. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. Иными словами, анализируется влияние возможных изменений исходных условий на полученное ранее оптимальное решение. Важность этого анализа ЗЛП объясняется также ещё и тем, что большая часть параметров ЗЛП точно не известна, и на практике обычно берутся приближенные значения параметров.
Отсутствие методов, позволяющих выявить влияние возможных изменений параметров модели на оптимальное решение, может привести к тому, что полученное (статическое) решение устареет еще до своей реализации. Существует два способа постоптимального анализа: графический метод и аналитический.
В постоптимальном анализе исследуются три класса параметров:
1. Компоненты вектора ограничений b t


После нахождения оптимального решения .представляется вполне логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Отметим, что неравенства модели типа " <
" обычно могут быть интерпретированы, как ограничения на использование лимитированного ресурса. А ограничения типа " >
" могут быть интерпретированы, как некоторые требования к моделируемому процессу.
При анализе изменений запасов ресурсов особенно важны два следующих аспекта:
> На сколько можно увеличить (уменьшить)
запас некоторого ресурса для улучшения
полученного оптимального значения целевой функции z?
> На сколько можно снизить (увеличить)
запас некоторого ресурса при сохранении
полученного оптимального значения целевой функции z?
Определяется пределы допустимых изменений коэффициентов целевой функции.
> Каков диапазон изменения (увеличения или уменьшения) того или иного коэффициента целевой функции, при котором не происходит изменение оптимального решения?
> Насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?
1. Существует диапазон изменения А коэффициентов ЦФ как базисных, так и небазисных переменных, в которых текущее оптимальное решение остается оптимальным.
- для небазисных переменных существует только нижняя
или верхняя
граница;
- для базисных - обычно существуют и нижняя и верхняя
границы.
2. Изменение коэффициента ЦФ базисной переменной
всегда приводит к изменению значения ЦФ.
3. Эффект от изменения коэффициентов ЦФ может рассматриваться с двух позиций :
- с точки зрения сбыта нас интересуют

равновесные цены;
- с точки зрения производства нас интересует диапазон изменения коэффициента ЦФ, ' в пределах которого текущий план производства остается оптимальным.
Нахождение диапазонов изменения запасов ресурсов

Если в оптимальном решении дополнительная переменная Si-ro ограничения базисная, то это ограничение является не связывающим (не активным в точке оптимума), а ресурс - недефицитный. В этом случае значение дополнительной базисной переменной дает диапазон изменения, в котором соответствующая компонента d
i

может:
• Уменьшатся (в случае знака ограничения " <
")
• Увеличивается (в случае знака ограничения " >
").
Пусть S 0
- значение соответствующей дополнительной переменной в точке оптимума. Тогда решение остаётся допустимым и оптимальным в диапазоне bi+ ∆ , где
Если в оптимальном решении некоторая дополнительная переменная небазисная, то существующее ' ей ограничение является связывающим (активным в точке оптимума), а ресурс - дефицитным.
Существует диапазон изменения коэффициентов ' целевой функции как базисных так и не базисных переменных, в которых полученное решение остаётся оптимальным. Изменение коэффициента базисной переменной в пределах этого диапазона приводит к изменению значения целевой функции, так как Z = С т
в
*β, а одна из компонент вектора Св изменяется. Изменение коэффициента небазисной переменной не меняет значения задачи.
Для базисной переменной диапазон устойчивости, в котором может изменяться коэффициент Ci, оставляя текущее решение оптимальным, задаётся выражением: Ci + ∆
где dj
-
относительная оценка переменной xj в текущем оптимальном решении.
Для не базисной переменной диапазон устойчивости, в котором может изменятся коэффициент Сi оставляя текущее решение оптимальным, задаётся выражением:
Для задачи на
min
: Базисные переменные:

Для базисной переменной диапазон устойчивости, в котором может изменяться коэффициент Сi , оставляя текущее решение оптимальным, задаётся выражением: Сi + ∆
Для не базисной переменной диапазон устойчивости, в котором может изменятся коэффициент С; оставляя текущее решение оптимальным, задаётся выражением:
2. Содержательная постановка задачи

Транспортная компания для перевозки инжира из Багдада в Мекку использует мулов, одногорбых и двугорбых верблюдов. Двугорбый верблюд может перевезти - 1000 фунтов, одногорбый – 500 фунтов, а мул – 300 фунтов. За один переход двугорбый верблюд потребляет 2 кипы сена и 40 галлонов воды. Одногорбый верблюд потребляет 2 кипы сена и 30 галлонов воды. Мул – 1 кипу сена и 10 галлонов воды. Пункты снабжения компании, расположенные в различных оазисах вдоль пути, могут выдать не более 900 галлонов воды и 35 кип сена. Верблюды и мулы арендуются у пастуха близ Багдада, арендная плата равна 12 пиастрам за двугорбого верблюда, 5 пиастрам за одногорбого и 4 пиастрам за мула.
Если компания должна перевести 8000 фунтов инжира из Багдада в Мекку, сколько надо использовать верблюдов и мулов для минимизации арендной платы пастуху?
3. Математическая постановка задачи

Целевая функция –
минимизация арендной платы.
Использования ресурса «вода» не более 900 галлонов:
Использования ресурса «сено» не более 35 кип:
Компания должна перевести 8000 фунтов инжира:
Все переменные должны быть не отрицательны:
Приведем задачу к канонической форме и введём искусственные переменные:
Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – MR1
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
В итоге: Z = 80, X1 = 0, X2 = 16, X3 = 0
5.1 Определения статуса и ценности ресурсов

В оптимальной таблице прямой задачи базисными переменными являются S1, S2 и X2. Согласно с соотношениями дополняющей нежесткости соответствующие этим переменным ограничения – неравенства двойственной задачи в точке оптимума выполняются как равенства. Таким образом, получаем следующую систему линейных равенств.
Решения полученной системы линейных уравнений:
По основной теореме двойственности решения прямой и двойственной задачи должны совпадать:
ω = 900*0 + 35*0 + 8000*0.01 = 80 => ω = Z
Согласно теории двойственности, двойственная переменная Yi (і = 1,2,3) определяет ценность і-го ресурса – величину, на которую изменится значения целевой функции при увеличении на единицу уровня запаса соответствующего ресурса.
Таким образом, при изменении в некоторых границах уровней запасов ресурсов имеем:
- при увеличении на 1 единицу ресурса «вода» не приведут к изменению
- при увеличении на 1 единицу ресурса «сено» не приведут к изменению
- при увеличении на 1 фунта перевозки, повысится арендная плата на 0,01 пиастров.
5.3 Определения допустимых диапазонов изменения уровней запасов ресурсов

Переменная S1 – базисная, ресурс «вода» недефицитный.
Переменная S2 – базисная, ресурс «сено» недефицитный.
Переменная R1 – не базисная, ресурс дефицитный.
5.4 Определение допустимых диапазонов изменения коэффициентов целевой функции

Абсолютный диапазон изменения коэффициента ЦФ:
Абсолютный диапазон изменения коэффициента ЦФ:
Абсолютный диапазон изменения коэффициента ЦФ:
- использование «двугорбый верблюд» - 0
- использование «одногорбый верблюд» - 16
Диапазон изменения уровня запасо
в:
Абсолютные диапазоны изменения уровней запасов
:
- при увеличении на 1 единицу ресурса «вода» не приведут к изменению
- при увеличении на 1 единицу ресурса «сено» не приведут к изменению
- при увеличении на 1 фунта перевозки, повысится арендная плата на 0,01 пиастров.
7. Задание на применения графического способа решения задач линейного программирования

1. Исследование операций. В 2-ух томах. Методологические основы и математические методы. / Под ред. Дж. Моудера, С. Элмаграби. - М.: Мир, 1981. Т. 1.-712 с.
2. Муртаф Б. Современное линейное программирование. Теория и практика -М.: Мир, 1984.- 224 с. Т.
3. Таха X. Введение в исследование операций: В 2-ух томах. - М.: Мир, 1985. Т. 1.-325с.
4. Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1967.-428 с.

Название: Решение и постоптимальный анализ задачи линейного программирования
Раздел: Рефераты по математике
Тип: курсовая работа
Добавлен 07:47:22 19 ноября 2010 Похожие работы
Просмотров: 172
Комментариев: 15
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Курсовая работа: Решение и постоптимальный анализ задачи линейного программирования
Магнитное поле
Инфраструктура Инновационной Деятельности Реферат
Реферат: Teachers Essay Research Paper Teachers Throughout my
Светодиодная Лампочка Глазами Ребенка Реферат
Доклад: Никогда никому не говорите «не»
Разработка Проекта Процесса Курсовая
Выборы Президента Реферат
Дипломная работа по теме Гастрономический туризм как перспективное направление развития въездного туризма в Вологодской области
Курсовая работа: Стратегическое управление: сущность, составляющие и связь между ними, проблемы
Курсовая работа: Менеджмент в моей организации 2
Дипломная работа по теме Механизм реализации управления человеческими ресурсами
Стартовая Контрольная Работа По Обществознанию 10
Лабораторные работы по программированию
Дипломная работа по теме Уголовная ответственность за посягательство на жизнь человека
Реферат: Коммуникативные функции музыки в рекламе
Курсовая Международное Управление Человеческими Ресурсами 2022 Г
Реферат: Історія розвитку криміналістики в Україні
Реферат: Проблемы организации психиатрической помощи населению в мегаполисе
Осень В Саду Сочинение 2 Класс
Катаракта Причины Лечение Реферат
Доклад: Освещение деятельности ОВД телевидением
Реферат: Финансовые расчеты
Реферат: Борьба народных масс Украины против шведских захватчиков. Развитие феодальных отношений на Украине