Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2017-10-01 | 372 |
5.00
из
|
Заказать работу |
Условие задачи (4.1) и (4.4) записываем в виде табл. (4.5), причем ограничения на знак переменной вида хк ≥ 0 в таблицу не включаем (как отмечалось выше). Независимые переменные, на знаки которых наложены ограничения, называются несвободными, а переменные не имеющие таких ограничений называются свободными.
Пусть, например, в табл. (4.6) после шага модифицированного жорданова исключения все свободные члены dm ≥ 0, т.е. неотрицательны. В этом случае получено одно из опорных решений задачи.
Если же в табл. (4.6) имеется, хотя бы один, отрицательный свободный член, например dm < 0, то полученный план не является опорным.
Для определения опорного плана выполняем шаг модифицированного жорданова исключения, что соответствует переходу от одной вершины многогранника решений к соседней.
Разрешающий элемент в симплексной таблице выбирается по правилу:
1. Отыскивается строка с отрицательным свободным членом (если их несколько, то выбирается строка с наибольшим по модулю отрицательным свободным членом).
Если среди коэффициентов взятой строки нет отрицательных, то система (4.2) несовместна.
2. Если в рассматриваемой строке имеются отрицательные коэффициенты, то выбирается любой из них (обычно наибольший по абсолютной величине) и столбец с этим коэффициентом принимается за разрешающий.
3. При выборе разрешающей строки вычисляются все неотрицательные отношения значений свободных членов к соответствующим коэффициентам разрешающего столбца, определяется наименьшее и принимается соответствующая строка в качестве разрешающей, а коэффициент, стоящий в знаменателе этого отношения, за разрешающий элемент.
Например, таким отношением пусть будет , тогда разрешающим элементом будет ars. В
случае, когда , то в качестве разрешающего принимается положительный элемент матрицы, т.е. ars > 0.
Пример 4.1
(4.7)
(4.8)
Найти опорное решение задачи линейного программирования:
Решение
1. Вводим зависимые переменные и перепишем ограничения (4.8) в виде:
(4.9)
Целевую функцию (4.7) запишем в виде: Z = - (-4х1 + 2х2 - 3 х3) + 5.
2. Составляем симплексную табл. (4.10):
(4.10)
Исходное решение не является опорным, так как в столбце свободных членов имеется два отрицательных элемента (-2 во второй строке и -3 в четвертой строке) в табл. 4.10.
3. Так как по условию задачи на переменную х3 ограничений на знак нет, то ее можно исключить из таблицы. Исключаем свободную переменную лг3, выполняя шаг модифицированного жорданова исключения с разрешающим элементом а43 = 1 для табл. (4.10), причем ограничений на выбор разрешающего элемента нет. Этот элемент выбираем в столбце под свободной переменной и отмечаем его квадратиком.
Из табл. (4.11) выписываем выражение для х3
(4.11)
x3 = 2x1 + x2 – y4 – 3 (4.12)
и вычеркиваем четвертую строку в этой таблице, записывая таблицу в виде:
(4.13)
4. Отыскиваем опорное решение, исключая отрицательный свободный член в табл. (4.13). Выполняем шаг модифицированного жорданова исключения с разрешающим элементом ars. Для выбора разрешающего элемента поступаем следующим образом: во второй строке отрицательный свободный член равен -8, а коэффициент в первом столбце равен -5 и принимаем его за разрешающий столбец. В качестве
Меньшее из них , но в случае вырождения следует разрешающим элементом принимать число в знаменателе, если оно положительное. Следовательно, выбираем и проведем шаг модифицированного жорданова исключения, который приводит к решению задачи в виде табл. (4.14).
(4.14)
Выписываем решения задачи из табл. (4.14). Переменные, расположенные на верху таблицы, равны нулю, т.е. у2 = х2 = у4 = 0, а значения переменных; расположенных в левом столбце таблицы, равны , , , Z = 12.
. Значение свободной х3 определяем из соотношения (4.12):
Итак, план (решение) задачи является опорным, так как все свободные члены табл. (4.12) положительны (элементы столбца, расположенные под 1).
Проверка значения целевой функции:
Ответ:
Пример 4.2
Для заданной целевой функции
(4.15)
при линейных ограничениях:
(4.16)
и условиях:
(4.17)
определить опорное решение.
Решение
1. Вводим зависимые переменные и запишем условие задачи (4.15)-(4.17) в виде
4.18)
(4.19)
2. Составляем симплексную таблицу, размещая на верху таблицы независимые переменные «-хк», а в левом столбце — зависимые переменные yi и целевую функцию Z. Коэффициенты при переменных находятся в соответствующих строках и столбцах таблицы. Свободные члены уравнений записываем в последнем столбце под «1». Табл. № 1 имеет вид:
Номера таблицы будем указывать в левом верхнем углу симплексной таблицы. Исходное решение задачи (первоначальный план) не является опорным, так как при (все переменные, расположенные на верху таблицы, равны нулю) Значение не удовлетворяет условию задачи.
Исключаем свободную переменную х2, выполняя шаг модифицированного жорданова исключения с разрешающим элементом а32 = -2, (при этом ограничений на его выбор нет).
Получим табл. № 2:
Выписываем выражение для х2
и вычеркиваем третью строку в табл. № 2.
Решение задачи остается неопорным, так как в первой строке свободный член равен -1, а коэффициенты этой строки являются положительными. Следовательно, система ограничений несовместна.
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!