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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.6.1

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