Курсовая работа: Двойственность в линейном программировании
Введение
Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.
Целью курсового проекта является изучить литературу по выбранной теме и научиться применять на практике симплекс – метод для решения прямой и двойственной задачи линейного программирования, а также решить двойственную задачу линейного программирования с помощью программы MS Excel.
Курсовой проект состоит из введения, двух глав и заключения.
В первой главе рассматриваются основные понятия и предложения теории двойственности ЗЛП, виды математических моделей двойственных задач и их экономическая интерпретация.
Во второй главе рассматривается решение двойственной задачи с помощью программы MS Excel.
1. Двойственность в линейном программировании
1.1 Прямые и двойственные задачи линейного программирования
С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Cj минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции xj(j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях Cj (j=1,2,…, n) единицы продукции и размерах имеющихся ресурсов bi(i=1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции:
F=c1x1+c2x2+…cnxn
при
условиях 
Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:
1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.
2. Матрица
составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица
в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками).
3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи.
5. Если переменная xj
исходной задачи может принимать только лишь положительные значения, то j-е
условие в системе двойственной задачи является неравенством вида «>». Если
же переменная xj может принимать как положительные, так и
отрицательные значения, то 1 – соотношение в системе представляет собой
уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и
переменными двойственной задачи. Если i – соотношение в системе исходной
задачи является неравенством, то i-я переменная двойственной задачи 
.
В противном случае переменная уj может принимать как
положительные, так и отрицательные значения.
Двойственные
пары задач обычно подразделяют на симметричные и несимметричные. В симметричной
паре двойственных задач ограничения прямой задачи и соотношения двойственной
задачи являются неравенствами вида «
«. Таким образом, переменные обеих задач могут
принимать только лишь неотрицательные значения.
Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты Cj функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты Bi системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.
Рассмотрим задачу использования ресурсов. У предприятия есть t видов ресурсов в количестве bi (i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится aij ед. t-гo ресурса, ее стоимость составляет Cj ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за xj (j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции
Z=C1x1+C2x2+ … +Cnxn
Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через уi (j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.
1.2 Основы теоремы двойственности
1.2.1. Несимметричные двойственные задачи
Теорема двойственности:
Система ограничений исходной задачи в несимметричных двойственных задачах определяется как равенство. Двойственная же задача задается, как неравенство, причем переменные могут быть и отрицательными. Что бы проще понимать постановку задачи будем интерпретировать ее в матричной форме.
Сформулируем двойственную задачу. Необходимо определить матрицу-строку Y=(y1, y2,…, ym), которая максимизирует линейную функцию f=YA0 и удовлетворяет ограничениям
YA>С (1.1)
Сформулируем исходную задачу. Определить матрицу-столбец X=(x1, x2,…, xn), которая минимизирует линейную функцию Z=СХ и. удовлетворяет ограничениям
AX=A0,Х>0 (1.2)
Как в исходной так и в двойственной задачах А=(aij) – матрица коэффициентов системы ограничений, A0=(b1, b2,…, bm) – матрица-столбец, C=(c1, c2,…, cn) – матрица-строка. Теорема двойственности устанавливает связь между оптимальными планами пары двойственных задач.
Теорема двойственности гласит: если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение minZ =maxf. Если линейная функция одной из задач не ограничена, то другая не имеет решения
Доказательство.
Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис состоит из т первых векторов A1, A2,…, Am.
Будем считать, что D является матрицей, составленной из компонент векторов конечного базиса A1, A2., Am Приведенная выше таблица состоит из коэффициентов разложения векторов A1, A2,…, An исходной системы по векторам базиса. В этой таблице каждому вектору A j соответствует вектор Xj.
Используя соотношения (1.3) и (1.4), получаем:
(1.5) A=D, D-1A=
(1.6) A0 =DX*; D-1A0 =X
(1.7) min Z= C*X*,
(1.8) = C* – C > 0,
где С=(C1, C2,…, Cm), С=(C1, C2,…, Cm, Cm +1,…, Cn), a=(CX1–C1; СХ2 – С2,…, CXn–Cn)=(Z1–С; Z2-C2;…, Zn–Cn) – вектор, компоненты которого неположительны, так как они совпадают с Zj–Cj>0, соответствующими оптимальному плану.
Оптимальный план исходной задачи имеет вид X=D-1А0, поэтому оптимальный план двойственной задачи ищем в виде
(1.9) Y = C*D-1
Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA-С>0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим
YА–С=С*D-1А–С=С-С>0, откуда находим Y*A>С
Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двойственной задачи f(Y)=Y*A0.Учитывая соотношения (1.9), (1.6) и (1.7), имеем
(1.10) f (Y) = Y*A0=C * D-1A0= C*X = minZ(X)
Таким образом, значение линейной функции двойственной задачи от Y численно равно минимальному значению линейной функции исходной задачи
Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) – на любой план X исходной задачи: YAX=YA0=f(Y), YAX>СХ=Z(X), отсюда следует, что для любых планов Х и Y выполняется неравенство
(1.11) f(Y)>Z(X)
Этим же соотношением связаны и экстремальные значения maxf(Y)>minZ(Х). Из последнего неравенства заключаем, что максимальное значение линейной функции достигается только в случае, если maxf(Y)=minZ(X), но это значение f(Y) достигает при плане Y, следовательно, план Y – оптимальный план двойственной задачи.
Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотношение maxf(Y)=minZ(X)
Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следует, что f(Y) – Y. Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.
Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Тогда из (1.11) получаем, что Z(X)+Y. Это выражение также лишено смысла, поэтому исходная задача не имеет решений.
Доказанная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой. Здесь матрица-строка С = (0; 1; 0; –1; – 3, 0), матрица-столбец
1 1 2 0 -1 1 0
A 0 = 2 A = 0 -4 1 2 -1 0
3 0 3 0 0 1 1
1 0 0
2 -4 3
A «’ = 0 1 0
-1 2 0
1 -1 0
0 0 1
Двойственная задача. Найти максимальное значение линейной функции f=y1+2y2+5y3 при ограничениях
y1> 0
2y1 – 4y2 + 3y3 > 1,
y2 > 0,
(-y1) + 2y2 >(-1),
y1 – y2 + y3 = -3, y3 > 0
Оптимальный план исходной задачи X = (0; 1/3; 0; 11/3; 4; 0), при котором получим Zmin= -46/3. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y= C*D-1, где матрица D-1 - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A5, A4, A2; значит,
1 -1 2
D = (A 5, A 4, A 2) = -1 2 -4
1 0 3
Обратная матрица D -1 образована из коэффициентов, стоящих в столбцах A1, A3, A6 четвертой итерации:
2 1 0
D -1 = -1/3 1/3 2/3
-2/3 -1/3 1/3
Из этой же итерации следует С = (–3; –1; 1). Таким образом
2 1 0
Y=С*D-1 =(-3; – 1; 1) -1/3 1/3 2/3
-2/3 1/3 1/3
Y=(-19/3; – 11/3; – 1/3),
т.е. yi =С*Хi, где Хi – коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.
Итак, i-ю двойственную переменную можно получить из значения оценки (m+1) – й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базис, если к ней прибавить соответствующее значение коэффициента линейной функции:
у1 =–19/3+0=–19/3; y2 =-11/3+0=-11/3; у3 =-1/3+0=-1/3
При этом плане maxf=-46/3
1.2.2 Симметричные двойственные задачи
Разновидностью двойственных задач линейного, программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу-столбец Х=(x1, x2,…, xn), которая удовлетворяет системе ограничений
(1.12). АХ>А0, Х>0 и минимизирует линейную функцию Z=СХ
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду. Для этого второе неравенство следует умножить на -1.
1.3 Виды математических моделей двойственных задач
Основываясь на рассмотренных несимметричных и симметричных двойственных задач отметим, что пары двойственных задач математических моделей могут быть представлены следующим образом:
· Симметричные задачи
(1) Исходная задача Двойственная задача
Zmin=CX; fmax =Y>A0;
AX=A0; YA=С
X>0 Y>0
(2) Исходная задача Двойственная задача
Zmax =CX; fmin =YA0;
AX=A0; YA=С
X>0 Y>0
· Несимметричные задачи
(3) Исходная задача Двойственная задача
Zmin=CX; fmax=YA0;
AX=A0; YA=С
X>0
(4) Исходная задача Двойственная задача
Zmax=CX; fmin=YA0;
AX=A0; YA=С
X>0
Поэтому до того, как сформулировать двойственную задачу для данной исходной, необходимо систему ограничений исходной задачи преобразовать должным образом.
1.4 Двойственный симплексный метод
Для получения решения исходной задачи можно перейти к двойственной. А используя оценки ее оптимального плана, можно определить оптимальное решение исходной задачи.
Если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, тогда переход к двойственной задаче не обязателен. Это связано с тем, что в столбцах определена исходная задача, а в строках – двойственная.
bi являются оценками плана двойственной задачи. Сj являются оценками плана исходной задачи.
Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана исходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи.
Такой метод принято называть двойственным симплексным методом.
Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: минимизировать функцию Z=СХ при АХ=A0, Х>0. Значит в двойственной задаче следует максимизировать функцию f=YA0 при YA>С. Пусть определен следующий базис D=(A1, А2,…, Аi,…, Аm), причем в нем хотя бы одна из компонент вектора Х=D-1A0=(x1, x2,…, xi,…, xm) отрицательная. Для всех векторов Aj используется следующее соотношение Zj–Cj >0 (i=1,2,…, n).
Пользуясь теоремой двойственности, Y=СбазD-1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны.
Поэтому, следует исключить из базиса исходной задачи вектор Аi, который соответствует компоненте xi<0. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи.
Просматриваем i-ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет xij<0, тогда линейная функция двойственной задачи не ограничена на многограннике решений. Поэтому нет решений исходной задачи.
В противном случае для столбцов, имеющих отрицательные значения, определяем q0j=min(xi/xij)>0. Также находим вектор, который соответствует minq0j(Zj–Cj) при решении исходной задачи на максимум, а также maxq0j(Zj–Cj) при значении исходной задачи на минимум.
Найденный вектор включаем в базис исходной задачи. Направляющей строкой определяется вектор, который надо убрать из базиса исходной задачи.
Допустим, что q0j=min(xi/xij)=0, т.е. xi=0, тогда xij выбирается как разрешающий элемент, но лишь тогда, когда xij>0.
Данный подход к решению задачи не приводит к росту количества отрицательных компонент вектора X. Пока не будет получено Х>0, процесс не прекращается.
Определяя оптимальный план двойственной задачи, находим и оптимальный план исходной задачи.
Используя при решении, алгоритм двойственного симплексного метода условие Zj–Cj>0 допускается не учитывать, пока не будут исключены все хi<0.
Обычным симплексным методом определяется оптимальный план. Этот метод обычно используется при условии, что все хi<0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q0j=max(xi/xij)>0.
Задачи линейного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положительном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений.
2. Разработка программы
2.1 Постановка задачи
Необходимо спланировать работу швейной мастерской на некоторый период. Установлен перечень выпускаемой продукции, известна рыночная цена каждого продукта. Для производства продукции используются ресурсы: материал, нитки, пуговицы, труд закройщиков, швей-мотористок и т.д. Установлен полный перечень этих ресурсов и общее количество каждого ресурса, которое может быть израсходовано в плановом периоде. Известен расход каждого ресурса на единицу каждого продукта. Необходимо определить, сколько каждой продукции нужно производить, чтобы суммарная рыночная цена всей продукции (выпуск, выручка) была наибольшей.
Введем следующие обозначения:
i=1,…, m - номера (индексы) используемых ресурсов;
- запас i-го ресурса, т.е.
допустимый расход i-го ресурса в плановом периоде; другое название - ограничение по ресурсу i;
j=1,…, n - номера (индексы) продуктов;
- рыночная цена j-го продукта;
- расход i-го ресурса на
производство единицы j-го продукта;
- плановый объем
производства j-го продукта, величина неизвестная, ее нужно найти в процессе
решения задачи. Исходные данные задачи запишем в виде матрицы.
Рис. 2
Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b1,…, bi,…, bm); внизу каждого столбца - цена продуктов (с1,…, сj,…, сm).
В каждой клеточке матрицы записаны так называемые технологические коэффициенты aij, показывающие расход i-го ресурса на производство единицы j-го продукта.
Запишем конкретный числовой пример
Рис. 3
2.2 Построение математической модели
Теперь приступим к созданию математической модели, т.е. к математической записи задачи.
Целевая функция:
Ограничения:
x1 ³ 0;
x2 ³ 0;
x3 ³ 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: х1 = 86, х2 = 0, х3 = 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
|