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

АНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Симплексный метод заключается в определении опорного решения (плана) среди решений системы линейных ограничений-неравенств, за­тем поэтапным переходом к оптимальному решению.

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

Пусть основная задача линейного программирования записана в виде:

Z = c₁x₁ + c₂x₂ + …+ c_nx_n → max (4.1)

a_i1x₁ + a_i2x₂ + … + a_inx_n ≤ b_i, i = (1,m) (4.2)

где m > n и x_k ≥ 0, k = (1,n) (4.3)

Введем зависимые переменные согласно условиям y_i ≥ 0 и ограниче­ния (4.2) перепишем в виде:

y_i = - a_i1x₁ – a_i2x₂ - … - a_inx_n + b_i ≥ 0, i = (1,m) (4.4)

Исходную задачу (4.1) и (4.4) представим в табличной форме (4.5):

(4.5)

Один шаг модифицированного исключения с разрешающим элемен­том a_rs означает переход к новой таблице (4.6), которая получается из табл. (4.5) по правилам:

1. зависимая переменная у_r и независимая x_s меняются местами, т.е. превращаются зависимые переменные в независимые;

2. разрешающий элемент a_rs заменяем на обратную величину (1/ a_rs);

3. остальные (кроме разрешающего) элементы разрешающей строки де­лятся на разрешающий элемент a_rs;

4. остальные элементы разрешающего столбца делятся на отрицатель­ное значение разрешающего элемента, т.е. (-a_rs);

5. элементы b_jk (i ≠r,s≠ к), т.е. элементы матрицы (4.6), не принадлежа­щие разрешающим столбцу и строке, вычисляются по формуле:

или по правилу так называемого «прямоугольника»

(4.6)

Решение задачи линейного программирования состоит из двух этапов:

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

2. Определение оптимального решения (плана), задачи, т.е. отыскание экстремальных значений целевой функции (max или min).

Условием оптимальности при определении максимального значения целевой функции является отсутствие отрицательных коэффициентов в Z — строке, табл. (4.6), кроме свободного члена Q.

ОПРЕДЕЛЕНИЕ ОПОРНОГО РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ

Условие задачи (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, а коэффициенты этой строки являются положитель­ными. Следовательно, система ограничений несовместна.

12	Поделиться:

Воспользуйтесь поиском по сайту: