Студопедия

КАТЕГОРИИ:

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


Симплекс метод в общем виде




Требуется найти максимум целевой функции:

(1)

При ограничениях:

(2)

И условиях неотрицательности:

xi ≥ 0, i=1, 2, ..., n (3)

Из системы (2) видно, что если за свободные неизвестные принять х1, х2 и положить их равными нулю, то базисные неизвестные х3, х4, х5 будут равны правым частям системы. в результате получаем план:

х1=0, х2=0, х3=b1, x4=b2, x5=b3 (4)

Для которого целевая функция равна

(5)

Выразим из (2) базисные неизвестные х3, х4, х5 через свободные х1, х2:

(6)

Подставим (6) в целевую функцию (1) и после приведения подобных членов будем иметь:

f = (c1–c3a11–c4a21–c5a31)x1 + (c2–c3a12–c4a22–c5a32)x2 + c3b1 + c4b2 + c5b3. (7)

Если коэффициенты перед х1, х2 в (7) окажутся отрицательными, то целевую функцию нельзя увеличить, переводя эти свободные неизвестные в базисные, то есть давая им какие-то положительное значения. Отрицательность коэффициентов перед неизвестными в (7) есть признак того, что найдено оптимальное решение. Коэффициенты перед свободными неизвестными в выражении для целевой функции принято называть оценками. Введем обозначения:

Z1 = c3a11 + c4a21 + c5a31, Z2 = c3a12 + c4a22 + c5a32. (8)

В этих обозначениях условия максимальности запишутся:

c1 – Z1 < 0, c2 – Z2 < 0, (9)

Пусть условии оптимальности (9) не выполнены, а именно пусть, для определенности, коэффициент перед х1 в (7) положителен, тогда, увеличивая х1, мы увеличим целевую функцию по сравнению с ее значением (5). Посмотрим, насколько может быть увеличена переменная х1по сравнению с нулем, при условии, что х2 остается свободной, то есть будет иметь неизменное значение х2=0. Из (6) видно, что увеличение х1 будет вести к уменьшению х3, х4, х5, если коэффициенты перед х1 в (6) отрицательны. Увеличивать х1 можно лишь до значения, при котором первая из неизвестных х3, х4, х5 обратится в нуль. Положив нулю левые части (6), получим три уравнения:

0 = b1 – a11x1, 0 = b2 – a21x1, 0 = b3 – a31x1.

Если положить:

(10)

то только одна неизвестная из х3, х4, х5 обратится в нуль, то есть станет свободной, а остальные останутся положительными. Предположим, что это будет х3, тогда будем иметь в качестве свободных неизвестных х2, х3 и в качестве базисных х1, х4, х5.

Для удобства дальнейших вычислений желательно преобразовать систему ограничений к виду (2), который характерен тем, что столбцы коэффициентов при базисных неизвестных образуют единичную матрицу. Так как старая базисная переменная х3 заменяется новой базисной переменной х1, то в первом уравнении коэффициент перед х1 должен быть равен 1. Это достигается делением первого уравнения на a11. Далее следует исключить неизвестную х1 из второго и третьего уравнений. Для этого преобразованное первое уравнение умножим сначала на а21 и вычтем из второго, затем на а31 и вычтем из третьего. В результате этих преобразований система (2) примет вид:

(11)

Здесь через a1ij обозначены новые значения коэффициентов. Заметим, что подобные преобразования выполняются в методе Гаусса при решении систем линейных уравнений.

Описание выше действия по работе с системой ограничений (2) следует повторить для системы (11) и т.д., до тех пор, пока не будет выполнены условия оптимальности.

Для удобства и компактности вычислений по симлекс-методу применяются симплексные таблицы.


 


Поделиться:

Дата добавления: 2015-08-05; просмотров: 58; Мы поможем в написании вашей работы!; Нарушение авторских прав





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