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

1. Двойственные задачи линейного программирования

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

Рассмотрим стандартную задачу ЛП с n переменными и m ограничениями в форме неравенств

f(x) = c1 x1 + c2 x2 + …+ cn xnmax,11 x1 + a12 x2 + … + a1n xn b1,21 x1 + a22 x2 + … + a2n xn b2,

…………………………………….……m1 x1 + am2 x2 + … + amn xn bm,j 0, j = 1, 2, …, n.

Двойственной к ней называется задача ЛП следующего вида:

g(y) = b1 y1+ b2 y2 + …+ bm ym??min11 y1 + a21 y2 + … + am1 ym c112 y1 + a22 y2 + … + am2 ym c2

………………………….………………1n y1 + a2n y2 + … + amn ym cn

yi 0, i = 1, 2, …, m.

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

видим, что Адв = АTпр.

Следовательно, пара двойственных задач может быть записана в матричной форме:

< c, x > max; Ax ?b, x ?0.g(y) = < b, y > min; ATy ?с, y ?0.

2. Симметричная пара двойственных задач

Пара двойственных задач, в которых прямая задача - стандартная, называется симметричной парой двойственных задач.

Правила построения двойственной задачи к стандартной задаче ЛП.

·Число переменных двойственной задачи равно числу основных ограничений прямой задачи и наоборот.

·Если прямая задача есть задача на max при ограничениях «», то двойственная задача - задача на min при ограничениях «».

·Правые части ограничений прямой задачи - числа bi - становятся коэффициентами целевой функции двойственной задачи.

·Коэффициенты целевой функции прямой задачи - числа cj - становятся правыми частями ограничений двойственной задачи ЛП.

·j - й столбец матрицы условий прямой задачи превращается в j - ю строку матрицы условий двойственной задачи.

·Переменные прямой и двойственной задачи неотрицательны.

Пример. Рассмотрим стандартную задачу ЛП с двумя переменными, тремя ограничениями в форме неравенств и условиями неотрицательности.

f(x)=2x1-4x2max;1+ 3x2 8,

3x1+ x2 -7,

2x1 - 5x2 10,

x1, x2 0.

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

g(y)=8 y1-7y2+10 y3 min;1 - 3 y2+ 2 y3 2,

3y1+ y2 -5 y3 -4,1, y2 0.

Покажем, что двойственная к двойственной задаче ЛП совпадает с прямой задачей ЛП, для чего воспользуемся предыдущим примером.

Сначала приведем двойственную задачу к стандартному виду

g(y)= -8y1+7y2-10y3 max;1+ 3y2 - 2y3 -2,

3y1 - y2+ 5y3 4,1, y2 0.

Построим к ней двойственную задачу по правилам 1-6, обозначая двойственные переменные через x1, x2.

f(x)= - 2x1+ 4 x2 min;

x1 - 3x2 -8,

x1 - x2 7,

2x1+ 5x2 -10,

x1, x2 0.

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

Из вышесказанного следует, что если прямая задача имеет вид:

f(x) = < c, x > min; b, x 0,

то двойственной к ней будет задача

g(y) = < b, y > max;Ty с, y 0.

3. Экономический смысл двойственной задачи

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

Предприятие после выпуска основной продукции имеет излишки ресурсов двух типов: R1 - 10 единиц, R2 - 8 единиц. Существует два способа распорядиться этими ресурсами:

·организовать из них выпуск 3 новых видов продукции: P1, P2, P3.

·продать их.

Рассмотрим оба способа.

Исходные данные приведены в таблице:

РесурсыРасход ресурса на единицу продукцииЗапас ресурсовP1P2P3R112110R22138Удельная прибыль$6$4$4

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

Пусть xj - план выпуска продукции Pj.

Тогда целевая функция будет выглядеть следующим образом:

f(x)=6x1+4x2+4x3 max;

Ограничения по ресурсам:

1+2x2+x3 10,

x1+x2+3x3 8,j 0, j=1,2,3.

Получили стандартную задачу ЛП.

Рассмотрим второй способ использования ресурсов, а именно, их продажу.

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

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

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

Пусть y1 - цена одной единицы ресурса R1, y2 - цена одной единицы ресурса R2.

Интерес покупателя будет выражаться целевой функцией, равной суммарной стоимости приобретаемых ресурсов

g(y) = 10 y1+ 8 y2 min.

Интерес продавца будет описываться ограничениями:

y1+2y2 6,

y1+y2 4,

y1+3y2 4,

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

Присоединяя естественные условия неотрицательности цен:

y1, y2, y3 0,

получаем двойственную задачу ЛП.

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

Прямая задача Определить такой план выпуска продукции x =(x1, x2,…, xn), используя ограниченные запасы ресурсов, при котором прибыль от реализации продукции будет максимальной.Двойственная задача Установить такой набор цен ресурсов y =(y1, y2,…, ym), при которых стоимость ресурсов, затраченных на выпуск единицы продукции будет не ниже прибыли от ее реализации, но при этом суммарная стоимость затрат будет минимальна.

Цены ресурсов y1, y2,…, ym носят названия теневых, неявных или внутренних цен. Эти названия отличают их от «внешних», заранее известных цен с1, с2,…, сn на выпускаемую продукцию. Цены y1, y2,…, ym на ресурсы определяются из решения двойственной задачи и характеризуют стоимость затрат на выпуск конкретных видов продукции, поэтому их часто называют двойственными оценками ресурсов.

4. Несимметричная пара двойственных задач

Пусть теперь исходная задача - каноническая, то есть имеет вид:

f(x) = < c, x > max;(4.1)Ax = b,(4.2)x 0.(4.3)

Здесь x = (x1,…, xn), c = (c1,…, cn), b = (b1,…, bm), так что число уравнений в системе (4.2) равно m.

Для построения двойственной задачи к задаче (4.1) - (4.3) сведем ее к стандартной форме.

Каждое равенство в (4.2) заменим парой неравенств

или, что то же самое

Получим стандартную задачу ЛП с 2m ограничениями.

f(x)=< c, x > max;b,

Построим к ней двойственную задачу ЛП по известным правилам.

Для этого введем двойственные переменные:

u = (u1,…, um) 0,

v = (v1,…, vm) 0.

Заметим, что, так как в прямой задаче ЛП было 2m ограничений, то в двойственной будет 2m переменных.

Целевая функция двойственной задачи примет вид:

g (u, v)=< b, u > + < - b, v > min,

а ограничения запишутся так:

ATu - ATv c,

Перепишем эту задачу более компактно:

g (u, v)=< b, u - v> min,T (u - v) c, 0, v 0.

Введем новый вектор двойственных переменных y = (y1, y2,…, ym) с координатами yi = ui - vi. Поскольку разность неотрицательных чисел может быть и отрицательной (например, 2-5= -3), то двойственные переменные yi не имеют ограничений по знаку.

Таким образом, двойственная задача к канонической будет иметь вид:

g(y) = < b, y > min;Ty 0,

Переменная любого знака !

5. Таблицы для построения двойственной задачи

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

Прямая задача линейного программированияДвойственная задача линейного программированияЦелевая функция< c, x > max< b, y > minЦелевая функцияТип i-го ограниченияi biyi 0Знак i-й переменнойi biyi 0i = biyij 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

Прямая задача линейного ПрограммированияДвойственная задача линейного программированияЦелевая функция< c, x > min< b, y > ?maxЦелевая функцияТип i-го ограниченияi biyi ?0Знак i-ой переменнойi biyi 0i = biyi - любого знакаЗнак j-ой переменнойxj 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

Задание . Составить двойственные задачи к следующим задачам ЛП.

1. f(x) = 2x1 - 2x2+ 3x3 - 6x4 max

x1+ x2 - 2x3 + x4 = -101 - 5x2 - x3 + 2x4 = 35j 0, j=1,2,3,4

F(x) = - x1 - 3x2+ x3 min1+ x2+ x3 61 - x2+ x3 8j 0, j=1,2,3

F(x) = 9x1+ 2x2+ 3x3+ 2x4 min

x1+ x2+ 2x3 = 2

x1+ x2 - x3 - 4x4 = -1j 0, j=1,2,3,4

F(x) = x1 - 2x2 max1+ x2 4

x1 - x2 8

x1+ x2 0

x2 0

6. Связь между планами двойственных задач

Рассмотрим симметричную пару двойственных задач:

