Курсовая работа: Использование линейного программирования для решения задач оптимизации

При решении Х₁ значение функции равно F(Х₁ ). Легко понять, что функцию F можно увеличить за счёт увеличения любой из не основных переменных, входящих в выражение Fс положительным коэффициентом. Это можно осуществить, перейдя к новому базисному решению, в котором эта переменная будет не основной, то есть принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдёт в не основные. В данном примере для увеличения F можно переводить в основные любую переменную, так как и х₁ и х₂ входят в выражение для F со знаком «+». Для определённости будем выбирать переменную, имеющую больший коэффициент, то есть х₂ . Система (10) накладывает ограничения на рост переменной х₂ . Поскольку необходимо сохранять допустимость решений, то есть все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁ = 0 как не основная переменная):

х₃ = 75 - х₂ ≥ 0; х₂ ≤ 75;

х₄ = 30 - х₂ ≥ 0; откуда х₂ ≤ 30;

х₅ = 84 - 4х₂ ≥ 0; х₂ ≤ 84.

Каждое уравнение системы, определяет оценочное отношение – границу роста переменной х_2, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной свободного члена к коэффициенту при х₂ при условии, что эти числа имеют разные знаки.

Очевидно, что сохранение неотрицательности всех переменных возможно, если не нарушается ни одна из полученных границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ = min {75, 30, 84/4} = 84/4 = 21. При х₂ = 21 переменная х = 0 и переходит в не основные.

Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (то есть, где оценка минимальна), называется разрешающим. В данном случае – это третье уравнение.

IIшаг.

Основные переменные: х₂ , х₃ , х_4.

Не основные переменные: х₁ , х_{. .}

Выразим основные переменные через новые не основные, начиная с разрешающего уравнения(его используем для записи выражения для х₂ ) :

х₂ = (84 - х₁ - х₅ )/4;

х₃ = 75 - 3х ₁ - 84/4 + х₁ /4 + х₅ /4;

х₄ = 30 - х₁ - 84/4 + х₁ /4 + х₅ /4;

или

х₂ =21 0,25 х₁ - 0,25х₅ ;

х=54 - 2,75х₁ + 0,25х₅ ;

х=9 - 0,75х₁ + 0,25х₅ .

Второе базисное решение Х₂ = (0, 21, 54, 9, 0 ) является допустимым.

Выразив линейную функцию через не основные переменные на этом шаге, получаем:

F = 30х₁ + 40 (84 - х₁ - х₅ )/4 = 840 + 20х₁ - 10х₅

Значение линейной функции F₂ = F(X₂ ) = 840.

Поскольку необходимо сохранять допустимость решений, то должны выполняться следующие неравенства(при этом х₁ = 0 как не основная переменная):

х₂ =21 - 0,25х₅ ≥ 0; х₅ ≤ 84;

х₃ =54+ 0,25х₅ ≥ 0; откуда х₅ ≤ -216; (11)

х₄ =9 + 0,25х₅ ≥ 0. х₅ ≤ -36 .

Обнаруживаем возможность дальнейшего увеличения линейной функции за счёт переменной х_1, входящей в выражение для F с положительным коэффициентом. Система уравнений (11) определяет наибольшее возможное значение для х₅ :

Х₅ = min {84, -216,-36} = -36 .

При х₅ = -36 х₄ = 0 переходит в неосновные переменные.