Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2017-10-01 | 468 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!