Студопедия  
Главная страница | Контакты | Случайная страница

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

Алгоритм симплексного метода.

Читайте также:
  1. Алгоритм взятия мазка из носа и зева.
  2. Алгоритм внутривенной инъекции
  3. Алгоритм выбора Н или НН в разных частях речи
  4. Алгоритм выполнения задания
  5. Алгоритм выполнения расчетов.
  6. Алгоритм действий медсестры при критическом снижении температуры
  7. Алгоритм действия.
  8. Алгоритм действия.
  9. Алгоритм действия.
  10. Алгоритм Деккера

1.Математическую модель задачи привести к каноническому (стандартному) виду.

2. Построить начальную симплекс-таблицу исходя из стандартного вида.

3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.

4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).

5.Построить новую симплекс-таблицу-второй шаг.

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

* Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент.

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

6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.

Прямая задача на минимум решается следующим образом:

* Написать математическую модель двойственной задачи в стандартном виде

* Решить двойственную модель симплекс - методом

* Записать ответ.

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

Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.

Х1 x2 xn S1 S2 Sm
S1 S2 Sm y1 y2 ym

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

Схема решения задачи симплексным методом (Это может быть и не то)

1) указывается способ вычисления первоначального допустимого решения задачи.

2) при помощи признака оптимальности проверяется не является ли это решение оптимальным.

3) по выбранному начальному решению строятся другие решения, более близкие к оптимальному.

Алгоритм перехода к симплекс-таблице № 2:

1) Неизвестные x 2 и x 4 меняют местами.

2) Разрешающий элемент a 24 заменяют обратной величиной.

3) Остальные элементы разрешающей строки делим на разрешающий элемент.

4) Элементы разрешающего столбца, кроме разрешающего

элемента, делят на разрешающий элемент и

меняют знаки.

5) Все остальные элементы симплекс–таблицы № 2 получают по правилу прямоугольника: Из произведения элементов диагонали, содержащей искомый элемент, вычитают произведение элементов противоположной диагонали и делят всё на элемент, противоположный искомому.




Дата добавления: 2015-02-16; просмотров: 45 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав