рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

М - метод

М - метод - раздел Информатика, Методические указания по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии Вернемся К Введенной В Примере 11.1 Линейной Модели. В Первом И Во В...

Вернемся к введенной в примере 11.1 линейной модели.

В первом и во втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из уравнений по одной искусственной переменной, обозначив их через R1 и R2:

За использование этих переменных в составе целевой функции можно ввести штраф, при­пи­сывая им достаточно большой положительный коэффициент М. Такой способ введения искусст­венных переменных R1 и R2 приводит к следующей линейной модели:

Логика использования искусственных переменных: имеем m=3 уравнения, n=6 неизвестных. Сле­до­вательно, базисное решение должно включать n-m= =6-3=3 нулевые переменные. Если положить рав­ны­ми нулю переменные x1, x2 и x3, то сразу же будет получено требуемое начальное допусти­мое решение: R1=3, R2=6, x4=4.

Рассмотрим теперь, каким образом “новая” структура модели автоматически приводит к тому, что на конечной стадии процесса оптимизации переменные и принимают нулевое значение. Так как мы имеем дело с задачей на отыскание минимума, а переменным R1 и R2 в целевой функции приписан большой по величине коэффициент М, то метод оптимизации, направленный на нахождение минимального значения z, приведет к тому, что переменные R1 и R2 в оптимальном решении обратятся в ноль. Заметим:

Все промежуточные итерации, предшествующие получению оптимума, не имеют значе­ния с точки зрения окончательного результата. Поэтому неважно, фигурирует ли на этих итера­циях положительные искусственные переменные.

Если целевая функция подлежит максимизации: приписываем искусственным переменным в целевой функции достаточно большой по абсолютной величине отрицательный коэффициент –М (М>0), что обусловит недопустимость положительных значений искусственных в оптимальном решении.

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

В результате

При этом z-уравнение в симплекс-таблице будет иметь вид:

,

.

Таким образом, стартовой точке, в которой x1=x2=x3=0, соответствует значение z=9M, как и должно быть при R1=3, R2=6.

Построим симплекс-таблицу (таблица 11).

Так как целевая функция минимизируется, переменные, включаемые в базис, должны иметь наибольшие положительные коэффициенты в z-уравнении. Оптимум достигается на той итерации, где все небазисные переменные имеют неположительные коэффициенты в z-уравнении (М – положительный коэффициент, значение которого принимается очень большим).

Итерация 0 (начало вычислений).

Таблица 11

БП x1 x2 x3 R1 R2 x4 Решение
z - 4+7M -1+4M -M 9M
R1
R2 -1
x4

Согласно условию оптимальности переменная x1 вводится в базис. Согласно условию допустимости переменная R1 выводится из базиса. Получаем таблицу 12.

Итерация 1.

Таблица 12

БП x1 x2 x3 R1 R2 x4 Решение
z (1+5M)/3 -M (4-7M)/3 4+2M
x1 1/3 1/3
R2 5/3 -1 -4/3
x4 5/3 -1/3

Согласно условию оптимальности переменная x2 вводится в базис. Согласно условию допустимости переменная R2 выводится из базиса. Получаем таблицу 13.

Итерация 2.

Таблица 13

БП x1 x2 x3 R1 R2 x4 Решение
z 1/5 8/5-M -1/5-M 18/5
x1 1/5 3/5 -1/5 3/5
x2 -3/5 -4/5 3/5 6/5
x4 -1

Согласно условию оптимальности переменная x3 вводится в базис. Согласно условию допустимости переменная x4 выводится из базиса. Получаем таблицу 14.

 

 

Итерация 3.

Таблица 14

БП x1 x2 x3 R1 R2 x4 Решение
z 7/5-M -M -1/5 17/5
x1 2/5 -1/5 2/5
x2 -1/5 3/5 9/5
x3 -1

Согласно условию оптимальности данное решение является оптимальным.

 

– Конец работы –

Эта тема принадлежит разделу:

Методические указания по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии

Национальный технический университет Украины.. Киевский политехнический институт.. Симплекс метод..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: М - метод

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Формы ЗЛП
Задача математического программирования вида: называется задачей линейного программирования (ЗЛП). Основн

Эквивалентность различных форм ЗЛП
Все перечисленные формы ЗЛП являются эквивалентными в том смысле, что простыми преобразова­ниями задачу, имеющую одну из форм, легко привести к задаче, имеющей одну из оставшихся форм, причем по оп

Решение
Так как первое ограничение имеет знак “≥”, то в левую часть ограничения вводим избыточную переменную s1. Данное ограничение будет иметь вид: x1 + 2x2

Решение
В этом случае на переменную x2 не накладывается ограничение неотрицательности. Введя две новые неотрицательные переменные x2+≥0, x2–X

Упражнения
1) Укажите, какая из ниже приведенных форм задач является канонической? а) б)

Основные свойства ЗЛП
Для ЗЛП справедлива следующая теорема. Теорема (о существовании решения). Если допустимое множество X ЗЛП не пусто, а значение её конечно, то эта задача имеет решение.  

Способ перехода от одного ДБР к другому
Пусть ДБР x0 соответствует преобразованной задаче (13)-(15). Перейдем от него к новому ДБР x1. При этом рассмотрим возможность того, что только одна небазисная переменн

Условие оптимальности ДБР
Определение. Вектор-строка, на которую умножается слева xN в уравнении для ЦФ (13), называется век­тором относительных оценок, т.к. он указывает, в какую сторону

Табличный симплекс-метод
Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые m столбцов матри­цы A. Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расши

Z-строка
Текущая z-строка:(-1 –3/2 0 0 0 0 | 0) –(–3/2) × Новая ведущая строка:(-3 3/2 3/2 0 0 0 | 3) =Новая z-строка:(-4 0 3/2 0 0 0 | 3) БП

Двухэтапный метод
Исторически первым появился М-метод, но он имеет существенный недостаток: возможность появления ошибок в вычислениях, обусловленных очень боль­шой величиной коэффициента М. Например: М=100

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

Отсутствие допустимых решений
Если ограничения модели одновременно выполняться не могут, то задача не имеет допустимых решений. Такое решение всегда существует, когда все ограничения типа "≤", поскольку введение

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги