АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. А)Равномерный метод.
  2. Абсорбционный метод.
  3. Адсорбционный метод.
  4. Анкетування - це найбільш поширений у соціології метод.
  5. Бактериологический метод.
  6. Бактериоскопический (микроскопический) метод.
  7. Балансовый метод.
  8. Вопрос – 1 Понятие и особенности мп как отрасли права РФ.Предмет и метод.
  9. И. А. Гончаров: художественное мировоззрение и творческий метод.
  10. Корреляционный метод.
  11. Корреляционный метод.
  12. Метод. Метод простой итерации.

Симплексный метод позволяет путем ряда преобразований, состоящих в переходе от одного опорного решения к другому (причем так, что значение целевой функции все время возрастает (max) или убывает (min)), находить оптимальное решение за конечное число шагов, либо показать неразрешимость исходной задачи.

Подготовка к решению задачи симплексным методом:

1) приведение задачи к каноническому виду

2) приведение системы уравнений к единичному базису

3) нахождение исходного опорного решения

Решение симлекс-методом:

1. Найти опорный план.

2. Составить симплекс-таблицу.

3. Исходный опорный план проверить на оптимальность, в результате чего может иметь место один из 3 случаев:

а) если Δj≥0, то исходный опорный план является оптимальным.

б) если Δj<0 и все элементы соответствующего столбца ≤0, то целевая функция не огранична сверху на множестве ее плана.

в) Δj<0 и для каждого такого j по крайней мере одно aij положительное, то можно перейти от исходного опорного плана к новому опорному плану, при котором значение целевой функции возрастает.

4. Найти разрешающий столбец и разрешающую строку. Разрешающий столбец определяется наибольшей по абсолютной величине отрицательной оценкой Δj. Разрешающая строка определяется минимальным отношением свободных членов к положительным элементам разрешающего столбца.

5. Сделать соответствующие замены в столбцах Вб и Сб и проделать один шаг метода Ж. Гауса с найденный разрешающим элементом. Пересчитать элементы в строке Δ.

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

 

Приращение целевой функции

Приращение – разность между последующей и предыдущей функциями

∆ = Z2 – Z1 >0

X1 àZ(X1) =Z1

| | |

X2 àZ(X2) =Z2

Z2=(z1aij-∆jbi) \ aij=Z1 - ∆jbi\aij

∆ = Z1 - ∆jbi/ aij – Z1 = -∆jbi/ aij > 0

∆j < 0

 

Критерии оптимальности

Теорема 1: Опорный план Х*=(х1*, х2*, 0,…, 0) задачи (1) – (3) является оптимальным, если ∆j ≥0, j = 1, n.

Теорема 2: Если ∆k< 0 для некоторого j=k и среди чисел aik нет положительных (aik ≤ 0), то целевая функция (1) задачи (1) – (3) не ограничена на множестве ее планов.

Теорема 3: Если ∆k < 0 и опорный план Х задачи (1) – (3) не вырожден, но среди чисел aik есть положительные (не все aik ≤ 0), то существует опорный план Х’ такой что Z(X’) >Z(X)

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

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:



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