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

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

 
  смешанная система ограничений - student2.ru

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

(4.40)

 
  смешанная система ограничений - student2.ru

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

(4.41)

 
  смешанная система ограничений - student2.ru

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

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

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

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

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

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

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

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

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

Пример 4.7

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

смешанная система ограничений - student2.ru

(4.43)

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

смешанная система ограничений - student2.ru

(4.44)

и условиях:

(4.45)

смешанная система ограничений - student2.ru

Решение

смешанная система ограничений - student2.ru смешанная система ограничений - student2.ru

1. Вводим зависимые переменные смешанная система ограничений - student2.ru и перепишем условие задачи (4.43) и (4.44) в виде:

смешанная система ограничений - student2.ru

(4.47)

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

смешанная система ограничений - student2.ru

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

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

(4.49)

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

смешанная система ограничений - student2.ru

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

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

смешанная система ограничений - student2.ru

Пример 4.8

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

(4.48)

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

(4.50)

и условиям:

смешанная система ограничений - student2.ru

Решение

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

смешанная система ограничений - student2.ru

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

 
  смешанная система ограничений - student2.ru

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

 
  смешанная система ограничений - student2.ru

Проверка.

смешанная система ограничений - student2.ru

Пример 4.9

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

(4.51)

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru (4.52)

и условиям:

смешанная система ограничений - student2.ru (4.53)

Решение

1. Вводим зависимые переменные смешанная система ограничений - student2.ru записав условие задачи (4.51)-(4.53) в виде:

смешанная система ограничений - student2.ru

(4.54)

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

 
  смешанная система ограничений - student2.ru

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

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

 
  смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

 
  смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru Разрешающую строку определяем из условия

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

смешанная система ограничений - student2.ru

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

Пример 4.10

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

смешанная система ограничений - student2.ru

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

(4.55)

смешанная система ограничений - student2.ru

и условиях:

(4.56)

(4.57)

смешанная система ограничений - student2.ru

Решение

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru (4.58)

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

смешанная система ограничений - student2.ru

(4.59)

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

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

смешанная система ограничений - student2.ru

Наши рекомендации