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

Введение

Поддвойственной задачей понимается вспомогательная задача линейногопрограммирования, формулируемая с помощью определённых правил непосредственноиз условий прямой задачи. Заинтересованность в определении оптимального решенияпрямой задачи путём решения двойственной к ней задачи обусловлена тем, чтовычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкостьвычислений при решении ЗЛП в большей степени зависит от числа ограничений, а неот количества переменных.

Цельюкурсового проекта является изучить литературу по выбранной теме и научитьсяприменять на практике симплекс – метод для решения прямой и двойственной задачилинейного программирования, а также решить двойственную задачу линейногопрограммирования с помощью программы MS Excel.

Курсовойпроект состоит из введения, двух глав и заключения.

В первойглаве рассматриваются основные понятия и предложения теории двойственности ЗЛП,виды математических моделей двойственных задач и их экономическаяинтерпретация.

Во второйглаве рассматривается решение двойственной задачи с помощью программы MS Excel.

 

 

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

1.1Прямые и двойственные задачи линейного программирования

Сэкономической точки зрения двойственную задачу можно интерпретировать так:какова должна быть цена единицы каждого из ресурсов, чтобы при заданныхколичествах ресурсов bi<sub/>и величинах стоимости единицыпродукции Cj<sub/>минимизировать общую стоимость затрат? Аисходную задачу определим следующим, образом: сколько и какой продукции xj(j<sub/>=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<sub/>системы ограничений исходной задачи называются коэффициентамидвойственной задачи. Транспонированная матрица коэффициентов системыограничений исходной задачи является матрицей коэффициентов системы ограниченийдвойственной задачи.

Рассмотримзадачу использования ресурсов. У предприятия есть t видов ресурсов вколичестве bi (i=1, 2,…, m) единиц, из которых выпускается n видовпродукции. На изготовление 1 ед. i-й продукции тратится aij ед. t-гoресурса, ее стоимость составляет Cj<sub/>ед. Необходимоопределить план выпуска продукции, обеспечивающий ее максимальный выпуск встоимостном выражении. Примем за 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<sub/>иудовлетворяет ограничениям

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<sub/>исходной системы по векторам базиса. В этой таблице каждому вектору A j<sub/>соответствует вектор 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), матрица-столбец

11 2 0 -1 1 0

A 0 = 2 A = 0 -4 1 2 -1 0

30 3 0 0 1 1

1 0 0

2-4 3

A «’= 0 1 0

-12 0

1-1 0

00 1

Двойственнаязадача. Найти максимальное значение линейной функции f=y1+2y2+5y3при ограничениях

y1> 0

2y1 – 4y2 + 3y3 > 1,

y2 > 0,

(-y1)<sub/>+ 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<sup/>-матрица, обратная матрице, составленной из компонент векторов, входящих впоследний базис, при котором получен оптимальный план исходной задачи. Впоследний базис входят векторы A5, A4, A2;значит,

1-1 2

D= (A 5, A 4, A 2) = -1 2 -4

10 3

Обратнаяматрица D -1<sup/>образована из коэффициентов, стоящих встолбцах A1, A3, A6<sub/>четвертойитерации:

21 0

D-1 = -1/3 1/3 2/3

-2/3-1/3 1/3

Изэтой же итерации следует С = (–3; –1; 1). Таким образом

21 0

Y=С*D-1=(-3; – 1; 1) -1/3 1/3 2/3

-2/31/3 1/3

Y=(-19/3; –11/3; – 1/3),

т.е.yi =С*Хi, где Хi<sub/>– коэффициентыразложения последней итерации, стоящие в столбцах векторов первоначальногоединичного базиса.

Итак,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>0Y>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<sub/>являютсяоценками плана исходной задачи.

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

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

Допустимнужно определить исходную задачу линейного программирования, которая поставленав общем виде: минимизировать функцию 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<sup/>являетсяпланом двойственной задачи. Этот план не оптимальный. Потому что оценкиоптимального плана двойственной задачи должны быть неотрицательными и выбранныйбазис 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

Ограничения

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

$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.

Отчет поустойчивости изображен на рис. 4.1.6. Он состоит из двух таблиц.

Отчет поустойчивости

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

Ячейка Имя Результат Норир.

Значение градиент

$B$8 Перем Пр1 86 0 $C$8 Перем Пр2 0 -22,8 $D$8 Перем Пр3 268 0

Ограничения

Ячейка Имя Результат. Лагранжа

