Элементы матричной алгебры




НазваниеЭлементы матричной алгебры
страница24/24
Дата публикации23.06.2013
Размер1.64 Mb.
ТипДокументы
lit-yaz.ru > Математика > Документы
1   ...   16   17   18   19   20   21   22   23   24
^

6.6. Анализ модели ЗЛП на чувствительность.



Возможности, предоставляемые теорией ЛП и симплекс–методом не ограничиваются лишь получением оптимальных значений управляемых переменных. Решение задачи линейного программирования должно обеспечивать пользователя динамичной информацией. Как только условия, в соответствии с которыми была построена модель, изменяются, информация, ассоциированная со статистическим оптимальным решением теряет актуальность. Поэтому чрезвычайно важным представляется анализ изменения оптимального решения при изменении исходной модели (свободных членов, коэффициентов целевой функции и т.д.).

Анализ модели на чувствительность как раз и связан с возможным изменением полученного оптимального решения в результате изменений исходной модели [ ]

Рассмотрим анализ модели на чувствительность к изменению правых частей ограничений исходной модели (запасов ресурсов). При выполнении этого анализа необходимо дать ответы на следующие вопросы:

  • каков статус ресурсов, т.е. какие из них "дефицитные" и какие "недефицитные";

  • какова значимость ресурсов, т.е. изменение объема какого из ресурсов является наиболее выгодным с точки зрения обеспечения наибольшего дохода от реализации продукции;

  • в каких пределах допустимо изменение запаса ресурсов, при которых их влияние на исходную модель задачи линейного программирования адекватно описывается оптимальным решением двойственной задачи (то есть решение двойственной задачи не меняется);

  • как отразится на оптимальном плане увеличение (уменьшение) запасов ресурсов.


^ 1. Определение статуса ресурсов (факторов производства )

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

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

В примере 6.3.дополнительные переменные второго и третьего ограничений ( ) равны 0, следовательно, 2-ой и 3-ий виды сырья являются "дефицитными", а первый – "недефицитным" ( ). Значение дополнительной переменной свидетельствует, что имеется остаток первого ресурса в количестве 8 единиц.

Статус ресурсов можно также оценить по значению двойственных переменных в оптимальном решении двойственной задачи (на основе второй теоремы двойственности). Оценки первого и второго ресурсов (Y2=1; Y3=0,2) положительны, следовательно, запасы этих ресурсов полностью используются и они относятся к "дефицитным" ресурсам.

^ Определение значимости ресурсов.

Значимость ресурса характеризуется величиной улучшения оптимального значения целевой функции F(X), приходящейся на единицу прироста этого ресурса. Как следует из теоремы об оценках Если Таким образом, значимость ресурса всегда можно определить по значению двойственных переменных в оптимальном решении. В нашем примере Следовательно, из двух дефицитных факторов производства второй имеет большую значимость с точки зрения получения прибыли. Если объем второго ресурса увеличить на 1, то прибыль F(X), возрастет на 1, а при увеличении объемов третьего ресурса на единицу, прибыль увеличится на

^ 3.Определение допустимого интервала изменения запасов ресурсов

При анализе модели представляет интерес исследование следующих вопросов:

  • насколько можно увеличить запас некоторого дефицитного ресурса для улучшения полученного оптимального решения так, чтобы технология производства и статус ресурсов остались неизменными;

  • насколько можно снизить запас недефицитного ресурса при сохранении полученного оптимального значения целевой функции.

Определение. Интервал изменения ресурса, внутри которого оптимальное решение двойственной задачи (двойственные оценки ) не меняется, называется интервалом устойчивости двойственных оценок.

При изменении ресурса внутри этого интервала сохраняется мера влияния единицы каждого ресурса на оптимальное значение целевой функции (сохраняется статус и значимость ресурсов).

Для того .чтобы понять, как находятся интервалы устойчивости, рассмотрим как можно найти значения коэффициентов столбца свободных членов на любой симплекс–итерации. Именно эти коэффициенты и определяют соответствующие опорные решения.

При переходе от одной итерации к другой меняется набор базисных переменных. Выделим в первой симплекс-таблице (на 0–итерации) подматрицу D, соответствующую базисным переменным текущей итерации. Тогда

