Смешанная система ограничений — КиберПедия 

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

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

2017-10-01 468
Смешанная система ограничений 0.00 из 5.00 0 оценок
Заказать работу

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

 
 

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

(4.40)

 
 

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

(4.41)

 
 

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

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

При исключении 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-строки, например, a41 = 2. Разрешающую строку опре­делим из условия:

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

 

(4.49)

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

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

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

Пример 4.8

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

(4.48)

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

(4.50)

и условиям:

Решение

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

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

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

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

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

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

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

5. Решение остается неопорным, поэтому выполним шаг модифи­цированного жорданова исключения с разрешающим элементом а22 = -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. Исключаем свободную независимую переменную х2, выполняя шагмодифицированного жорданова исключения с разрешающим элемен­том а22 = -1.

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

 
 

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

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

 
 

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

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

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


 

 

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

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

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

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

Пример 4.10

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

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

(4.55)

и условиях:

(4.56)

(4.57)

 


Решение

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

 

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

(4.58)

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

(4.59)

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

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

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

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

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

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

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

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

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


Поделиться с друзьями:

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...

Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.055 с.