f(x) = < c, x > max;(4.4)g(y) = < b, y > min;(4.7)Ax b(4.5)ATy c(4.8)x 0(4.6)(y 0(4.9)x = (x1,…, xn)y = (y1,…, ym)

Между решениями этих задач существует тесная связь, отражаемая следующими свойствами и теоремами.

7. Первая теорема двойственности

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

Теорема 1. Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план, причем значения целевых функций на этих планах равны

(x*) = g(x*) или < c, x*> = < b, y*>.

Если же целевая функция одной из пары двойственных задач не ограничена на своём множестве планов (прямая - сверху, двойственная - снизу), то множество планов другой задачи пусто.

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

Утверждение второй части теоремы легко доказывается от противного. Предположим, что в прямой задаче (4.4) - (4.6) целевая функция не ограничена сверху на множестве X, то есть max f(x) ¥ , xÎ X, но множество планов Y двойственной задачи не пусто - существует хотя бы одна точка yÎ Y. Тогда в силу основного неравенства теории двойственности: maxf(x) g(y), что противоречит неограниченности целевой функции прямой задачи. Таким образом, неограниченность сверху целевой функции исходной задачи влечет за собой несовместность ограничений двойственной задачи. Аналогично доказывается, что из неограниченности снизу двойственной целевой функции g(y) на множестве Y, следует пустота множества планов X прямой задачи.

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

Первая теорема двойственности позволяет исследовать любой заданный план на оптимальность.

8. Вторая теорема двойственности

Теорема 2.Планы x* = (x1*,…, xn*) и y* = (y1*,…, ym*) - оптимальны (каждый в своей задаче), тогда и только тогда, когда выполняются условия:

< Ax* - b, y* > = 0,(4.15)

< ATy* - c, x* > = 0,(4.16)

Доказательство.

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

Прямая задача ЛПДвойственная задача ЛПf(x) = < c, x > maxg(y) = < b, y > min(4.17) Ax = bATy cx 0

Необходимость.

Пусть x*, y* - оптимальные планы прямой и двойственной задач соответственно. Покажем, что условия (4.15), (4.16) выполняются.

Заметим, что при x = x* из (4.17) следует (4.15). Так как Ax* - b= 0, значит и скалярное произведение * - b, y* > тоже равно нулю. По первой теореме двойственности для оптимальных планов x*, y* выполняется равенство: < c, x* > = < b, y* >. Подставим сюда выражение для b из (14): b = Ax*. Используя правило перекидки, получим:

< c, x* > = < Ax*, y* >= < x*, ATy* > = < ATy*, x* >,

откуда следует < ATy* - c, x* > = 0. А это не что иное как условие (4.16)

Достаточность.

Пусть для допустимых планов x*, y* справедливо (4.15), (4.16). Докажем их оптимальность.

Условия (4.15) и (4.16) можно записать следующим образом

< Ax*, y* > = < b, y* >, < ATy*, x* > = < c, x* >.

По правилу перекидки < Ax*, y* > = < ATy*, x* >. Так как левые части условий равны, то равны и правые части:

< b, y* > = < c, x* >,

отсюда по свойству 2 заключаем, что x* - оптимальный план прямой задачи,* - оптимальный план двойственной задачи. Что и требовалось доказать.

. Условия равновесия

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

< Ax* - b, y* > = 0,(4.18)

< ATy* - c, x* > = 0. (4.19)

Прямая задача ЛПДвойственная задача ЛП f(x) = c1 x1 + … + cn xn maxg(y) = b1 y1+ …+ bm ym??minai1 x1 + … + ain xn bi, i =1,…, ma1j y1 + … + amj ym cj, j = 1,…, nxj 0, j = 1,…, nyi 0, i = 1,…, m

Раскрывая скалярные произведения, распишем условия (4.18) и (4.19) более подробно.

å (ai1 x1*+ … + ain xn* - bi) yi* = 0,(4.20)

å (a1j y1*+ … + amj ym* - cj) xj* = 0.(4.21)

В сумме (4.20) каждое слагаемое есть произведение разности левой и правой частей ограничения прямой задачи на соответствующую двойственную переменную. Очевидно, что все слагаемые имеют один и тот же знак «0», так как разности в круглых скобках меньше или равны нулю, а yi 0. Отсюда следует, что сумма (4.20) равна нулю тогда и только тогда, когда каждое слагаемое в ней равно нулю.

(ai1 x1*+ … + ain xn* - bi) yi* = 0, i =1,…, m. (4.22)

двойственность неравенство равновесие линейный

В сумме (4.21) каждое слагаемое равно произведению разности левой и правой частей ограничения двойственной задачи на соответствующую переменную прямой задачи. Все слагаемые в этой сумме одного знака (0), так как разности в круглых скобках и переменные xj* неотрицательны. Для того, чтобы сумма равнялась нулю, любое слагаемое в сумме должно быть равно нулю.

(a1j y1*+ … + amj ym* - cj) xj* = 0, j = 1,…, n. (4.23)

Учитывая знаки сомножителей в произведении (4.22), из него можно получить пару условий

Если ai1 x1*+ … + ain xn* < bi, то yi* = 0. (4.22a)

Если yi* > 0, то ai1 x1*+ … + ain xn* = bi. (4.22b)

Аналогично, из (6) следует пара условий

Если a1j y1*+ … + amj ym* > cj, то xj* = 0. (4.23a)

Если xj* > 0, то a1j y1*+ … + amj ym* cj.(4.23b)

Таким образом, для пары двойственных задач

·если какое-либо ограничение одной задачи на оптимальном плане выполняется как строгое неравенство, то соответствующая координата оптимального плана другой задачи равна нулю (условия (4.22a) и (4.23a)).

·Если какая-либо координата оптимального плана одной задачи положительна, то соответствующее ограничение другой задачи обращается в равенство (условия (4.22b) и (4.23b)).

Эти условия называются условиями дополняющей нежесткости или условиями равновесия.

. Геометрический смысл условий равновесия

Определение 1. Ограничение стандартной задачи линейного программирования

ai1 x1 + … + ain xn bi(4.24)

называется связным или активным на плане x", если на этом плане оно обращается в равенство

ai1 x1"+ … + ain xn" bi.

Определение 2 . Ограничение (4.24) называется несвязным (неактивным, пассивным) на плане x", если на этом плане оно выполняется как строгое неравенство

ai1 x1"+ … + ain xn" < bi.

Геометрически, ограничение, активное в точке x", проходит через эту точку, а неактивное - не проходит.

На рисунке в точке x" P1 и P3 - активные, связные ограничения; P2 - неактивное ограничение. В точке x» P1, P2 - активные ограничения; P3 - неактивное ограничение.

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

На оптимальных планах двойственных задач

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

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

Литература

1. Айвазян С.А., Иванова С.С. Эконометрика. Краткий курс: учеб. пособие / С.А. Айвазян, С.С. Иванова. - М.: Маркет ДС, 2007. - 104 с.

Бородич С.А. Вводный курс эконометрики: Учебное пособие. - Мн.: БГУ, 2009. - 354 с.

Бывшев В.А. Эконометрика: учеб. пособие / В.А. Бывшев. - М.: Финансы и статистика, 2008. - 480 с.

Доугерти Кристофер. Введение в эконометрику: Учебник для экон. спец. вузов / Пер. с англ. Е.Н. Лукаш и др. - М.: ИНФРА-М, 2007. - 402 с.

Дубров А.М., Мхитарян В.С., Трошин Л.И. Многомерные статистические методы: Учебник. - М.: Финансы и статистика, 2009. - 352 с.

Дуброва Т.А. Прогнозирование социально-экономических процессов. Статистические методы и модели: учеб. пособие / Т.А. Дуброва. - М.: Маркет ДС, 2007. - 192 с.

Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: Учебник. -3-е изд., перераб. и доп. - М.: Дело, 2008. - 400 с.

Методы математической статистики в обработке экономической информации: учеб. пособие / Т.Т. Цымбаленко, А.Н. Баудаков, О.С. Цымбаленко и др.; под ред. проф. Т.Т. Цымбаленко. - М.: Финансы и статистика; Ставрополь: АРГУС, 2007. - 200 с.

Палий И.А. Прикладная статистика: Учебное пособие. - М.: Издательско-торговая корпорация «Дашков и К», 2008. - 224 с.

Порядина О.В. Эконометрическое моделирование линейных уравнений регрессии: Учебное пособие. - Йошкар-Ола: МарГТУ, 2006. - 92 с.

Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2007. - 344 с.

Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-у изд., испр. - Т. 2: Айвазян С.А. Основы эконометрики. - М.: ЮНИТИ-ДАНА, 2009. - 432 с.

Симчера В.М. Методы многомерного анализа статистических данных: учеб. пособие. - М.: Финансы и статистика, 2008. - 400 с.

Чураков Е.П. Прогнозирование эконометрических временных рядов: учеб. пособие / Е.П. Чураков. - М.: Финансы и статистика, 2008. - 208 с.

Эконометрика: учеб. / под ред. д-ра экон. наук, проф. В.С. Мхитаряна. - М.: Проспект, 2008. - 384 с.

Эконометрика: учеб. / под ред. И.И. Елисеевой. - М.: Проспект, 2009. - 288 с.

Эконометрика: Учебник/И.И. Елисеева, С.В. Курышева, Т.В. Костеева и др., Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2006. - 576 с.

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

Каждой задаче линейного программирования может быть поставлена в соответствие другая вполне определенная задача линейного программирования, такая, что при решении одной из них одновременно решается и другая. Эти задачи были названы парой взаимодвойственных задач.

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

Правила построения двойственной пары

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

1. Основные теоремы двойственности

Примечание. Геометрическая интерпретация двойственных задач.

При решении двойственных задач возможны три случая:

обе задачи разрешимы;

области допустимых решений обеих задач пусты;

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

Пример 2. Для данной задачи составить двойственную, решить ее графическим методом, и, используя теоремы двойственности, найти решение данной задачи.

Решение.

Составим матрицу из коэффициентов при неизвестных, свободных членах и коэффициентах целевой функции (f).

Транспонируем полученную матрицу (т. е. заменяем строки на столбцы).

По транспонированной матрице составляем двойственную систему ограничений и целевую функцию (φ)

;

Функция φ минимизируется, так как целевая функция исходной задачи максимизируется.

Поскольку на переменные исходной задачи наложены условия неотрицательности
, то соотношения (1) – (5) в системе ограничений двойственной задачи являются неравенствами. Переменныеy 1 , y 2 не должны удовлетворять условию неотрицательности, т.к. они соответствуют ограничениям- неравенствам исходной задачи.

Решим полученную задачу графическим методом. На рис. 2 изображены: область допустимых решений задачи,
, линии уровня и оптимальное решение задачи,Y* = (-2; -5) и φ(Y*) = -22.

Рис. 2.

По первой теореме двойственности

Подставим оптимальное решение Y* = (-2; -5) в систему ограничений. Получим ограничения

1, 4, 5 выполняются как строгие неравенства. Согласно второй теореме двойственности соответствующие компоненты оптимального плана двойственной задачи, т.е. исходной задачи, равны нулю:
. Учитывая это, из системы ограничений исходной задачи найдем ее оптимальное решение:

X* = (0; 2; 1; 0; 0).

Ответ:
приX* = (0; 2; 1; 0; 0).

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

5.1 Понятие двойственности 83

5.2 Экономическая интерпретация двойственной задачи 87

5.3 Первая теорема двойственности 88

5.4 Вторая теорема двойственности 90

5.5 Третья теорема двойственности 92

5.6 Пример решения сопряженных задач 96

5.6.1 Задача, двойственная задаче о диете 96

5.6.2 Выполнение основной теоремы двойственности 97

5.6.3 Выполнение теоремы о равновесии 99

5.6.4 Выполнение теоремы об оценке 99

5.7 Вопросы и упражнения 106

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

5.1 Понятие двойственности

Рассмотрим задачи линейного программирования в стандартной форме, записанные в матричной форме:

где С = (с 1 . . . с n), X =, B =, A =

,

где Y= (y 1 . . .y m).

Здесь X, Y - переменные * ; A, B, C - константы.

Задача (21) и любая эквивалентная ей задача линейного программирования называется двойственной задаче (20) и любой эквивалентной ей задаче.

Подчеркнем, что новых переменных вводится ровно столько, сколько в задаче (20) ограничений, т.е. m.

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

Исходную задачу, по отношению к которой строится двойственная, иногда еще называют прямой задачей.

Теорема (о сопряженных задачах). Задача, двойственная двойственной, эквивалентна исходной.

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

Приведем задачу (21) к стандартной форме на максимум:

Транспонируем входящие сюда величины, чтобы порядок действий над векторами и матрицами был таким же, как и в задаче (20):

mах -B Т Y Т

Теперь можно построить двойственную задачу в соответствии со сформулированным определением. Введем строку переменных Z.

Эта задача является двойственной к двойственной. Преобразуем ее.

Эта задача эквивалентна задаче (20) с точностью до обозначения.

Теорема доказана.

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

Рассмотрим задачу в канонической форме. Чтобы построить задачу, двойственную к ней, преобразуем ее к стандартной форме.

Построим теперь двойственную задачу. Отметим, что число ограничений задачи возросло в два раза (каждое уравнение преобразовано в два неравенства). Вектор-строку переменных двойственной задачи разобьем на две части, в каждую из которых будет входить равное число переменных, и обозначим его (U,V) = (u 1 , …,u m ,v 1 , …,v m).

При этом во всех линейных выражениях компоненты вектора В и матрицы А можно вынести за скобки, а в скобках останется разность векторов U = (u 1 , …,u m) и V = (v 1 , …,v m). Например, при перемножении строки переменных на первый столбец матрицы А будет получено: (a 11 u 1 +a 21 u 2 + …+ a m1 u m - a 11 v 1 - a 21 v 2 - … - a m1 v m = a 11 (u 1 - v 1) + a 21 (u 2 – v 2) + … + a m1 (u m – v m); - и т.д.

Обозначим U - V = Y. При этом переменные Y = (u 1 -v 1 ; …;u m –v m) = = (y 1 . . .y m) не ограничены по знаку. Тогда двойственная задача примет вид:

Итак, ограничениям-уравнениям поставлены в соответствие неограниченные по знаку переменные. Поскольку двойственность взаимна, можно сказать, что и неограниченным по знаку переменным следует ставить в соответствие ограничения уравнения, а не неравенства.

На основании проведенных рассуждений можно сделать вывод, что для построения двойственной задачи не обязательно каждый раз приводить задачу линейного программирования к стандартной форме, а именно нет необходимости преобразовывать уравнения к неравенствам, а не ограниченные по знаку переменные - к неотрицательным. Пусть в задаче в смешанной форме первые m` ограничений – уравнения, а остальныеm-m` - неравенства; и первыеn` переменных неотрицательны, а остальныеn-n` переменных по знаку могут быть любыми. Между задачей линейного программирования в смешанной форме и двойственной ей задачей линейного программирования можно установить следующее соответствие:

max c j x j	min b i y i
a ij x j = b i ,	a ij y i c j ,
a ij x j b i ,	a ij y i = c j ,
x j 0,	y i 0,
x j 0,	y i 0,

Сформулируем ряд правил построения двойственной задачи:

а) Переменные двойственной задачи соответствуют ограничениям исходной задачи, а ограничения - переменным.

б) Если исходная задача линейного программирования задана на максимум, то двойственная строится на минимум, и наоборот.

в) В задаче линейного программирования на максимум в ограничениях-неравенствах должен стоять знак , а на минимум -.

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

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

Если обе сопряженные задачи записаны в стандартной форме, их называют симметричными сопряженными задачами .

Например, построим задачу, двойственную к следующей задаче:

min 2х 1 + 3х 2 - 4х 3 + х 5

4х 1 - 3х 2 - х 3 + х 4 + х 5 10

х 1 + 4х 2 + х 3 + х 5 = 15

2х 1 - 4х 2 - х 3 + х 4 3

Так как задача на минимум, умножим обе части первого ограничения на -1, чтобы получить знак неравенства : -4х 1 + 3х 2 + х 3 - х 4 - х 5  -10.

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

Целевая функция двойственной задачи максимизируется, так как прямая задача поставлена на минимум. Коэффициенты целевой функции двойственной задачи представляют собой свободные члены прямой задачи.

Первое ограничение двойственной задачи соответствует переменной х 1 прямой задачи, поэтому коэффициенты этого ограничения берут из столбца коэффициентов при х 1 , а свободный член – из целевой функции прямой задачи. Так как х 1 0, это ограничение – неравенство. Так как двойственная задача на максимум, знак неравенства. Аналогично строятся второе, третье и пятое ограничения. Четвертое ограничение соответствует переменной х 4 , знак которой может быть любым. Поэтому оно – уравнение.

Переменные y 1 иy 3 соответствуют первому и третьему ограничениям прямой задачи, которые представляют собой неравенства. Поэтому эти переменные – неотрицательные. Второе ограничение прямой задачи – уравнение, поэтому переменнаяy 2 не ограничена по знаку.

max -10y 1 + 15y 2 + 3y 3

4y 1 + y 2 + 2y 3  2

3y 1 + 4y 2 - 4y 3  3

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

Прямая задача в исходной форме:

при ограничениях:

.

Чтобы сформулировать условия двойственности задачи, составим следующую схему (рис. 7.1).

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

1) каждому ограничению прямой задачи соответствует переменная двойственной задачи;

2) каждой переменной прямой задачи соответствует ограничение двойственной задачи;

1) коэффициенты при переменной ( -й), фигурирующие в ограничениях прямой задачи, становятся коэффициентами левой части соответствующего ограничения двойственной задачи;

2) коэффициент при переменной в целевой функции прямой задачи, становится постоянной правой части соответствующего ограничения двойственной задачи;

3) постоянная правой части некоторого ограничения прямой задачи, становится соответствующим коэффициентом при переменной в целевой функции двойственной задачи;

4) если прямая задача решается на максимум целевой функции, то двойственная задача решается на минимум, и наоборот. Переменные двойственной задачи не ограничены в знаке;

5) если прямая задача решается на максимум, то ограничения в двойственной задаче имеют вид неравенства , если задача решается на минимум, то смысл неравенства противоположен.

Пример 7.1

Прямая задача:

Стандартная форма прямой задачи:

Двойственная задача:

Из указанных правил следует: двойственная задача имеет переменных ( , , , ) и ограничений (соответствующих переменным прямой задачи , , , ).

Доказано, что для каждой пары двойственных задач справедливы свойства:

1) для любой пары допустимых решений прямой и двойственной задач:

2) На любой итерации процесса решения прямой задачи:

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

, (7.1)

где звездочка (*)означает, что значения переменных берутся из оптимальных решений прямой и двойственной задач;

4) для каждой пары сопряженных условий в оптимальном решении выполняются следующие соотношения: если одно из них выполняется как простое равенство, то другое – как строгое неравенство и наоборот, т.е.

если , то , (7.2)

если , то , (7.3)

если , то , (7.4)

если , то . (7.5)

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

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

2. Если ресурс в оптимальном плане израсходован полностью, то его оценка положительна (см. формулу (7.2)), если же ресурс не полностью израсходован в оптимальном плане, то его оценка равна нулю (см.

формулу (7.3)). В первом случае ресурс является дефицитным, во втором – недефицитным. Для недефицитного ресурса значение соответствующей балансовой переменной покажет его остаток после выполнения оптимального плана. Чем больше оценка ресурса, тем он дефицитнее с точки зрения его вклада в поставленную цель – максимизировать суммарную выручку.

3. В оптимальный план включается производство только тех видов продукции, оценка ресурсов на производство единицы которых совпадает с ценой (см. формулу (7.5)) (такую продукцию будем называть рентабельной) и продукция не выпускается в оптимальном плане, если аналогичная оценка превышает цену (см. формулу (7.4)).

Проиллюстрируем рассмотренные положения на следующем примере.

Пример 7.2

Пусть в производстве 4-х видов продукции используется 4 вида ресурсов. Известны нормы расхода ресурсов на производство единицы продукции, цены ее реализации

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

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

; ; .

Решение. Модель задачи примет вид:

Найти , , и (объемы производства каждого вида продукции), удовлетворяющие ограничениям:

,

при которых функция достигает максимума.

Для решения задачи симплексным методом приведем ее к стандартному виду:

Значения балансовых переменных показывают объемы неизрасходованных ресурсов в соответствующем плане. Последняя симплексная таблица при решении этой задачи имеет вид табл. 7.1.

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

При этом . – это остаток неизрасходованного второго ресурса.

