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