АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. VI. Общая задача чистого разума
  2. Апофеоз: двойственная роль развития речи
  3. Виды деятельности линейного ИТР (мастера, прораба).
  4. Вопрос 2 Проверка и оценка в задачах со случайными процессами на примере решения задач экозащиты, безопасности и риска.
  5. Вопрос 5. Какие ресурсные ограничения моделей общей задачи линейного программирования должны анализироваться в первую очередь?
  6. Геометрическая интерпретация задачи линейного программирования.
  7. Гидроцилиндры прямолинейного действия
  8. Глава 10 Системный подход к задачам управления. Управленческие решения
  9. ГЛАВА 2.1. ЗАЩИТА ИННОВАЦИЙ КАК ЗАДАЧА УПРАВЛЕНИЯ ИННОВАЦИОННЫМИ ПРОЦЕССАМИ
  10. Глава 4. Математические основы оптимального управления в экономических задачах массового обслуживания
  11. Графический способ решения задачи линейного программирования

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

Необходимо определить такие цены

(y 1 ³ 0, y 2 ³ 0,…, ym ³ 0) (П.6)

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

Z = b 1 y 1 + b 2 y 2 +…+ bm ym à min. (П.7)

С другой стороны, предприятию будет выгодно продать ресурсы в случае, если выручка от их продажи будет не менее той суммы, которую предприятие может получить при изготовлении продукции из этих ресурсов. Т.к., на производство единицы продукции j расходуется a 1 j единиц ресурса 1, a 2 j единиц ресурса 2,…, amj единиц ресурса m, то для обеспечения выгодности продажи ресурсов необходимо выполнение следующих неравенств:

a 11 y 1 + a 21 y 2 +…+ am 1 ym ³ с 1,

a 12 y 1 + a 22 y 2 +…+ am 2 ym ³ с 2,

…………………………………. (П.8)

a 1 n y 1 + a 2 n y 2 +…+ amn ym ³ сn,

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

Цены ресурсов y 1, y 2,…, ym получили различные названия: учетные, неявные, теневые. В отличие от «внешних» цен с 1, с 2,…, сn на продукцию, известных, как правило, до начала производства, цены ресурсов y 1, y 2,…, ym являются внутренними, ибо они определяются непосредственно в результате решения задачи, поэтому их чаще называют объективно обусловленными оценками ресурсов (Л.В.Канторович).

Построим двойственную задачу для примера П.1:

Z = 12 y 1 + 18 y 2 +15 y 3 à min. (П.9)

2 y 1 + 2 y 2 + y 3 ³ 5,

y 1 + 3 y 2 + 3 y 3 ³ 6, (П.10)

y 1 ³ 0, y 2 ³ 0, y 3 ³ 0.

Из алгебраических соображений легко показать, что F £ Z, откуда max F =min Z, если они существуют (основная теорема двойственности).

В нашем примере 2.1 max F = min Z = 40.5, и объективно обусловленные оценки y 1= 0.75, y 2 = 1.75, y 3 = 0, вычисленные простым счетом в П.5, являются решением двойственной задачи (П.9) - (П.10).

Действительно, 12´0.75 + 18´1.75 + 15´0 = 40.5.

Из выражения (П.9) видно, что если увеличить в условии задачи какое-либо ресурсное ограничение b i на единицу, то Z (и следовательно F) также увеличится ровно на yi.

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

Рассмотрим теперь пример П.2 и построим для него двойственную задачу. Напомним, что в этом примере из сена и концентратов необходимо составить суточный рацион питания, калорийность которого 20 кормовых единиц, содержание белка 2000 гр., а кальция 100 грамм. Цена сена 1.5, а концентратов 2.5 усл.единиц за 1 кг. Пусть y 1, y 2, y 3 - наша оценка (за единицу) полезности каждого из этих показателей. Тогда общая (условная) оценка рациона питания:

Z = 20 y 1 + 2000 y 2 +100 y 3.

Мы будем стремиться максимизировать Z. Если 1 кг. сена содержит 0.5 кормовых единиц, 50г белка и 10 г кальция, то оценка его питательного содержания, т.е. 0.5 y 1 + 50 y 2 + 10 y 3, не может превышать его рыночной цены (1.5). Аналогично этому для концентратов оценка питательных веществ, равная y 1 + 200 y 2 + 2 y 3, не может превышать 2.5. Следовательно, двойственную задачу можно сформулировать таким образом:

Найти такие оценки питательных веществ, чтобы

Z = 20 y 1 + 2000 y 2 +100 y 3 à mах (П.11)

при условии

0.5 y 1 + 50 y 2 + 10 y 3 £ 1.5,

y 1 + 200 y 2 + 2 y 3 £ 2.5, (П.12)

y 1 ³ 0, y 2 ³ 0, y 3 ³ 0.

Мы получили двойственную задачу к примеру П.2, в котором требовалось найти минимальную стоимость входящих в рацион продуктов питания при заданных рыночных ценах на эти продукты и при соблюдении ограничений в отношении потребности в питательных веществах. После введения условных оценок показателей питательности возникает двойственная задача (П.11)–(П.12), где требуется максимизировать условную оценку рациона питания при соблюдении ограничений, согласно которым расходы в расчете за единицу продукта не могут превышать его заданной рыночной цены. Цель первой, прямой задачи заключается в том, чтобы закупаемые продукты были, возможно, более дешевыми, удовлетворяя вместе с тем требованиям в отношении питательной ценности, а цель сопряженной двойственной задачи – в том, чтобы при заданных рыночных ценах на продукты получить рацион наиболее высокопитательный.

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

F = à max

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

£ bi (i =1,2,…, m),

xj ³ 0 (j =1,2,… n).

можно так же кратко записать двойственную к ней задачу:

m

Zb i y i à min

i=1

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

m

å aijy i ³ c j (j =1,2,…, n),

i=1

yi ³ 0 (i =1,2,…, m).

Пример П.3.Дана исходная задача:

максимизировать линейную функцию F = 2× х 1 + 3× х 2 ® max

при ограничениях x 1 + 3× x 2 £ 18,

x 1 + x 2 £ 16,

x 2 £ 5,

x 1 £ 21,

x 1 ³ 0, x 2 ³ 0.

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

Решение.

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

Z = 18× y 1 + 16× y 2 + 5× y 3 + 21× y 4 ® min

при ограничениях y 1 + 2× y 2 + 3× y 4 ³ 2,

y 1 + y 2 + y 3 ³ 3,

y i ³ 0, i = 1, 4.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |

Поиск по сайту:



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