|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Двойственная задача линейного программированияВ П.2 мы рассматривали общую задачу линейного программирования. Рассмотрим теперь другую экономическую задачу на том же предприятии с теми же исходными данными. Необходимо определить такие цены (y1 ³ 0, y2 ³ 0,…, ym ³ 0 ) (П.6) всех ресурсов, чтобы сумма потраченных средств на их приобретение была бы минимальна, т.е. Z = b1 y1 + b2 y2 +…+ bm ymà min. (П.7) С другой стороны, предприятию будет выгодно продать ресурсы в случае, если выручка от их продажи будет не менее той суммы, которую предприятие может получить при изготовлении продукции из этих ресурсов. Т.к., на производство единицы продукции j расходуется a1j единиц ресурса 1, a2j единиц ресурса 2,…, amj единиц ресурса m, то для обеспечения выгодности продажи ресурсов необходимо выполнение следующих неравенств:
a12 y1 + a22 y2 +…+ am2 ym ³ с2, …………………………………. (П.8) a1n y1 + a2n y2 +…+ amn ym ³ сn, Полученная экономико-математическая модель называется двойственной или сопряженной по отношению к исходной. Цены ресурсов y1, y2,…, ym получили различные названия: учетные, неявные, теневые. В отличие от «внешних» цен с1, с2 ,…, сn на продукцию, известных, как правило, до начала производства, цены ресурсов y1, y2,…, ym являются внутренними, ибо они определяются непосредственно в результате решения задачи, поэтому их чаще называют объективно обусловленными оценками ресурсов (Л.В.Канторович). Построим двойственную задачу для примера П.1: Z = 12 y1 + 18 y2 +15 y3 à min. (П.9)
y1 + 3 y2 + 3 y3 ³ 6, (П.10) y1 ³ 0, y2 ³ 0, y3 ³ 0. Из алгебраических соображений легко показать, что F £ Z, откуда maxF=minZ, если они существуют (основная теорема двойственности). В нашем примере 2.1 maxF = minZ = 40.5, и объективно обусловленные оценки y1= 0.75, y2 = 1.75, y3 = 0, вычисленные простым счетом в П.5, являются решением двойственной задачи (П.9)-(П.10). Действительно, 12´0.75 + 18´1.75 + 15´0 = 40.5. Из выражения (П.9) видно, что если увеличить в условии задачи какое-либо ресурсное ограничение bi на единицу, то Z (и следовательно F) также увеличится ровно на yi. Однако прямая и двойственная ей задача линейного программирования имеют и экономическое истолкование. Так, в задачах на распределение ограниченных ресурсов в производстве оптимальный план можно получить, либо минимизируя издержки для заданной программы, либо максимизируя выпуск при заданной общей сумме издержек. Двойственными аспектами одной и той же задачи являются распределение ресурсов и оценка их. Если для ресурсов не существует рыночных цен, то необходимо их создать, ввести систему условных или расчетных цен. Рассмотрим теперь пример П.2 и построим для него двойственную задачу. Напомним, что в этом примере из сена и концентратов необходимо составить суточный рацион питания, калорийность которого 20 кормовых единиц, содержание белка 2000 гр., а кальция 100 грамм. Цена сена 1.5, а концентратов 2.5 усл.единиц за 1 кг. Пусть y1, y2, y3 - наша оценка (за единицу) полезности каждого из этих показателей. Тогда общая (условная) оценка рациона питания: Z = 20 y1 + 2000 y2 +100 y3. Мы будем стремиться максимизировать Z. Если 1 кг. сена содержит 0.5 кормовых единиц, 50г белка и 10 г кальция, то оценка его питательного содержания, т.е. 0.5 y1 + 50 y2 + 10 y3 , не может превышать его рыночной цены (1.5). Аналогично этому для концентратов оценка питательных веществ, равная y1 + 200y2 + 2y3, не может превышать 2.5. Следовательно, двойственную задачу можно сформулировать таким образом: Найти такие оценки питательных веществ, чтобы Z = 20 y1 + 2000 y2 +100 y3 à mах (П.11) при условии
y1 + 200 y2 + 2 y3 £ 2.5, (П.12) y1 ³ 0, y2 ³ 0, y3 ³ 0. Мы получили двойственную задачу к примеру П.2, в котором требовалось найти минимальную стоимость входящих в рацион продуктов питания при заданных рыночных ценах на эти продукты и при соблюдении ограничений в отношении потребности в питательных веществах. После введения условных оценок показателей питательности возникает двойственная задача (П.11)–(П.12), где требуется максимизировать условную оценку рациона питания при соблюдении ограничений, согласно которым расходы в расчете за единицу продукта не могут превышать его заданной рыночной цены. Цель первой, прямой задачи заключается в том, чтобы закупаемые продукты были, возможно, более дешевыми, удовлетворяя вместе с тем требованиям в отношении питательной ценности, а цель сопряженной двойственной задачи – в том, чтобы при заданных рыночных ценах на продукты получить рацион наиболее высокопитательный. Имея краткую запись общей задачи линейного программирования в виде: F = при ограничениях:
xj ³ 0 (j=1,2,…n). можно так же кратко записать двойственную к ней задачу: m Z =å biyi à min i=1 при ограничениях: m å aijyi ³ cj (j=1,2,…, n), i=1 yi ³ 0 (i=1,2,…, m). ПримерП.3.Дана исходная задача: максимизировать линейную функцию F = 2×х1 + 3×х2 ® max при ограничениях x1 + 3×x2 £ 18, 2×x1 + x2 £ 16, x2 £ 5, 3×x1 £ 21, x1 ³ 0, x2 ³ 0. Требуется составить задачу, двойственную к исходной задаче. Решение. Сформулируем двойственную задачу: Z = 18× y1 + 16×y2 + 5× y3 + 21× y4 ® min при ограничениях y1 + 2×y2 + 3×y4 ³ 2, 3×y1 + y2 + y3 ³ 3,
|
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.) |