Прямая и двойственная задачи - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Прямая и двойственная задачи - страница №1/1

メ褌à 4. ト粽鴦褊燾å 鈞萵 è淲鳫魲î ð魲ì頏魵瑙

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


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

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

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

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

В качестве примера рассмотрим задачу планирования производства.

Задача: Предприятие № 1 имеет m видов ресурсов в количестве bi (i=) единиц каждого вида ресурсов, из которых производится n – видов продукции. Для производства единицы j-ого вида продукции используется aij-единиц i-того вида ресурсов, а стоимость единицы продукции cj. Необходимо составить план выпуска продукции (указать, сколько и какого типа надо произвести) обеспечивающей ее максимальную стоимость.

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





и обеспечивающей максимум целевой функции .

Допустим, что предприятие № 2 решило закупить все ресурсы, которыми располагает предприятие № 1. В этом случае предприятию № 2 необходимо установить оптимальные цены на эти ресурсы.

Поставим каждому ограничению исходной задачи в соответствие двойственную переменную как вектор оценок видов сырья, где yi - оценка стоимости единицы i-того ресурса.

Оценка ресурсов исходит из следующих условий:



  • Общая стоимость ресурсов (общие затраты) для предприятия № 2 должна быть минимальной: ;

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

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

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



Замечание. Стоимостное выражение ресурса не есть его цена, т.е. – это неявные или учетные цены.

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



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

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

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

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

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

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


  1. Прямая задачаДвойственная задача







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

Несимметричные двойственные задачи имеют вид:


  1. Прямая задачаДвойственная задача







Введем обозначения:



  • – матрица коэффициентов системы ограничений;

  • – матрица-строка коэффициентов целевой функции;

  • – матрица-столбец свободных членов;

  • – матрица-столбец неизвестных.

Тогда схема составления двойственных задач имеет вид:

Схема составления двойственных задач

Прямая задачаДвойственная задача



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

  1. Если целевая функция задачи исследуется на max, то ограничения должны иметь знак «» или «=», а если целевая функция задачи исследуется на min, то ограничения должны иметь знак «» или «=».

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

  3. Если целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи исследуется на min, и наоборот: .

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

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

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

  7. Если на переменную прямой задачи наложено ограничение на знак (), то j-е ограничение двойственной задачи записывается в виде неравенства, и наоборот.

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

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

  10. Если на переменную двойственной задачи наложено условие неотрицательности , то в прямой задаче соответствующее ограничение двойственной задачи записывается в виде неравенства.

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



Решение.

  1. Упорядочим запись задачи. Для этого первое ограничение умножим на (-1):



  1. Каждому ограничению исходной задачи поставим в соответствие двойственную переменную

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



  1. Так как целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи будет исследоваться на min:



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



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

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



  1. Так как все три переменные исходной задачи принимают только лишь неотрицательные значения, то в системе ограничений двойственной задачи должны быть три неравенства. Вид неравенства выбирается по целевой функции. Поскольку F исследуется на min, то неравенства должны быть со знаком «». Следовательно, система ограничений примет следующий вид:



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

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

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




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


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


Прямая задачаДвойственная задача



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



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

или .

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

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



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



Следствие 1. Для разрешимости одной из задач двойственной пары необходимо и достаточно, чтобы множество допустимых планов каждой из двойственных задач было не пусто.

Следствие 2. Если целевая функция одной из задач двойственной пары не ограничена, то другая задача двойственной пары не имеет планов.

Следствие 3. Для оптимальности планов и пары двойственных задач необходимо и достаточно выполнение равенства .

Следствие 4. Если в одной из двойственных задач нарушается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное.

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

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


Теорема (Вторая теорема двойственности):

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







Экономически первое условие означает, что если оценка i-того вида ресурса положительна в оптимальном плане , то в оптимальном плане этот ресурс используется полностью . Если же в оптимальном плане этот ресурс используется не полностью , то оценка в оптимальном плане равна нулю .

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

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


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

При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) план имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто.



Задача. Составить к следующей задаче ЛП двойственную и найти решение обеих задач:



Решение. Двойственной задачей по отношению к исходной является следующая задача:

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



Рис. 1. Рис. 2.

Из рис. 1 видно, что при всяком плане исходной задачи значение целевой функции не больше 46. Одновременно, как видно из рис. 2, значение целевой функции двойственной задачи при любом ее плане не меньше 46.

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

Как видно из рис. 1, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, является оптимальным планом, при котором .

Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 2). Значит, является оптимальным планом двойственной задачи, при котором .

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