значение Множитель

$G$2 Рес 1 Расход 271,6 0 $G$3 Рес 2 Расход 310 20 $G$4 Рес 3 Расход 2200 4,4

Рис. 4.1.6

Таблица«изменяемые ячейки» показывает значения переменных, которые уже имеются втаблице EXCEL. Столбец «нормируемый градиент» показывает, как влияет увеличениепеременных на единицу на величину целевой функции. Таблица «ограничения»содержит важную информацию в столбце «Лагранжа множители». Эти величины влитературе имеют различные названия: объективно обусловленные оценки (О.О.О.)по Л. Канторовичу, двойственные оценки по Д. Данцигу, оптимальныецены, теневые цены и другие. В дальнейшем будем называть их наиболеераспространенным именем – двойственные оценки и обозначать – vi, где i – номер ограничения. Вданном примере v1 = 0, v2 = 20,0, v3 = 4,4. Отчет по пределампоказан на рис. 4.1.7.

Отчет попределам

Ячейка Целевое Значение

имя

$G$6 Цены ЦФ 15880 Ячейка Изменяемое Значение имя

Нижний Целевой

предел результат

Нижний Целевой

предел результат

$B$8 Перем Пр1 86 0 10720 86 15880 $C$8 Перем Пр2 0 0 15880 0 15880 $D$8 Перем Пр3 268 0 5160 268 15880

Рис. 4.1.7.

В этом отчетеуже в третий раз дается значение целевой функции 15880, в пятый раз значениепеременных (х1 = 86, х2 = 0, х3= 268). Нижний предел для всех переменных = 0, так, установлены ограничения попеременным. Верхний предел равен соответственно 86, 0 и 268, так устанавливаютограничения по ресурсам. Целевой результат показывает значение целевой функциипри соответствующих значениях переменных. Если х1 = 0, то ЦФ= 10720 и т.д.

Запишем математическую модель рассмотреннойзадачи в общем виде:

 

/>

Пусть:

В-бюджет, т.е. количество денег, которое можноизрасходовать на приобретение ресурсов для производства продукции, а si – рыночная цена i-го ресурса. Тогдаединственное ограничение по ресурсам будет выглядеть следующим образом:

 

/>.

Смысл этого ограничения — нельзя израсходоватьресурсов на сумму больше, чем В.

Здесь: />  — расход i-го ресурса в натуральномвыражении по j-му технологическому способу;

/> — расход i-го ресурса в натуральномвыражении по всем способам;

/> — суммарная цена i-го ресурса, израсходованногопо всем способам;

/> — суммарная цена всехресурсов по всем технологическим способам.

Решим задачуна максимум продукции с ограничением по бюджету. За основу возьмем электроннуюмодель на рис. 4.1.3. и дополним ценами ресурсов si и бюджетом В (рис. 4.1.8)

/>

Рис. 4.1.8

Дополнительныевеличины:

H2:H4 – цены ресурсов(задаются);

I2:I4 – издержки(вычисляются);

I2 = G2*H2;

I3:I4 – копируется из I2;

H6 = 5000 – бюджет(задается);

I6 – издержки всего(вычисляются);

I6 = СУММ (I2:I4).

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

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

I6 /> H6 – совокупные издержкине больше бюджета.

Будетполучено решение

x1 = 0; x2 = 0; x3 = 409,84.

v = 3,08 – двойственнаяоценка ограничения по бюджету – увеличение бюджета на единицу увеличиваетваловой продукт на 3,28.

Еслиограничения по ресурсам в модели имеют смысл и не больше (/>) и не меньше (/>), причем всевеличины (/>)не отрицательные, то в общем случае вывод о существовании или отсутствиидопустимого плана сделать нельзя. Все зависит от конкретных значений величин /> и />. Возможен случай,когда для некоторого k-го ресурса установлено такое ограничение />, что оно не можетбыть выполнено из-за других ограничений. Тогда нет ни одного допустимого плана.

Заключение

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

Результатомработы над курсовым проектом является программа для решения задач линейногопрограммирования с помощью двойственного симплекс-метода.

Список используемой литературы

1.  Кузнецов Ю.Н., Кузубов В.И.,Волощенко А.Б. Математическое программирование. «Наука», 1980 г.

2.  Солодовников А.С., Бабайцев В.А.,Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.

3.  Математическоемоделирование в задачах. Белолипецкий В.М., Шокин Ю.И.

4.  Математическое Белолипецкий В.М.