В таблице 7.1 оптимального решения имеется также вся информация о решении двойственной задачи. Как известно, это – оценки балансовых переменных. Выпишем сначала двойственную задачу, а затем и ее решение. , а изменение второго ресурса не приведет к изменению целевой функции. По крайней мере, его увеличение не приведет к увеличению выручки, так как (как мы видим) этот ресурс остался в излишке в оптимальном решении, но если мы его изменим до величины, меньшей 61 , то выручка уменьшится. Проверьте самостоятельно, что, подставив оптимальное решение во второе ограничение исходной задачи, получим, что для выполнения этого плана второго ресурса понадобится как раз 61ед., а 1-й, 3-й и 4-й ресурсы израсходованы полностью.

2. Наиболее дефицитным является 1-й ресурс, так как его оценка наибольшая, недефицитным – 2-й (его оценка равна нулю), в 3-й и 4-й ресурсы по дефицитности равнозначны (их оценки равны).

3. Рентабельными являются 2-я, 3-я и 4-я продукции (эти виды продукции выпускаются), а нерентабельной – 1-я . Подставив в первое ограничение двойствен-

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

что на 0,6 больше цены единицы этой продукции, равной 4 (обратите внимание, что число 0,6 находится в оценочной строке столбца «x 1 » в таблице 7.1).

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

План

1. Постановка и модель двойственной задачи

2. Методы решения

3. Теоремы теории двойственности и ее экономическое содержание

1. Постановка и модель двойственной задачи

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

Напомним, что в основе задачи линейного программирования рассматривается предприятие, имеющее ресурсы b i , где i = 1, 2, …, m . Оно тратит их на изготовление готовой продукции и эту продукцию реализует. При этом ставится цель - получить максимум продукции в стоимостном выражении не перерасходуя ресурсы. Модель задачи выглядит следующим образом: двойственный симплекс линейный программирование

I) Ж = с 1 х 1 + с 2 х 2 + … + с n х n max.

II) a 11 х 1 + а 12 х 2 + … + а 1 n х n ? b 1 ,

a 21 х 1 + а 22 х 2 + … + а 2 n х n ? b 2 ,

………………………………

a m 1 х 1 + а m 2 х 2 + … + а mn х n ? b m .

III) х j ? 0, j = 1, 2, …, n .

Предположим, что некоторое предприятие решило не тратить ресурсы на изготовление продукции, а продать эти ресурсы. Тогда возникает вопрос: по какой цене продавать ресурсы? Цена должна устраивать как продавца, так и покупателя. Интерес покупающей стороны заключается в том, чтобы заплатить за ресурсы как можно меньше, а интерес продающей стороны - в том, чтобы получить за ресурсы не меньше того, что она получила бы за реализованный готовый товар.

Тогда, в так называемой двойственной модели , целевая функция будет описывать интерес покупающей стороны, система ограничений - интерес продающей стороны (необходимо оценить ресурсы, которые пошли бы на изготовление единицы продукции и стоимость этих ресурсов ограничить ценой реализованной единицы продукции). Третье условие (неотрицательность переменных величин) будет выполняться в силу того, что цена единицы ресурса не может быть отрицательной. Введя в качестве цены единицы ресурса величину u i 0 (i = 1, 2, …, m ), ее еще называют оценкой ресурса (или двойственной оценкой), получим следующую модель:

I) F = b 1 u 1 + b 2 u 2 + … + b m u m min.

II) a 11 u 1 + a 21 u 2 + … + a m 1 u m c 1 ,

a 12 u 1 + a 22 u 2 + … + a m 2 u m c 2 ,

………………………………

a 1 n u 1 + a 2 n u 2 + … + a mn u m c n .

III) u i 0, i = 1, 2, …, m .

Сопоставим обе задачи:

Первая - задача на максимум (z max), вторая - на минимум (F min);

В первой система ограничений типа, во второй;

В первой задаче n неизвестных и m ограничений, во второй m неизвестных и n ограничений;

Коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче c j - коэффициенты целевой функции, во второй c j - свободные члены; в первой задаче b i - свободные члены, во второй b i - коэффициенты целевой функции);

Матрицы коэффициентов в первой и второй задаче являются транспонированными относительно друг друга (строки и столбцы поменялись местами).

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

Алгоритм составления двойственной задачи:

1) тип экстремума целевой функции меняется;

2) каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи;

3) свободные члены исходной задачи становятся коэффициентами при переменных в целевой функции двойственной задачи;

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

Рассмотрим конкретный пример построения двойственной модели:

исходная задача:

I) Z = 6x 1 + 4x 2 max.

II) 2x 1 +4 x 2 ? 8,

2x 1 + x 2 ? 6.

III) x 1 ? 0, x 2 ? 0.

двойственная задача:

I) F = 8u 1 + 6u 2 min.

II) 2u 1 + 2u 2 ? 6,

4u 1 + u 2 ? 4.

III) u 1 ? 0, u 2 ? 0.

Следует отметить, что:

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

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

2. Методы решения

Каждая из задач двойственной пары может решаться отдельно. При этом используется как симплексный метод, так и графический (в случае если задача содержит две переменные). Одновременное решение задач реализуется с использованием, так называемой, двойственной симплекс-таблицы.