Нахождение решения двойственных задач


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

,

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

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

,

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

Подставим оптимальный план в выражение

.

Тогда


,

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

Тогда оптимальный план двойственной задачи равен

.

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

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



Соответствие между переменными прямой и двойственной задач
в симплекс-таблице

переменные прямой задачи



основные

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

дополнительные

основные

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

Экономическая интерпретация двойственных оценок


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

Свойства двойственных оценок:

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

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

Экономическую интерпретацию двойственных оценок рассмотрим на примере.

Пример. Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в табл. 1.

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


Вид сырьяНормы затрат сырья (кг) на единицу продукции

АВС

I421

II313

III125

Цена единицы продукции (руб.)101412

Решение. Предположим, что производится x1 изделий А, х2 изделий В и х3 изделий С. Для определения оптимального плана производства нужно решить следующую задачу

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



Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше цены единицы продукции данного вида, т.е. y1, y2 и у3 должны удовлетворять следующей системе неравенств:



Как видно, задачи образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий А, В и С, а решение двойственной — оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой-либо одной из них. Так как система ограничений исходной задачи содержит лишь неравенства вида «≤», то лучше сначала найти решение этой задачи. оптимальное решение приведено в симплексной таблице.


БСБB101412000a1a2a3a4a5a6a2148219/8105/80-1/8a508023/8001/81-5/8a31216-3/401-ј0ј 134057/40023/405/4y1*у2*y3*Из этой таблицы видно, что оптимальным планом производства изделий является такой план, при котором изготовляется 82 изделия В и 16 изделий С, при этом остается неиспользованным 80кг сырья II вида, а максимальную прибыль равна руб., т.е. . Из таблицы также видно, что оптимальным решением двойственной задачи является .

Переменные y1* и y2* обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье I и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

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

Так, увеличение количества сырья 1 вида на 1кг приведет к тому, что появится возможность найти новый оптимальный план производства, при котором общая стоимость произведенной продукции возрастет на 5,75 руб. и станет равной 1340+5,75 = 1345,75 руб. При этом числа, стоящие в столбце вектора a4 оптимальной таблицы, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида увеличится на 1/8 кг.

Точно так же увеличение на 1кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий B на 1/8 ед., причем объем используемого сырья II вида уменьшится на 5/8 кг.

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



.

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

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

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

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

Анализ устойчивости двойственных оценок


Теорема: В оптимальном плане двойственной задачи значение переменной численно равно частной производной оптимального значения целевой функции, (берется производная целевой функции и подставляются значения оптимального плана), как функции от объема ресурсов по данному аргументу, т.е.

Это равенство означает, что изменение значений bi приводит к изменению значения Zmax, причем , , тогда .

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

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



, где

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

- величина изменения i-го ресурса;

- величина уменьшения i-го ресурса;

- величина увеличения i-го ресурса;

- компоненты оптимального плана.

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



Пример.

Оптимальное решение записано в последней симплексной таблице:


БазисСbb101412000A1A2A3A4A5A6A1148219/8105/80-1/8A208023/8001/81-5/8A51216-3/401-ј0ј 134057/40023/405/4y1*у2*y3*

и .

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

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

:

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

:

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



:

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

Предположим, что произошло изменение ресурсов:

, , .

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



.

Тогда максимальная прибыль при новых объемах производства будет равна



руб.

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



Так как двойственные оценки y1* и y3* положительны, то сырье первого и третьего видов использовано полностью, поэтому можно перейти от неравенств к равенствам:



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


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


Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой в системе уравнений, имеется m единичных векторов. Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, когда прямой симплекс-метод не может быть использован, т.е. когда свободные члены системы уравнений могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными), а система ограничений задана неравенствами вида « »,« », «=». Определенная таким образом задача называется задачей в двойственной базисной форме.

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

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

,

где – матрица-столбец свободных членов; где среди чисел имеются отрицательные.



, ,…, – вектора условий функции при соответствующих переменных (столбцы), среди которых есть единичные,

– матрица-столбец неизвестных,

0 – нулевая матрица-столбец той же размерности, что и Х.

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

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

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

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

Алгоритм решения задачи двойственным симплекс-методом.



1. Составление псевдоплана.

Систему ограничений исходной задачи требуется привести к системе неравенств вида « ». Для этого обе части неравенства вида « » необходимо умножить на (-1). Затем от системы неравенств вида « » переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. На основе исходных данных составляют симплекс-таблицу), в которой некоторые элементы столбца вектора В отрицательные числа, и получаем первый опорный план.



