Определение опорного решения задачи линейного программирования симплексным методом

Условие задачи (4.1) и (4.4) записываем в виде табл. (4.5), причем ог­раничения на знак переменной вида х_к ≥ 0 в таблицу не включаем (как отмечалось выше). Независимые переменные, на знаки которых наложе­ны ограничения, называются несвободными, а переменные не имеющие таких ограничений называются свободными.

Пусть, например, в табл. (4.6) после шага модифицированного жорданова исключения все свободные члены d_m ≥ 0, т.е. неотрицательны. В этом случае получено одно из опорных решений задачи.

Если же в табл. (4.6) имеется, хотя бы один, отрицательный свобод­ный член, например d_m < 0, то полученный план не является опорным.

Для определения опорного плана выполняем шаг модифицирован­ного жорданова исключения, что соответствует переходу от одной вер­шины многогранника решений к соседней.

Разрешающий элемент в симплексной таблице выбирается по правилу:

1. Отыскивается строка с отрицательным свободным членом (если их несколько, то выбирается строка с наибольшим по модулю отрица­тельным свободным членом).

Если среди коэффициентов взятой строки нет отрицательных, то сис­тема (4.2) несовместна.

2. Если в рассматриваемой строке имеются отрицательные коэффици­енты, то выбирается любой из них (обычно наибольший по абсолют­ной величине) и столбец с этим коэффициентом принимается за раз­решающий.

3. При выборе разрешающей строки вычисляются все неотрицательные отношения значений свободных членов к соответствующим коэффициентам разрешающего столбца, определяется наименьшее и прини­мается соответствующая строка в качестве разрешающей, а коэффици­ент, стоящий в знаменателе этого отношения, за разрешающий элемент.

Например, таким отношением пусть будет , тогда разрешающим элементом будет a_rs. В

случае, когда , то в качестве разрешающе­го принимается положительный элемент матрицы, т.е. a_rs > 0.

Пример 4.1

(4.7)

(4.8)

Найти опорное решение задачи линейного программирования:

Решение

1. Вводим зависимые переменные и перепишем ограничения (4.8) в виде:

(4.9)

Целевую функцию (4.7) запишем в виде: Z = - (-4х₁ + 2х₂ - 3х₃) + 5.

2. Составляем симплексную табл. (4.10):

(4.10)

Исходное решение не является опорным, так как в столбце свободных членов имеется два отрицательных элемента (-2 во второй строке и -3 в четвертой строке) в табл. 4.10.

3. Так как по условию задачи на переменную х3ограничений на знак нет, то ее можно исключить из таблицы. Исключаем свободную перемен­ную лг₃, выполняя шаг модифицированного жорданова исключения с разрешающим элементом а₄₃ = 1 для табл. (4.10), причем ограничений на выбор разрешающего элемента нет. Этот элемент выбираем в столбце под свободной переменной и отмечаем его квадратиком.

Из табл. (4.11) выписываем выражение для х3

(4.11)

x₃ = 2x₁ + x₂ – y₄ – 3 (4.12)

и вычеркиваем четвертую строку в этой таблице, записывая таблицу в виде:

(4.13)

4. Отыскиваем опорное решение, исключая отрицательный свободный член в табл. (4.13). Выполняем шаг модифицированного жорданова исключения с разрешающим элементом a_rs. Для выбора разрешающе­го элемента поступаем следующим образом: во второй строке отри­цательный свободный член равен -8, а коэффициент в первом столб­це равен -5 и принимаем его за разрешающий столбец. В качестве

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

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

(4.14)

Выписываем решения задачи из табл. (4.14). Переменные, расположен­ные на верху таблицы, равны нулю, т.е. у₂ = х₂ = у₄ = 0, а значения переменных; расположенных в левом столбце таблицы, равны , , , Z =12.

. Значение свободной х₃определяем из соотношения (4.12):

Итак, план (решение) задачи является опорным, так как все свобод­ные члены табл. (4.12) положительны (элементы столбца, расположенные под 1).

Проверка значения целевой функции:

Ответ:

Пример 4.2

Для заданной целевой функции

(4.15)

при линейных ограничениях:

(4.16)

и условиях:

(4.17)

определить опорное решение.

Решение

1. Вводим зависимые переменные и запишем условие задачи (4.15)-(4.17) в виде

4.18)

(4.19)

2. Составляем симплексную таблицу, размещая на верху таблицы неза­висимые переменные «-х_к», а в левом столбце — зависимые переменные y_iи целевую функцию Z. Коэффициенты при переменных находятся в соответствующих строках и столбцах таблицы. Свободные члены урав­нений записываем в последнем столбце под «1». Табл. № 1 имеет вид:

Номера таблицы будем указывать в левом верхнем углу симплексной таблицы. Исходное решение задачи (первоначальный план) не является опорным, так как при (все переменные, расположенные на верху таблицы, равны нулю) Значение не удовлетворяет условию задачи.

Исключаем свободную переменную х₂, выполняя шаг модифициро­ванного жорданова исключения с разрешающим элементом а₃₂ = -2, (при этом ограничений на его выбор нет).

Получим табл. № 2:

Выписываем выражение для х₂

и вычеркиваем третью строку в табл. № 2.

Решение задачи остается неопорным, так как в первой строке свобод­ный член равен -1, а коэффициенты этой строки являются положитель­ными. Следовательно, система ограничений несовместна.