Двойственность в линейном программировании

Исходная задача. Найти  матрицу-столбец Х=(x₁, x₂,…, x_n), которая удовлетворяет системе ограничений

 

(1.12). АХ>А₀, Х>0 и минимизирует линейную функцию Z=СХ

 

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

Используя симметричность, можно выбрать задачу, более удобную  для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.

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

 

1.3 Виды математических моделей двойственных задач

 

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

• Симметричные задачи

(1) Исходная задача Двойственная задача

Z_min=CX; f_max =Y>A₀;

AX=A₀; YA=С

X>0 Y>0

(2) Исходная задача Двойственная задача

Z_max =CX; f_min =YA_0;

AX=A₀; YA=С

X>0 Y>0

• Несимметричные задачи

(3) Исходная задача Двойственная задача

Z_min=CX; f_max=YA₀;

AX=A₀; YA=С

X>0

(4) Исходная задача Двойственная задача

Z_max=CX; f_min=YA₀;

AX=A₀; YA=С

X>0

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

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

 

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

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

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.

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

 

 

 

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

 

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

 

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

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

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

 

2.2 Построение математической модели

 

Теперь приступим к  созданию математической модели, т.е. к математической записи задачи.

Целевая функция:

Ограничения:

x₁ ³ 0;

x₂ ³ 0;

x₃ ³ 0.

 

2.3 Описание решения данной задачи

 

Решим поставленную выше задачу с применением EXCEL.

 

 

Содержание ячеек:

B1:D1 – имена продуктов (технологических способов);

A2:A4 – имена ресурсов;

B2:D4 – технологические коэффициенты (расход ресурсов при единичных интенсивностях технологических способов);

B6:D6 – цены продуктов;

B8:D8 – переменные;

F2:F4 – запас ресурсов;

G2:G4 – плановые расходы ресурсов, получаются в результате решения;

G6 – значение целевой функции, получается в результате решения.

Формулы для вычислений:

G2=СУММПРОИЗВ (B$8:D$8; B2:D2);

G3:G4 – копируются из G2;

G6=СУММПРОИЗВ (B8:D8; B6:D6).

Запишем формулы в  ячейки G2:G4. Установить курсор на G2. На панели инструментов выбрать значок формул (f). Появятся два окна. В окне «категория» выбрать «математические», затем в окне «функция» выбрать «СУММПРОИЗВ». Появится окно «СУММПРОИЗВ». В нем нужно указать, где располагаются операнды. Первый операнд – строка B$8:D$8, второй операнд – стока B2:D2. В ячейки G3:G4 формулу скопировать из G2. Аналогичным образом записать формулу целевой функции в ячейку G6. Теперь нужно указать остальные условия решения задачи. Установить курсор на ячейку целевой функции G6. В главном меню выбрать «сервис», а потом «поиск решения». Появится окно, в котором нужно указать:

1. Целевая ячейка – G6;
2. Включить кнопку «максимальное значение»;
3. Указать изменяемые ячейки (расположение переменных) – B8:D8;
4. Записать ограничения. Их можно записать прямо в этом же окне, но лучше выбрать «добавить» и в появившемся окне «добавить» последовательно записать ограничения:

B8:D8 0 – неотрицательности переменных;

G2:G4 F2:F4 – плановый расход ресурсов меньше их запаса.

Теперь электронная  модель сформирована и можно решать задачу. Для этого нужно вернуться  в окно «поиск решения» и нажать «выполнить». Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL и в трех отчетах: Результаты, Устойчивость, Пределы.

 

Рис. 4.1.4

 

Основные результаты видны в таблице (рис. 4.1.4.). По сравнению с условиями задачи, показанными на рис. 4.1.3., появились данные:

1. Значение целевой  функции в ячейке G6 = 15880;

2. Значения переменных  в ячейках B8:D8: х₁ = 86, х₂ = 0, х₃ = 268; это значит, что 1-й продукт должен производиться в объеме 86 единиц, 2-й – 0, а 3-й – 286.

3. Плановый расход  ресурсов в ячейках G2:G4: расход 1-го ресурса = 271,6, расход 2-го ресурса = 310, расход 3-го ресурса = 2200.

Как видно 1-й ресурс недоиспользован, а 2-й и 3-й израсходованы полностью.

Кроме результатов в электронной таблице EXCEL готовит три отчета: Результаты, Устойчивость, Пределы. Отчет по результатам изображен на рис 4.1.5, где изображены три таблицы.

Отчет по результатам

Целевая ячейка (максимум)

Ячейка   Имя   Исходно  Результат

$G$6    Цены  ЦФ  15880

 

Изменяемые Ячейки

Ячейка Имя Исходно Результат

$B$8 Перем Пр1 0 86

$C$8 Перем Пр2 0 0

$D$8 Перем Пр3 0 268

 

Ограничения

Ячейка Имя Значение Формула Статус Разница

$G$2 Рес 1 Расход 271,6 $G$2 $F$2 не связан 228,4

$G$3 Рес 2 Расход 310 $G$3 $F$3 связанное 0

$G$4 Рес 3 Расход 2200 $G$4 $F$4 связанное 0

$B$8 Перем Пр1 86 $B$8 0 не связан 86

$C$8 Перем Пр2 0 $C$8 0 связанное 0

$D$8 Перем Пр3 268 $D$8 0 не связан 268

Рис. 4.1.5

 

1-я таблица – целевая ячейка – дает значение целевой функции, которая уже имеется в таблице EXCEL, значит, эти данные избыточны.

2-я таблица – изменяемые ячейки – дает значение переменных, которые уже имеются в таблице EXCEL, эти данные тоже избыточны.

3-я таблица – ограничения – дает оценку ограничений. Колонка «значение» дает значения планового расхода ресурсов и переменных – эти данные имеются в таблице EXCEL и здесь избыточны. Столбец «статус» значением «связанное» отмечает ограничения (не больше или не меньше), которые в результате решения превратились в строгие равенства, прочие ограничения имеют статус «несвязанные». Столбец «разница» показывает, на какую величину ограничения отклонились от строгого равенства. Так, например, ограничение 1-го ресурса 500, плановое значение 271,6, разница = 500 – 271,6 = 228,4.