2. Проверка плана на оптимальность.

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



3. Выбор направляющих строки и столбца.

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

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

Число, стоящее на пересечении направляющей строки и направляющего столбца называется направляющим элементом.



4. Нахождение нового опорного плана.

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

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

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



Задача. Найти максимальное значение функции при условиях



Решение. Систему ограничений исходной задачи требуется привести к системе неравенств вида « ». Для этого обе части второго и третьего неравенств вида « » необходимо умножить на (-1).

Запишем исходную задачу линейного программирования в канонической форме:



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

БазисСbbс1=1с2=1с3=2с4=0с5=0A1A2A3A4A5a32811100a40-4-11010a50-6-1-2001 1611000

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

Из этой таблицы видим, что псевдопланом исходной задачи является . При этом плане значение целевой функции . Так как в столбце вектора В имеются два отрицательных числа (–4 и –6), а в индексной строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. В данном случае это можно сделать, так как в строках векторов а4 и а5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима.

Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора В. В данном случае это число –6. Следовательно, из базиса исключаем вектор а5. Чтобы определить, какой вектор необходимо ввести в базис, находим , где . В нашем случае: .

Значит, в базис будем вводить вектор а2, при этом направляющим элементом является число –2. Переходим к новой симплекс–таблице.

БазисСbBс1=1с2=1с3=2с4=0с5=0а1а2а3а4а5а3251/20101/2а40–7–3/20011/2а2131/2100–1/2 131/20001/2Из этой таблицы видно, что получен новый псевдоплан . При этом плане значение целевой функции .

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

Так как в столбце вектора В стоит одно отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное – 3/2, следовательно, направляющей вектор - строкой является a4. Направляющим элементом в этой таблице является число – 3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице.


БазисСbBС1=1С2=1С3=2С4=0С5=0а1а2а3а4а5а328/90011/32/3а1114/3100-2/3-1/3а212/30101/3-1/3 32/30001/32/3

Видно, что найден оптимальный план исходной задачи. Ими является вектор . При этом плане значение целевой функции .


Индивидуальные задания


Задача 1. Предприятие производит продукцию двух видов А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида а1, а2 и а3 кг соответственно, а для изготовления единицы изделия В - в1, в2 и в3 кг. Производство обеспечено сырьем каждого вида в количестве р1, р2 и р3 кг соответственно. От реализации единицы готовой продукции вида А предприятие имеет прибыль в размере c1 рублей, а от единицы продукции вида Вс2 рублей. Требуется:

  1. Построить экономико-математическую модель задачи

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

  3. Дать геометрическую интерпретацию полученного решения.

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

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

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

Примечание. Величину Δр1, Δр2, Δр3 можно взять любою в пределах интервала устойчивости.


  1. № задачиа11а21а31а12а22а32b1b2b3с1с292461124146124146392461123455103456368131251191891878324258661429040649395111292142242931229959398247224240256287152578744848051243526135372620310288757812185019982109355121862448286908285392461122383463866358235728414815685105412791481981604712102416183420516818572111292142233824023059137896111441961323681215221472482563627515467911719118352431258136185324112615841244445642453854214615412437512186244412104124537982561441641743731110144154151826199851218624451261061253104265262618632667435810123223493785666839846845241927512186244912708822532942101524830936242

Задача 2. Для следующих задач линейного программирования

  1. составить двойственные им задачи;

  2. найти оптимальные решения для обеих задач.

Решить задачу с использованием двойственного симплексного метода



Контрольные вопросы


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

  2. Сформулируйте задачу о диете и составьте ее математическую модель.

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

  4. Что такое допустимое решение задачи линейного программирования?

  5. Что такое оптимальное решение задачи линейного программирования?

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

  7. Как целевая функция выражается через свободные неизвестные?

  8. Что такое оценочный коэффициент Δj?

  9. Каковы условия оптимальности данного допустимого решения?

  10. В чем состоит условие неразрешимости задачи линейного программирования из-за неограниченности целевой функции на множестве допустимых решений?

  11. Какими методами можно решить задачу линейного программирования?

  12. Какие переменные называются базисными?

  13. Какие переменные называются свободными?

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

  15. Чем отличается решение задачи о минимуме функции от стандартной задачи линейного программирования?

  16. В чем суть симплексного метода?

  17. Каковы критерии симплексного метода?

  18. В чем состоит правило выбора разрешающего элемента при переходе в симплексном методе от одного базисного решения к другому?

  19. Как составляется первая симплексная таблица?

  20. Какими методами определяется опорный план при решении симплексным методом?