Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2017-10-16 | 343 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим задачу ЛП, в которой система ограничений задана в виде неравенств смысла "≤".
Требуется найти экстремум функции
(1.23) |
при следующих ограничениях:
(1.24) | |
При использовании симплекс-метода процесс решения проще выполняется в симплексных таблицах.
Алгоритм симплекс-метода.
Построим первоначальный опорный (или базисный) план. От системы неравенств переходим к системе уравнений, вводя дополнительные неотрицательные переменные:
(1.25) |
Дополнительные неотрицательные переменные
будут являться базисными, т.к. последние m столбцов матрицы коэффициентов системы уравнений (1.25) представляют столбцы единичной матрицы, которые являются линейно-независимыми. Следовательно, неотрицательные переменные соответствующие этим столбцам, по определению будут базисными переменными.
Составляем симплексную таблицу, которая состоит из столбцов базисных переменных, свободных членов, контрольных сумм и θ. Последняя строка симплекс-таблицы, называемая индексной, заполняется коэффициентами линейной формы (1.23), взятыми с противоположными знаками (кроме С0).
Проверяем выполнение признака оптимальности для построенного плана. Для того, чтобы план X=(x1, x2, …, xn) был оптимальным, достаточно, чтобы все коэффициенты индексной строки (кроме C0) были неотрицательны при решении задачи ЛП на максимум и не положительны на минимум.
Если признак оптимальности выполняется, то выписываем решение. В столбцах базисных переменных и свободных членов расположены соответственно компоненты и значения построенного оптимального плана, на пересечении индексной строки и столбца свободных членов – экстремальное значение линейной формы L(X).
|
Если признак оптимальности не выполняется, то при решении задачи на максимум из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, а при задаче на минимум из положительных коэффициентов индексной строки выбираем наибольший. Столбец, соответствующий выбранному наибольшему коэффициенту, называется ключевым. Ключевой столбец показывает, какая переменная войдет в базис.
Вычисляем отношения столбца свободных членов только к положительным элементам ключевого столбца (если таковых не имеется, то задача ЛП решения не имеет) и записываем их в столбец θ. Из всех элементов столбца θ выбираем наименьший. Строку симплексной таблицы, содержащую наименьшее значение θ, назовем ключевой. Ключевая строка показывает, какая переменная выйдет из базиса.
На пересечении ключевого столбца и ключевой строки находится генеральный элемент.
Переходим к составлению следующей симплекс-таблицы. Для этого выполняем следующие действия:
a) свободную переменную, соответствующую ключевому столбцу, вводим в базисные переменные, а базисную переменную, соответствующую ключевой строке, переводим в свободные;
b) заполняем направляющую строку новой таблицы, которая составляется из элементов ключевой строки предыдущей таблицы путем деления на генеральный элемент;
c) для перевода переменной, соответствующей ключевому столбцу, из свободной в базисные нужно исключить ее из всех строк, кроме направляющей. Для этого методом Жордана – Гаусса накапливаем нули во всех остальных клетках столбца, соответствующего ключевому столбцу предыдущей таблицы.
Процесс вычислений продолжаем в симплексных таблицах до выполнения признака оптимальности.
Замечание.
Если при оптимальном плане в индексной строке имеется нуль, а столбец, соответствующий ему, содержит не менее двух ненулевых элементов, из которых хотя бы один положительный, то задача ЛП имеет множество оптимальных планов. Действительно, столбец, соответствующий нулю в индексной строке, выбирается за ключевой и строится новый оптимальный план с другим набором базисных переменных, но с тем же самым значением L(X). Тогда по основной теореме ЛП любая выпуклая комбинация этих планов будет тоже оптимальной, следовательно, задача ЛП имеет множество оптимальных планов.
|
Решение контрольного примера.
Найти максимум функции при следующих ограничениях:
1. Вводя дополнительные неотрицательные переменные x3, x4, x5, переходим к системе уравнений
Составим первую симплекс-таблицу с базисными переменными x3, x4, x5. Получаем первоначальный опорный план
X1(0, 0, 15, 8, 7) и L(X1)=0.
2. Проверим полученный план на оптимальность. Так как задача на максимум, то при оптимальном плане в индексной строке не должно быть отрицательных чисел. В индексной строке первой симплекс-таблицы (таблицы 1.1.) имеются два отрицательных коэффициентов.
3. Выбираем среди отрицательных коэффициентов индексной строки наибольший по абсолютной величине: max{/-2/, /-3/}=/-3/. Следовательно, столбец, содержащий переменную x2, будет являться ключевым. Отметим его стрелкой, которая указывает, что переменная x2 из свободных должна перейти в базисные.
4. Для нахождения ключевой строки вычисляем значения θ: элементы столбца свободных членов делим только на положительные элементы ключевого столбца x2. Получаем столбец θ(5,4,-). Находим min{5,4}=4. Следовательно, ключевой строкой будет строка, соответствующая базисной переменной x4. Обозначим эту строку стрелкой, показывающей, что x4 должна из базисных переменных перейти в свободную.
На пересечении ключевой строки и столбца стоит генеральный элемент 2. Выделяем его кружком.
5. После этого переходим к составлению следующей симплекс-таблицы. Заполняем направляющую строку x2, которая получается из ключевой строки x4 предыдущей таблицы путем деления на генеральный элемент 2. В остальных клетках столбца второй симплекс-таблицы (таблица 1.1.) должны накопиться нули, оперируя с элементами направляющей строки.
Так, например, для получения нуля в этом столбце в строке x3, умножим все элементы направляющей строки второй симплекс-таблицы (таблица 1.1.) на соответствующий элемент ключевого столбца первой симплекс-таблицы (таблица 1.1.), взятый с противоположным знаком, т.е. на (-3), и сложим с соответствующими элементами строки x3 первой симплекс-таблицы (таблица 1.1.):
|
Сумма всех элементов этой строки равна 3, следовательно, все элементы строки x3 вычислены правильно.
Строку x5 переписываем во вторую симплекс-таблицу (таблица 1.1.) без изменения, т.к. в ключевом столбце она имеет нуль. Для получения нуля в оставшейся клетке столбца x2 умножим направляющую строку на 3 и сложим с соответствующими элементами строки L(X) первой симплекс-таблицы (таблица 1.1.). В результате заполнения второй симплекс-таблицы (таблица 1.1.) получим второе базисное решение, которое имеет улучшенное значение линейной формы, но не является оптимальным, так как в индексной строке второй симплекс-таблицы (таблица 1.1.) имеется отрицательное число. Решение необходимо продолжить, возвращаясь к шагу 2.
В третьей симплекс-таблице (таблица 1.1.) в индексной строке все коэффициенты неотрицательны, следовательно, X3(6, 1, 0, 0, 1) являются оптимальным решением и L(X3)-Lmax=15.
Но анализ индексной строки показывает, что полученный оптимальный план не является единственным.
Если за ключевой столбец третьей симплекс-таблицы (таблица 1.1.) принять столбец x4 и проделать всю необходимую симплекс-процедуру, то получим другой оптимальный план, но с тем же самым значением Lmax=14 (таблица 1.1.).
Зная два оптимальных решения, можно построить их множество:
где
Полное решение этого примера приводится в симплексной таблице 1.1.
Таблица 1.1.
№ | Базисные переменные | Свободные члены | X1 | X2 | X3 | X4 | X5 | Σ | θ |
1. | X3 | ||||||||
← X4 | |||||||||
X5 | - | ||||||||
L(X) | -2 | -3↑ | -5 | max | |||||
2. | ← X3 | 1/2 | 3/2 | ||||||
X2 | 1/2 | ||||||||
X5 | |||||||||
L(X) | -1/2 ↑ | 3/2 | max | ||||||
3. | X1 | -3 | - | ||||||
X2 | -1 | ½ | |||||||
X5 | -2 | 1/3 | |||||||
L(X) | 0↑ | max | |||||||
4. | X1 | ||||||||
X2 | 1/3 | 1/3 | -2/3 | ||||||
X4 | 1/3 | -2/3 | 1/3 | ||||||
L(X) | max |
|
|
|
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!