Лекции.Орг


Поиск:




Двойственный симплексный метод




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

В двойственном симплексном методе оптимальный план получается в результате движения по псевдопланам.

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

Алгоритм двойственного симплексного метода включает следующие этапы.

1. Составление псевдоплана. Систему ограничений исходной задачи требуется привести к системе неравенств смысла «». Для этого обе части неравенств смысла «» необходимо умножить на (—1). Затем от системы неравенств смысла «» переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. Первый опорный план заносят в симплексную таблицу.

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

Если в опорном плане условия оптимальности удовлетворяются и все значения базисных переменных – положительные числа, то получен оптимальный план. Наличие отрицательных значений в столбце «Значения базисных переменных» свидетельствует о получении псевдоплана.

3. Выбор ведущих строки и столбца. Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.

Симплексную таблицу дополняют строкой , в которую заносят взятые по абсолютной величине результаты деления коэффициентов индексной строки на отрицательные коэффициенты ведущей строки. Минимальные значения определяют ведущий столбец и переменную, вводимую в базис. На пересечении ведущих строки и столбца находится разрешающий элемент.

4. Расчет нового опорного плана. Новый план получаем в результате пересчета симплексной таблицы методом Жордана - Гаусса. Далее переходим к этапу 2.

 

Пример 1. Известно, что содержание трех питательных веществ А, В и С в рационе должно быть не менее 60, 50 и 12 единиц соответственно. Указанные питательные вещества содержат три вида продуктов. Содержание единиц питательных веществ в одном килограмме каждого из видов продукта приведено в таблице 2.6.1.

Определите дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

Таблица 2.6.1

Питательные вещества Количество единиц питательных веществ в 1 кг продукта вида
I II III
А      
В      
С      
Цена 1 кг продукта      

 





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


Дата добавления: 2016-10-30; Мы поможем в написании ваших работ!; просмотров: 1017 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Большинство людей упускают появившуюся возможность, потому что она бывает одета в комбинезон и с виду напоминает работу © Томас Эдисон
==> читать все изречения...

1027 - | 841 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.