|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Симплексный методПриведем задачу к каноническому виду, т.е. неравенства системы преобразуем в уравнения путём введения дополнительных переменных х 3 и х 4.
Переменные x 3 и x 4 в системе линейных уравнений образуют неотрицательный базис, поскольку каждая из них входит только в одно уравнение, причём с коэффициентом единица, и правая часть уравнения неотрицательна.
Представим целевую функцию в неявном виде, перенеся все члены в левую часть уравнения: f – 2 x 1 – x 2= 0. Это уравнение не содержит базисных переменных x 3 и x 4, зато формально содержит переменную f, которую также можно считать базисной. Составим расширенную систему уравнений: Запишем расширенную матрицу этой системы в виде симплексной таблицы. В заголовках столбцов указаны обозначения соответствующих этим столбцам переменных и правой части b, а в заголовках строк - обозначения базисных переменных для соответствующих уравнений.
Заметим, что первую компактную симплексную таблицу нетрудно составить, пользуясь непосредственно записью стандартной задачи: дополнительные переменные – базисные и соответствуют строкам (неравенствам), коэффициенты целевой функции – в нижней строке со знаком (–), в последней клетке нижней строки – нуль. Значения свободных переменных полагаем равными нулю: x 1= x 2= 0, а значения базисных переменных и целевой функции находим в последнем столбце: x 3= 6; x 4= 9; f = 0. Первое базисное решение: С этой целью сначала выбираем ведущий столбец по отрицательному элементу нижней строки (наибольшему по модулю: -2), ¾ столбец x 1. Затем выбираем ведущую строку по наименьшему отношению соответствующих элементов последнего и ведущего столбцов, причём рассматриваем только строки с положительными элементами ведущего столбца. В нашем случае в ведущем столбце два элемента положительны (а 12= 1; а 21= 4), и минимум отношения: min{ Теперь переходим к новой симплексной таблице, используя следующие правила.
1. Меняем местами переменные x 1 и x 4, соответствующие ведущему элементу. 2. На место ведущего элемента (4) записываем обратную ему величину: 3. Остальные элементы ведущей строки делим на ведущий элемент, то есть на 4. 4. Остальные элементы ведущего столбца тоже делим на ведущий элемент Э и меняем знак. 5. Элементы е, не принадлежащие ведущим рядам, можно пересчитывать по правилу прямоугольника, вычитая из е произведение соответствующих ему элементов ab ведущих рядов, делённое на ведущий элемент Э:
или: е заменить на(е -
Например, на место элемента а 12 = 3 запишется: 3 – на место f = 0 запишется: 0 -
Новое базисное решение f = 4,5 не является оптимальным, т.к. в строке f имеется отрицательный элемент (-2,5). Поэтому новый ведущий столбец: x 2. В ведущем столбце только один положительный элемент: 3,75, который и определяет ведущую строку: x 3 (первую строку).Новый ведущий элемент: Э = 3,75. Вводим в базис x 2 (вместо x 3) и строим новую симплексную таблицу.
Например, на месте ведущего элемента Э = 3,75 = В нижней строке последней симплексной таблицы нет отрицательных элементов, поэтому базисное решение
- оптимальное! Проверка №1: f = 2 x 1+ x 2, где x 1= 3, x 2= 1, f = 7. Подставим:
7 = 2×3 + 1; истина. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |