2. метод больших штрафов (М –метод) icon

2. метод больших штрафов (М –метод)




Скачати 59.67 Kb.
Назва2. метод больших штрафов (М –метод)
Дата20.09.2012
Розмір59.67 Kb.
ТипРешение

2 . 5. МЕТОД БОЛЬШИХ ШТРАФОВ (М –метод)

Если в исходной задаче ЛП хотя бы одно ограничение имеет знак = или > , то сразу получить начальное допустимое решение не удается. Действительно , пусть требуется найти такие X1 и Х2 , которые обеспечивают max L = 2X1 + X2 при ограничениях



Х1 + 2Х2 = 6 ;

Х1 – Х2 > 2 ;

Х1 < 5 ;

Х1 , Х2. > 0 .


В стандартной форме эта задача имеет вид :

max L = 2Х1 + Х2 ;

Х1 + 2Х2 = 6 ;

Х1 – Х2 – Х3 = 2 ;

Х1 + Х4 = 5;

Х1 , Х2 , Х3 , Х4 > 0 .


Имеем три уравнения (m = 3) и четыре неизвестных n = 4. Это означает , что каждому базисному решению соответствует одна

( n – m = 1) небазисная ( равная нулю ) переменная . Приравняем , например , Х1 нулю , получаем Х4 = 5 ; Х2 = 3 ; Х3 = -5 , но это решение не является допустимым ( Х3 не является неотрицательной ).

Для простого получения начального допустимого решения разработан метод больших штрафов или М – метод. Суть его в следующем. В уравнения, которые в исходном виде были записаны со знаками >- и = , вводят искусственные неотрицательные переменные R і.

Для рассматриваемого примера имеем:

min L = 3 Х 1 + Х 2 + MR 1 ;

5 Х 1 + 4 Х 2 –Х 3 + R 1 =25 ;

Х 1 + Х 4 = 3 ;

Х 1, Х 2, Х 3, Х 4, R 1 > 0 .


За использование этих переменных в составе целевой функции вводят штраф, используя большой положительный коэффициент М. На конечной стадии оптимизации переменные R i должны принять нулевое значение, при этом не будет их влияния на целевую функцию. Очевидно, что в задаче максимизации коэффициент М вводится в целевую функцию со знаком минус, а в задаче минимизации со знаком плюс. Это обусловит недопустимость положительных значений искусственных переменных в оптимальном решении.

После введения искусственных переменных легко получается начальное допустимое решение путём приравнивания к нулю n-m переменных . В рассматриваемом примере n – m = 5 – 2 = 3. Приравнивая нулю Х 1, Х 2 и Х 3 получаем R 1 = 25 и Х 4 = 3 .

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

В рассматриваемой примере


R 1 = 25 - 5 Х 1 – 4 Х 2 + Х 3 .


Тогда


L = 3 Х 1 + Х 2 + MR 1 = 3 Х 1 + Х 2 + М ( 25 – 5 Х 1 – 4 Х 2 +

Х 3 ) = ( 3 – 5 М ) Х 1 + ( 1- 4 М ) Х 2 +МХ 3 +25М.


Симплекс – таблица, соответствующая начальному допустимому решению , имеет вид


БП

Х1

Х2

Х3


Х4

R1

Решение




R1

5

4

-1

0

1

25




Х4

1

0

0

1

0

3

Ведущая строка

L


-3+5М

-1+4М



0

0

25М







Ведущий столбец


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


БП

Х1

Х2

Х3

Х4

R1

Решение



R1


0

4

-1

-5

1

10

Ведущая строка

Х1

1

0

0

1

0

3




L

0

-1+4М



3-5М

0

9+10М




























Х2

0

1

-1/4

-5/4

1/4

2,5




Х1

1

0

0

1

0

3




L

0

0

-1/4

7/4

¼-М

11,5






Оптимальное решение следующее : Х1 = 3; Х2 = 2,5 ;

min L = 11,5.


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

Схожі:

2. метод больших штрафов (М –метод) icon2. метод больших штрафов (М –метод)
Имеем три уравнения (m = 3) и четыре неизвестных n = Это означает, что каждому базисному решению соответствует одна
2. метод больших штрафов (М –метод) iconТеоретичні питання з курсу „Аналітична геометрія та лінійна алгебра
Системи лінійних рівнянь. Основні означення. Методи розв’язування (метод Крамера, метод Гауса, матричний метод). Приклади
2. метод больших штрафов (М –метод) iconТеоретичні питання з курсу „Аналітична геометрія та лінійна алгебра
Системи лінійних рівнянь. Основні означення. Методи розв’язування (метод Крамера, метод Гауса, матричний метод). Приклади
2. метод больших штрафов (М –метод) iconДокументи
1. /Метод. реком. ДОШК_ЛЬНА ОСВ_ТА 2012-2013.doc
2. /Метод....

2. метод больших штрафов (М –метод) iconНазва модуля: Теорія керування Код модуля: пм 6111 С01
Задачі теорії оптимальних систем керування, метод фазових траєкторій, метод гармонічної лінеаризації, спостережуваність та керованість...
2. метод больших штрафов (М –метод) iconПитання до екзамену з дисципліни «пускорегулюючі апарати»
Методи розрахунку кіл з розрядними лампами: метод гармонічного аналізу, метод еквівалентних синусоїд, метод "припасовування", машинні...
2. метод больших штрафов (М –метод) iconЗафарбування. Метод гуро І фонга
Основна причина популярності алгоритмів зафарбування, заснованих на розбитті на багатокутники, існування двох методів зафарбування:...
2. метод больших штрафов (М –метод) iconДокументи
1. /Дистанц_йне (заочне ) та п_слядипломне навчання/метод.вказ_вки по фармакогноз_х/ал1.doc
2. метод больших штрафов (М –метод) iconПитання на модуль 2 з дисципліни «пускорегулюючі апарати»
Опишіть метод розрахунку електричних кіл з розрядними лампами : метод гармонічного аналізу (недоліки, переваги)
2. метод больших штрафов (М –метод) iconДокументи
1. /Метод вказ СТОМАТ_01.doc
2. /Метод вказ...

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи