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

Симплекс-метод

Читайте также:
  1. I. 3.2. Двойственный симплекс-метод.
  2. I.2.3. Табличный симплекс-метод.
  3. I.2.4. Алгоритм симплекс-метода.
  4. Алгоритм симплекс-метода
  5. Алгоритм симплекс-метода.
  6. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
  7. Задание 3. Решение задач линейного программирования симплекс-методом
  8. Задача 3. Составить математическую модель, решить задачу симплекс-методом.
  9. Модифицированный симплекс-метод
  10. Описание второго алгоритма симплекс-метода
  11. Описание первого алгоритма симплекс-метода
  12. ПРИЛОЖЕНИЕ 6. КОМПЬЮТЕРНАЯ ПРОГРАММА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

Алгоритм метода рассмотрим для линейной задачи, в которой требуется найти экстремум целевой функции

Z = z 1 x 1 +z 2 x 2 ® extr,

при ограничениях-равенствах

a 11 x 1 +a 12 x 2 + х 3 = b 1;

a 21 x 1 +a 22 x 2 + х 4 = b2;

a 31 x 1 +a 32 x 2 + х 5 = b 3

и граничных условиях неотрицательности переменных

х i > 0, i = 1, 2,...5.

х 1 х 2 х 3 х 4 х 5 b; Z

a 11 a 12       b 1
a 21 a 22       b 2
a 31 a 32       b 3
z 1 z 2       -Z

 

Исходное решение:

свободные переменные x 1 = 0; x 2 = 0;

базисные переменные х 3 = b 1; х 4 = b 2; х 5 = b 3;

целевая функция –Z=0.

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


Это универсальный метод решения линейных оптимизационных задач;

Метод основан на таком переборе решений, что на каждом шаге решение улучшается;

Метод состоит из двух этапов: на первом этапе ищется допустимое решение; на втором – оптимальное решение.

1. В табличной записи просматривается столбец свободных членов bj. Если все bj >0, выполня-ется переход к п.4. Если есть bj <0, то соответ-ствующая строка будет разрешающей.

2. Просматриваются коэффициенты aij разрешаю-щей строки. Выбирается отрицательный коэф-фициент и соответствующий столбец будет разрешающим.

3. Выполняется пересчет всех коэффициентов таблицы, включая значение целевой функции и ее коэффициенты zi. Переход к п.1

4. Просматриваются коэффициенты z i. Если все z i³0 (при поиске минимума Z) или все z i £ 0 (при поиске максимума Z), то текущее решение будет оптимальным, вычисления заканчиваются.

5. Если есть z i<0 (при поиске минимума Z) или z i>0 (при поиске максимума Z), то соответ-ствующий столбец будет разрешающим.

6. Вычисляются отношения свободных членов b j к положительным коэффициентам a ji разрешающе-го столбца. Строка, отвечающая минимальному из этих отношений будет разрешающей.

7. Выполняется пересчет всех коэффициентов таблицы. Переход к п. 4.

Тесты


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

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



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