(6.23)

В текущих симплексных таблицах матрица расположена под начальными базисными переменными (базисными переменными первой симплексной таблицы).

Чтобы проиллюстрировать использование соотношения (6.23), рассмотрим пример 6.3. Начальными базисными переменными являются ..

На первой итерации базисные переменные , тогда матрица

(берется из первой симплексной таблицы), а

Если обратится к симплексной таблице первой итерации, то можно увидеть, что расположена в столбцах базисных переменных первой симплексной таблицы (X3, X4, X5.)



Аналогично,



Соотношение аналогичное (6.23) может быть использовано для вычисления любого столбца симплексной таблицы на любой итерации:

(6.24)
Пусть найдено оптимальное решение некоторой ЗЛП. Тогда

(6.25)

Легко показать, что изменение правых частей ограничений исходной задачи будет оказывать влияние только на элементы столбца свободных членов симплексной таблицы, матрица D при этом остается неизменной. Следовательно, если выбираем новый вектор ресурсов , то соответствующее ему оптимальное решение задачи

(6.26),

где – столбец свободных членов в оптимальной симплексной таблице.

Чтобы новое базисное решение осталось допустимым необходимо, чтобы все компоненты вектора были неотрицательны, т.е. Из вышесказанного следует правило вычисления допустимого интервала изменений правых частей ограничений:

Изменим свободный член в i–ом ограничении:

Вычисляем новое оптимальное решение

(6.27)

Компоненты нового решения зависят от i.

Решаем систему неравенств:

(6.28)

Допустимый интервал изменения свободного члена в i-ом ограничении определится на основе решения системы неравенств (6.28). Рассмотренный метод можно обобщить на случай одновременного изменения нескольких свободных членов ограничений. При этом усложняются вычислительные процедуры, связанные с решением системы неравенств (6.28).

Проиллюстрируем вышеизложенное на рассматриваемом примере.

Так как начальными базисными переменными являлись , то в оптимальной симплексной таблице в соответствующих столбцах расположена матрица

обратная матрице
Изменим запас второго ресурса на 2, тогда его новый объем 48+2.

Найдем, решение, соответствующее измененным значениям объема второго ресурса.

=

Легко заметить, что новая правая часть (bi*) каждого ограничения представляет сумму двух величин: постоянной и члена, линейно зависимого от 2.

Постоянная часть совпадает с элементами столбца свободных членов в оптимальной симплексной таблице (соответствует компонентам оптимального решения до изменения объемов ресурсов). Коэффициенты при 2 совпадают с элементами столбца для x4 в оптимальной симплексной таблице (x4 – дополнительная базисная переменная ограничения, соответствующего второму ресурсу).

Для того, чтобы было допустимым, необходимо, чтобы выполнялись условия:



Отсюда следует, что

Таким образом, первоначальный запас второго ресурса может быть увеличен до 56 единиц без нарушения допустимости решения, статуса и значимости ресурсов.
  1. ^

    6.7. Геометрическая интерпретация анализа модели


Рассмотрим графическое решение задачи 6,3







OABCD – область допустимых решений, – нормальный вектор целевой функции.

Оптимальное решение находится в точке B(3,6), Fопт=60. Точка B является пересечением второй и третьей ограничивающих прямых. Эти прямые называют связывающими или активными, они соответствуют "дефицитным" ресурсам. Если менять объем использования "дефицитного" ресурса, то соответствующая прямая будет передвигаться параллельно самой себе. При этом возможны следующие случаи:

  1. до некоторого изменения объема ресурса (свободного члена в ограничении) прямая остается связывающей, тогда интересно определить интервалы изменения запасов ресурса.

  2. прямая перестает быть связывающей, что соответствует смене базиса в оптимальном решении, а следовательно и статуса ресурсов.

Будем увеличивать объем использования второго ресурса, тогда прямая ^ BC будет передвигаться вверх параллельно самой себе. Чтобы не изменились статус и значимость ресурсов, это движение допустимо пока прямые AB и BC остаются связывающими, то есть до точки E. Прохождение прямой CD через точку Е соответствует b2=56, то есть границе допустимых изменений объемов второго ресурса.

В точке Е(5,6) F(Е)=68 то есть прибыль по сравнению с найденным оптимальным решением (точка В) увеличится на В точке E все граничные прямые становятся связывающими.

Допустимому объему использования третьего ресурса соответствует движение связывающей прямой AB до точки K(0,8). , что соответствует увеличению прибыли на Прохождение прямой AB через точку K соответствует 80, т.е. в точке K объем использования третьего ресурса увеличивается на . Тогда в соответствии с третьей теоремой двойственности .
  1. ^

    6.8. Контрольные вопросы





  1. Приведите экономическое толкование двойственной задачи к задаче планирования производства

  2. При каких условиях получаются симметричные двойственные и при каких–несимметричные?

  3. Сформулируйте необходимые и достаточные условия оптимальности, основанные на рассмотрении двойственных задач.

  4. Какой вывод можно сделать о решении двойственной задачи, если исходная имеет неограниченное оптимальное решение?

  5. Как определить оптимальное решение двойственной задачи по известному решению исходной?

  6. Как найти решение симметричной двойственной задачи из оптимальной симплексной таблицы прямой задачи?
  • Литература





  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов экономических специальностей вузов. – М.: Высшая школа, 1986.

  2. Банди Б. Основы линейного программирования. – М.: Радио и связь, 1989.

  3. Вагнер Г. Основы исследования операций. – М.: Мир, 1972.

  4. Исследование операций в экономике. / Под ред. Кремера Н.Ш. – М, ЮНИТИ, 1997.

  5. Калихман И.Л. линейная алгебра и программирование.– М.: Высшая школа,1975

  6. Калихман И.Л. Сборник задач по математическому программированию. – М.: Высшая школа, 1975.

  7. Карандаев И.C. Решение двойственных задач в оптимальном планировании. – М.: Статистика, 1976.

  8. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1980.

  9. Таха Х. Введение в исследование операций. – М.: Мир, 1985, т. 1.

  10. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения. – M.: Наука, гл. ред. физ.-мат. лит., 1969.




1   ...   16   17   18   19   20   21   22   23   24

Похожие:

Элементы матричной алгебры iconКурсовая работа по дисциплине «Информатика» на тему «Применение алгебры...
Элементы алгебры высказываний. Примеры использования алгебры высказываний в информатике

Элементы матричной алгебры iconКурсовая работа по информатике на тему: «применение алгебры высказываний в информатике»
Алгебра – это наука, которая изучает множество некоторых элементов и действия (операции) над ними. Если элементы алгебры – натуральные...

Элементы матричной алгебры iconКонспект урока на тему «Основы логики (повторение). Решение логических...
Основы логики; познакомить учащихся с методами решения логических задач; формирование у учащихся практических умений и навыков решения...

Элементы матричной алгебры iconМетод «от пролога к эпилогу»
«все его элементы суть элементы смысловые» (Лотман Ю.). Исходя из этих положений, выделяем основные приемы, опробуем их на уроке

Элементы матричной алгебры iconЭлементы радиочастотных линий передачи
Элементы радиочастотных линий передачи: Учебно-методическое пособие по курсу «Устройства свч и антенны» / В. В. Паслен, Е. С. Нестругина....

Элементы матричной алгебры iconДипломной практике «система управления ртк для обработки сложных поверхностей»
Обычно изделия изготавливаются из мягких цветных металлов, пластика или дерева. Это могут быть элементы орнамента для декорирования...

Элементы матричной алгебры iconУрок по геометрии в 8 классе на тему «теорема пифагора»
Осуществление межпредметной связи алгебры с географией, историей, литературой, геометрией

Элементы матричной алгебры icon15. Уроки алгебры Кирилла и Мефодия,10-11 класс
МАрк sql. Автоматизированная информационно-библиотечная система. Версия для школьных библиотек

Элементы матричной алгебры iconРабочая программа факультативного курса «Элементы статистики и теории вероятностей»
«Элементы комбинаторики, статистики и теории вероятностей». Так как в этом году учащиеся 9 класса изучают программный материал по...

Элементы матричной алгебры iconИсследование свойств алгебры множеств
Цель работы: Изучение множества, его подмножеств и законов сочетания подмножеств, образующих алгебраическую систему, называемую булевой...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница