Контрольная работа: Исследование операций

x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0; x5 >= 0; x6 >= 0; x7 >= 0; x8 >= 0; x9 >= 0; R1 >= 0; R2 >= 0; R3 >= 0; R4 >= 0

Существуют базисные и небазисные переменные.

Включающиеся переменные называются небазисными в данный момент переменными, которые включаются в состав базиса на следующей итерации.

Исключаемые - базисные переменные, которые на следующей итерации подлежат исключению.

На следующем шаге необходимо подставить значение в целевую функцию:

Таким образом, задача в стандартной форме имеет следующий вид:

x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0; x5 >= 0; x6 >= 0; x7 >= 0; x8 >= 0; x9 >= 0; R1 >= 0; R2 >= 0; R3 >= 0; R4 >= 0

Перенесем члены целевой функции влево

z -5x1-1x2 = 0

Далее задача решается обычным симплекс-методом

Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю n- m небазисных переменных.

Шаг 1. Из числа небазисных переменных (равных нулю) выбирается включаемая в новый базис переменная, увеличение которой обеспечивает больший по сравнению с остальными рост целевой функции (условие оптимальности). Если такой переменной нет, вычисления прекращаются и полученное решение является оптимальным. В противном случае, переходят к шагу 2.

Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, значение которой быстрее всех стремится к нулю при переходе к новой смежной точке (становящаяся небазисной и равной нулю при введении в базис новой переменной - условие допустимости).

Шаг 3. Определяется новое базисное решение (соответствующее новой смежной точке, т.е. новому составу базисных и небазисных переменных) и осуществляется переход к шагу 1.