![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Основы метода
Будем рассматривать каноническую форму задачи линейного программирования. Приведем, прежде всего, систему ограничений к единичному базису и допустим для определенности, что этот базис состоит из первых r столбцов. Кроме того, в записи линейной функции перенесем все переменные в левую часть равенства. Тогда задача II запишется так: Найти решение Х системы уравнений:
удовлетворяющее условиям неотрицательности x1 ≥ 0; x2 ≥ 0; …, xk ≥ 0; …, xn ≥ 0; (2) и максимизирующее линейную функцию z — с1х1 — с2х2 —... — сkхk —... — сnхn =—с0 (3) Допустим, что в системе (1) все свободные члены неотрицательны, т. е. выполняется неравенство bi ≥ 0, для i = 1, 2,..., r. (4) Тогда системе (1) соответствует исходное опорное решение
Подставляя это решение в равенство (3), вычислим соответствующее исходное значение функции z0 = z( Для этого умножим первое уравнение системы (1) на с1, второе — на с2 и т. д., r-е. уравнение — на сr, и сложим с равенством (3). В результате получим Z + a0r+1хr+1 + а0r+2+xr+2 +... + а0k xk+...a0n xn=а00, (6) где b0k= Будем называть равенство (6) приведенным (к свободным переменным) выражением для функции z, а коэффициенты а0k- — оценками соответствующих свободных переменных хk. Способ образования приведенного выражения для функции Z остается в силе и в том случае, когда номер базисной переменной не совпадает с номером уравнения, т. е. когда, например, первое уравнение разрешено относительно х3, второе — относительно х8 и т. д.. Следует лишь в формуле (7) величины сi рассматривать не как коэффициенты при i-й переменной, а как коэффициенты в равенстве (З) при базисной переменной, относительно которой разрешено i-е уравнение. Приведенное выражение (6) позволяет сразу без дополнительных расчетов определить значение z0, соответствующее опорному решению (5): z0+z( Равенство (6) формально не отличается от уравнений системы (1). Поэтому будем рассматривать его как «нулевое» уравнение, разрешенное относительно дополнительной базисной переменной z. Добавив его к системе (1), получим расширенную систему: Заметим, что столбец свободных членов системы (8) содержит полную информацию на данном этапе расчета: первые r его членов определяют исходное опорное решение
Выполним теперь одно симплексное преобразование этой системы при условии, чтобы последнее уравнение не выбиралось в качестве разрешающего (т. е. чтобы z все время оставалось в качестве базисной переменной). При выполнении этого преобразования разрешающий столбец С этим дополнением алгоритм симплексных преобразований включает следующие основные пункты: 1. Выбирается разрешающий столбец аp из условий: оценка а0p < 0 и хотя бы один элемент аiр > 0. (9) 2. Выбирается разрешающая q-я строка из условия:
для aip> 0 З. Производится пересчет элементов разрешающей строки по формуле
4. Вычисляются элементы всех остальных строк (при k ≠ p) по формуле
После выполнения одной итерации придем к новой системе уравнений, приведенной к новому единичному базису. Этот новый базис состоит, как и исходный, из единичных векторов
и новое значение функции z:
Подставляя в (14) значение а0 из (12) и вычитая из нового значения функции исходное, получим изменение функции, достигнутое в результате данной итерации,
В этом выражении Будем полагать вначале, что ни один из свободных членов системы (1) и систем, получаемых после очередных итераций, не обращается в нуль. Случай, когда какой-нибудь из свободных членов аi0 = 0 приводит к так называемому вырожденному решению. Подставляя значение
Таким образом, оценка а0р свободной переменной xр характеризует изменение целевой функции z, приходящееся на каждую единицу изменения значения переменной хр. Этим и объясняется термин “оценка”. Так как Этим объясняется дополнительное условие выбора разрешающего столбца, включенное в п. 1 алгоритма. Если бы решалась задача минимизации функции z, то, очевидно, разрешающий столбец следовало бы выбирать по положительной оценке а0р.
|