Смешанная система ограничений

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

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

(4.40)

Введем зависимые переменные y _i ≥0' для системы неравенств и 0-стро-ки для соответствующей системы уравнений и запишем ограничения в виде:

(4.41)

Составим симплексную табл. (4.42), включая в нее независимые, за­висимые переменные, 0-строки и целевую функцию в виде:

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

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

После исключения всех 0-строк приступаем к определению опорного, а затем и оптимального решения задачи.

Таким образом, решение задачи линейного программирования со смешанными ограничениями выполняется в такой последовательности:

1. Исключение свободных независимых переменных х_к, если они имеются в условии задачи.

2. Исключение 0-строк по соответствующим правилам.

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

4. Определение оптимального решения. Условием оптимальности при определении максимума (минимума) целевой функции явля­ется наличие неотрицательных (неположительных) коэффициен­тов в Z-строке симплекс-таблицы.

Пример 4.7

Определить максимальное значение линейной целевой функции

(4.43)

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

(4.44)

и условиях:

(4.45)

Решение

1. Вводим зависимые переменные и перепишем условие задачи (4.43) и (4.44) в виде:

 

(4.47)

2. Запишем условие задачи (4.46) и (4.47) в табл. № 1, включая в нее за­висимые, независимые переменные и целевую функцию:

3. Так как независимые переменные х_к являются несвободными, то ис­ключаем 0-строку.

В качестве разрешающего столбца принимаем любой положительный коэффициент 0-строки, например, a₄₁ = 2. Разрешающую строку опре­делим из условия:

Следовательно, разрешающим элементом будет а₂₁ = -2. Выполняя шаг модифицированного жорданова исключения с разрешающим элементом а₂₁ = -2, отмеченный в табл. № 1 квадратиком. Получаем решение задачи в виде табл. № 2:

 

(4.49)

4. В табл. № 20 строка осталась. Исключаем ее, выполняя шаг модифици­рованного жорданова исключения с разрешающим элементом а₄₃ = 1. Получаем табл. № 3 в виде:

Вычеркивая в табл. № 3 0-столбец, получаем решение опорное и опти­мальное.

Выпишем решение задачи из табл. № 3 и проверим условия (4.46) и зна­чение целевой функции (4.47):

Пример 4.8

Найти неотрицательные значения переменных x₁,x₂ и х₃ доставляю­щие целевой функции

(4.48)

максимальное значение и удовлетворяющие смешанным ограничениям:

(4.50)

и условиям:

Решение

1. Перепишем ограничения (4.49) с учетом введенных переменных

2. Составляем симплексную табл. № 1

3. Исключаем свободную переменную х₃ в табл. № 1, выполняя шаг мо­дифицированного жорданова исключения с разрешающим элемен­том а₄₃ = 1. Получим табл. № 2:

В табл. № 2 вычеркиваем 0-столбец, выписываем выражение для не­зависимой переменной хъ

и вычеркиваем четвертую строку.

Получаем табл. № 3, уменьшенную на одну строку и один столбец:

4. Полученное решение не является опорным, так как в столбце свобод­ных членов имеется два отрицательных числа -13 и -7. Выполним шаг модифицированного жорданова исключения с разрешающим элемен­том а₁₂ = -5, получим табл. № 4:

5. Решение остается неопорным, поэтому выполним шаг модифи­цированного жорданова исключения с разрешающим элементом а₂₂ = -1 в табл. № 5:

6. Полученное решение является опорным, но неоптимальным, посколь­ку в Z-строке первый коэффициент — отрицательный, равный - 6/5.Выполним шаг модифицированного жорданова исключения с разрешающим элементом . Получим табл. № 6 в виде:

7. Из табл. № 6 выписываем решение задачи:

Проверка.

 

Пример 4.9

Найти максимальное значение линейной целевой функции

(4.51)

переменные которой удовлетворяют смешанным линейным ограничени­ям-неравенствам:

(4.52)

и условиям:

(4.53)

 

Решение

1. Вводим зависимые переменные записав условие задачи (4.51)-(4.53) в виде:

(4.54)

2. Составляем симплексную табл. № 1, представляя условие задачи (4.54) в табличной форме, включая в нее все переменные, 0-строку и целе­вую функцию Z:

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

Полученная табл. № 2 имеет вид:

Запишем значение переменной х₂ из табл. № 2

и вычеркнем вторую строку этой таблицы. Получаем табл. № 3 в виде:

4. Исключаем 0-строку в табл. № 3, выполняя шаг модифицированного жорданова исключения с разрешающим первым столбцом (в 0-строке этот коэффициент равен 2), а строку определяем из условия:

Следовательно, а₃₁ = 2. Тогда табл. № 4 имеет вид:

В табл. № 4 вычеркнем 0-столбец и получим решение в виде табл. № 5:

 

 

Решение задачи, записанное в табл. № 5, не является опорным, так как у₃ = -6. В качестве разрешающего берем столбец, содержащий отрица­тельный элемент, равный -2.

Разрешающую строку определяем из условия

Выполнив шаг модифицированного жорданова исключения с разре­шающим элементом а₁₁ = 3, получим табл. № 6:

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

Пример 4.10

Найти максимальное значение линейной целевой функции

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

(4.55)

и условиях:

(4.56)

(4.57)

 

Решение

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

 

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

(4.58)

Целевую функцию представим в виде:

(4.59)

2. Составляем симплексную табл. № 1, включая в нее зависимые y_i, не­зависимые переменные х_k, 0-строку (4.58) и Z-строку (4.59):

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

и вычеркиваем вторую строку табл. № 2. Получаем табл. № 3 в виде:

4. Исключаем 0-строку в табл. № 3, выбирая разрешающий столбец с коэффициентом, равным 2, в качестве разрешающей принимаем строку из условия:

Выполним шаг модифицированного жорданова исключения с разре­шающим элементом а₃₁ = 2 и получим табл. № 4:

В табл. № 4 вычеркнем 0-столбец и запишем полученную таблицу в виде:

Решение, представленное табл. № 5, не является опорным, так как у₃ = -9, что не удовлетворяет условию 5. Определяем опорное решение задачи, выполняя шаг модифициро­ванного жорданова исключения с разрешающим элементом а₁₁ = 3. Получаем табл. № 6:

Решение получили неопорное, поэтому выполним шаг модифициро­ванного жорданова исключения с разрешающим элементом и получим табл. № 7:

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