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

 

Для получения решения исходной задачи можно перейти к двойственной. А используя оценки ее оптимального плана, можно определить оптимальное решение исходной задачи.

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

b_i являются оценками плана двойственной задачи. С_j являются оценками плана исходной задачи.

Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана исходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи.

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

Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: минимизировать функцию Z=СХ при АХ=A₀, Х>0. Значит в двойственной задаче следует максимизировать функцию f=YA₀ при YA>С. Пусть определен следующий базис D=(A₁, А₂,…, А_i,…, А_m), причем в нем хотя бы одна из компонент вектора Х=D^-1A₀=(x₁, x₂,…, x_i,…, x_m) отрицательная. Для всех векторов A_j используется следующее соотношение Z_j–C_j >0 (i=1,2,…, n).

Пользуясь теоремой двойственности, Y=С_базD^-1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны.

Поэтому, следует исключить из базиса исходной задачи вектор А_i, который соответствует компоненте x_i<0. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи.

Просматриваем i-ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет x_ij<0, тогда линейная функция двойственной задачи не ограничена на многограннике решений. Поэтому нет решений исходной задачи.

В противном случае для столбцов, имеющих отрицательные значения, определяем q_0j=min(x_i/x_ij)>0. Также находим вектор, который соответствует minq_0j(Z_j–C_j) при решении исходной задачи на максимум, а также maxq_0j(Z_j–C_j) при значении исходной задачи на минимум.

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

Допустим, что q_0j=min(x_i/x_ij)=0, т.е. x_i=0, тогда x_ij выбирается как разрешающий элемент, но лишь тогда, когда x_ij>0.

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

Определяя оптимальный план двойственной задачи, находим и оптимальный план исходной задачи.

Используя при решении, алгоритм двойственного симплексного метода условие Z_j–C_j>0 допускается не учитывать, пока не будут исключены все х_i<0.

Обычным симплексным методом определяется оптимальный план. Этот метод обычно используется при условии, что все х_i<0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q_0j=max(x_i/x_ij)>0.

Задачи линейного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положительном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений.

 

 

Разработка программы

 

Постановка задачи

 

Необходимо спланировать работу швейной мастерской на некоторый период. Установлен перечень выпускаемой продукции, известна рыночная цена каждого продукта. Для производства продукции используются ресурсы: материал, нитки, пуговицы, труд закройщиков, швей-мотористок и т.д. Установлен полный перечень этих ресурсов и общее количество каждого ресурса, которое может быть израсходовано в плановом периоде. Известен расход каждого ресурса на единицу каждого продукта. Необходимо определить, сколько каждой продукции нужно производить, чтобы суммарная рыночная цена всей продукции (выпуск, выручка) была наибольшей.

Введем следующие обозначения:

i =1,…, m - номера (индексы) используемых ресурсов;

 - запас i -го ресурса, т.е. допустимый расход i -го ресурса в плановом периоде; другое название - ограничение по ресурсу i;

j =1,…, n - номера (индексы) продуктов;

 - рыночная цена j -го продукта;

- расход i -го ресурса на производство единицы j -го продукта;

 - плановый объем производства j -го продукта, величина неизвестная, ее нужно найти в процессе решения задачи. Исходные данные задачи запишем в виде матрицы.

 

 

 

Рис. 2

 

Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b ₁,…, b_i,…, b_m); внизу каждого столбца - цена продуктов (с₁,…, с _j,…, с _m).

В каждой клеточке матрицы записаны так называемые технологические коэффициенты a _ij, показывающие расход i -го ресурса на производство единицы j -го продукта.

Запишем конкретный числовой пример

 

Рис. 3