Подготовленные для записи в симплекс таблицу модели будут выглядеть следующим образом:

исходная задача (введем y i 0):

I) Ж = с 1 х 1 + с 2 х 2 + … + с n х n max.

II) y 1 = -a 11 х 1 - а 12 х 2 - … - а 1 n х n + b 1 ,

y 2 = -a 21 х 1 - а 22 х 2 - … - а 2 n х n + b 2 ,

…………………………………..

y m = -a m 1 х 1 - а m 2 х 2 - … - а mn х n + b m .

III) х j ? 0, j = 1, 2, …, n .

двойственная задача (введем v j 0):

I) F = b 1 u 1 + b 2 u 2 + … + b m u m min.

II) v 1 = a 11 u 1 + a 21 u 2 + … + a m 1 u m - c 1 ,

v 2 = a 12 u 1 + a 22 u 2 + … + a m 2 u m - c 2 ,

……………………………………

v n = a 1 n u 1 + a 2 n u 2 + … + a mn u m - c n .

III) u i 0, i = 1, 2, …, m .

Обе модели записываются в двойственную симплекс-таблицу следующим образом (таблица 4):

Таблица 4 - Двойственная симплексная таблица

					v n
					-x n	Свободные члены
					a 1 n
					a 2 n
u m	y m	a m 1	a m 2		a mn	b m
Свободные члены					-c n

Замечания:

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

Прежде чем составлять модель двойственной задачи, необходимо у исходной модели «выровнять» знаки, т.е. если целевая функция стремится к max , то все знаки в системе ограничений должны быть ? , а если к min , то ? . Система приводится в соответствие путем домножения обеих частей «неподходящего» неравенства на (-1). Например, чтобы записать модель, двойственную к приведенной модели

I) Z = 4x 1 + 2x 2 + 3x 3 min.

II) -4x 1 - 3x 2 +x 3 ? -4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0,

необходимо исходную переписать в виде:

I) Z = 4x 1 + 2x 2 + 3x 3 min.

II) 4x 1 + 3x 2 - x 3 ? 4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0.

Тогда двойственная задача будет выглядеть так:

I) F = 4u 1 +6u 2 max.

II) 4u 1 + 5u 2 ? 4,

3u 1 + u 2 ? 2,

-u 1 + 2u 2 ? 3.

III) u 1 ? 0; u 2 ? 0;

В центр двойственной симплекс-таблицы (таблицы 4) всегда ставится задача на max, вне зависимости от того какова целевая функция исходной задачи.

3. Основные теоремы теории двойственности и ее экономическое содержание

В качестве основной теоремы двойственности выделяют следующую формулировку: если одна из взаимно двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, при этом соответствующие им оптимальные значения целевых функций равны (т.е. max z = min F ).

Кроме этого варианта возможны следующие взаимоисключающие случаи:

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

Обе из рассматриваемых задач имеют пустые допустимые множества (т.е. обе не имеют решения).

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

Для экономических задач часто представляет интерес то, как повлияет на оптимальное решение изменение запасов сырья и изменение прибыли от единицы продукции. В связи с этим посредством двойственных оценок можно выяснить: увеличение объемов какого вида ресурсов наиболее выгодно; на сколько можно увеличить запас сырья для улучшения полученного оптимального значения целевой функции; каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменение оптимального решения; целесообразность включения в план новых изделий.

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

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

Исчисленные в оптимальных оценках суммарные затраты на производства каждого ингредиента не могут быть меньше, чем оценка данного ингредиента в конечном продукте;

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

Абсолютные значения оценок можно трактовать как некоторые расчетные «цены» ресурсов и потребностей, выраженные в тех же единицах, что и критерий, а знак «+» или «-» при этих «ценах» показывает, ведет ли увеличение данного фактора к возрастанию или уменьшению значения критерия;

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

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

Таким образом, двойственные оценки являются важнейшим результатом, вытекающим из теории двойственности, которая широко применяется на практике.

Размещено на Allbest.ru

...

Подобные документы

Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.

курсовая работа , добавлен 31.10.2014


Понятие теории оптимизации экономических задач. Сущность симплекс-метода, двойственности в линейном программировании. Элементы теории игр и принятия решений, решение транспортной задачи. Особенности сетевого планирования и матричное задание графов.

курс лекций , добавлен 14.07.2011


Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

курсовая работа , добавлен 21.03.2012


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

курсовая работа , добавлен 11.02.2011


Оптимальный план прямой задачи графическим, симплекс-методом. План двойственной задачи по первой теореме двойственности. Определение целочисленного решения графическим, методом Гомори. Сравнение значений функций целочисленного и нецелочисленного решений.

задача , добавлен 29.12.2013


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

контрольная работа , добавлен 08.09.2010


Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.

курсовая работа , добавлен 09.12.2008


Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

контрольная работа , добавлен 11.04.2012


Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.

контрольная работа , добавлен 15.01.2009


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