Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2017-10-01 | 475 |
5.00
из
|
Заказать работу |
|
|
В некоторых задачах линейного программирования ограничения могут быть заданы в виде системы уравнений или системы уравнений и неравенств, т.е. в виде смешанной системы ограничений. Решение задач с такими ограничениями имеют определенную особенность.
(4.40)
(4.41)
Если по условию задачи некоторые независимые переменные хк являются свободными, т.е. ограничений на знак переменных нет, то их можно исключить из табл. (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 в виде:
Пример 4.9
Найти максимальное значение линейной целевой функции
(4.51)
переменные которой удовлетворяют смешанным линейным ограничениям-неравенствам:
(4.52)
и условиям:
(4.53)
Решение
1. Вводим зависимые переменные записав условие задачи (4.51)-(4.53) в виде:
(4.54)
2. Составляем симплексную табл. № 1, представляя условие задачи (4.54) в табличной форме, включая в нее все переменные, 0-строку и целевую функцию Z:
Полученная табл. № 2 имеет вид:
и вычеркнем вторую строку этой таблицы. Получаем табл. № 3 в виде:
Следовательно, а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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!