|
Чтобы сделать новое допустимое решение базисным, нужно одну переменную х; вывести из базисного решения, а соответствующий вектор из базиса. В этом случае новый базис будет содержать также m векторов. Для этого выбираем значения в соответствии с соотношением (29). Тогда новое базисное решение имеет вид: Х \ ~ ХгтжХ\г'Х2 ~ ХгтахХ2г>Х1\0ПУЩеН)>-">Хт ~ Х г max Xmr > Xr max > (у"/ а новый базис (А ь А2,..., Ац, A i+b ..., Am, Ar). Такой переход от одного базиса к другому позволяет находить решения почти всех задач линейного программирования. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений т и п это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению (ДБР), которому отвечает большее значение целевой функции, используют соответствующий критерий (симплекс-разность) [76, с. 310]. Новому ДБР (28) соответствует следующее значение целевой функции: Z, =С(Х] — xrxlr) + c2{x2 — xrx2r) + ... + ст(хт — хгх тг) + сгх г = (31) = {схх\ + с2х'2 + ... + стх'т) + хг(сг -сххХг -...-стхтг)= = zn + х (с —с,х, —,.. — сх 0 г\ г 1 1г ' Л. т тг/ > где Z значение целевой функции для начального ДБР; o cr-CiXir с2х2г -... cmxmr симплекс-разность для переменной хг. Симплекс-разность вычисляют для каждой переменной, не входящей в базисное решение. Причем, выбирают такую небазисную переменную хг, для которой симплекс-разность положительна и максимальна, и вводят ее в базис с исключением одной переменной из базисного решения и вектора из базиса. Эти вычисления повторяются до тех пор, пока симплекс-разности для всех пере74 |
* х,_=тт{^}, (34) гдех1г>0. Чтобы сделать новое допустимое решение базисным, нужно одну переменную х; вывести из базисного решения, а соответствуюп];ий вектор из базиса. В этом случае новый базис будет содержать также ш векторов. Для этого выбираем значения в соответствии с соотношением (34). Тогда новое базисное решение имеет вид: (35) а новый базис (Аь А2,..., А-^.х, А-^+х,..., А^, Аг). Такой переход от одного базиса к другому позволяет находить решения почти всех задач линейного программирования. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений ш и п это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению (ДБР), которому отвечает большее значение целевой функции, используют соответствующий критерий (симплекс-разность) [113\ Новому ДБР (33) соответствует следующее значение целевой функции: 2, =с,{х1 -х,х„,) + с,(х; -х,Х2,) + ... + с„,(х; х,х„^) + с,.г, = (36) = (с,х; + С 2 Х 2 ' + ... + с„,х^) + хДс, С 1 Х 1 , ...-с„,х„,^= = ^0 +^ЛСг -с,х„.-...-с,„х„^^), где 2о значение целевой функции для начального ДБР; С г С 1 Х 1 г С2Х2Г . . . С щ Х щ г симплекс-разность для переменной Хг. Симплекс-разность вычисляют для каждой переменной, не входящей в базисное решение. Причем, выбирают такую небазисную переменную Хг, для 89 которой симплекс-разность положительна и максимальна, и вводят ее в базис с исключением одной переменной из базисного реп1ения и вектора из базиса. Эти вычисления повторяются до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными. Это и есть признак оптимальности текущего базисного решения. Вычислительные процедуры симплекс-метода состоят из следующих шагов. Шаг 0. Используя линейную модель стандартной формы , определяют начальное допустимое базисное решение путем приравнивания к нулю небазисных переменных. Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый' базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2. Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна принять нулевое значение (стать небазисной) при введении в состав базисных новой переменной. Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход шагу 1. При решении задач линейного программирования с двумя к переменными удобно использовать графический симплексный метод. При большем числе переменных необходимо применение рассмотренного алгебраического аппарата [6, с. 140]. Экстремальная целочисленные программирования. задача, переменные называется которой задачей принимают лишь значения, целочисленного 90 |