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

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

Читайте также:
  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 = z1x1+z2x2 ® extr,

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

a11x1+a12x2 + х3 = b1;

a21x1+a22x2 + х4 = b2;

a31x1+a32x2 + х5 = b3

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

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

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

a11 a12 b1
a21 a22 b2
a31 a32 b3
z1 z2 -Z

 

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

свободные переменные x1=0; x2=0;

базисные переменные х3= b1; х4= b2; х5= b3;

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

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


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

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

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

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

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

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

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

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

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

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

Тесты


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


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