Рассмотрим теперь другую экономическую задачу на том же предприятии с теми же исходными данными. Необходимо определить такие цены ( y 1 ≥ 0, y 2 ≥ 0,…, ym ≥ 0 ) (2.2.6) всех ресурсов, чтобы сумма потраченных средств на их приобретение была бы минимальна, т.е. Z = b 1 y 1 + b 2 y 2 +…+ bm
ym ꅘ min. (2.2.7) С другой стороны, предприятию будет выгодно продать ресурсы в случае, если выручка от их продажи будет не менее той суммы,
104 которую предприятие может получить при изготовлении продукции из этих ресурсов. Т.к., на производство единицы продукции 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, …………………………………. (2.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 являются внутренними, ибо они определяются непосредственно в результате решения задачи, поэтому их чаще называют объективно обусловленными оценками ресурсов (Л.В.Канторович). Построим двойственную задачу для примера 2.2.1:
Z = 12 y 1 + 18 y 2 +15 y 3 揘 min. (2.2.9) 2 y 1 + 2 y 2 + y 3 ≥ 5,
y 1 + 3 y 2 + 3 y 3 ≥ 6, (2.2.10)
y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0. Из алгебраических соображений легко показать, что F ≤ Z , откуда max F =min Z , если они существуют (основная теорема двойственности). В нашем примере 2.2.1 max F = min Z = 40.5, и объективно обусловленные оценки y 1= 0.75, y 2 = 1.75, y 3 = 0, вычисленные простым счетом в 2.2.5, являются решением двойственной задачи (2.2.9) - (2.2.10). Действительно, 12×0.75 + 18×1.75 + 15×0 = 40.5. Из выражения (2.2.9) видно, что если увеличить в условии задачи какое-либо ресурсное ограничение b i на единицу, то Z (и следовательно F ) также увеличится ровно на yi . Однако прямая и двойственная ей задача линейного программирования имеют и экономическое истолкование. Так, в задачах на распределение ограниченных ресурсов в производстве оптимальный план можно получить, либо минимизируя издержки для заданной программы, либо максимизируя выпуск при заданной общей сумме издержек. Двойственными аспектами одной и той же задачи являются распределение ресурсов и оценка их. Если для ресурсов не
105 существует рыночных цен, то необходимо их создать, ввести систему условных или расчетных цен. Рассмотрим теперь пример 2.2.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ах (2.2.11) при условии 0.5 y 1 + 50 y 2 + 10 y 3 ≤ 1.5,
y 1 + 200 y 2 + 2 y 3 ≤ 2.5, (2.2.12)
y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0. Мы получили двойственную задачу к примеру 2.2.2, в котором требовалось найти минимальную стоимость входящих в рацион продуктов питания при заданных рыночных ценах на эти продукты и при соблюдении ограничений в отношении потребности в питательных веществах. После введения условных оценок показателей питательности возникает двойственная задача (2.2.11) – (2.2.12), где требуется максимизировать условную оценку рациона питания при соблюдении ограничений, согласно которым расходы в расчете за единицу продукта не могут превышать его заданной рыночной цены. Цель первой, прямой задачи заключается в том, чтобы закупаемые продукты были возможно более дешевыми, удовлетворяя вместе с тем требованиям в отношении питательной ценности, а цель сопряженной двойственной задачи – в том, чтобы при заданных рыночных ценах на продукты получить рацион наиболее высокопитательный. Имея краткую запись общей задачи линейного программирования в виде:
106
F =∑ = n j jjxc 1 䲸 max при ограничениях: ∑ = n j jijxa 1 ≤ bi ( i =1,2,…, m ),
xj ≥ 0 ( j =1,2,… n ). можно так же кратко записать двойственную к ней задачу: m
Z =∑ b i y i 䲸 min i=1 при ограничениях: m ∑ aijy i ≥ c j ( j =1,2,…, n ), i=1
yi ≥ 0 ( i =1,2,…, m ). Пример 2.2.3. Дана исходная задача: максимизировать линейную функцию F = 2⋅ х 1 + 3⋅ х 2 → max при ограничениях x 1 + 3⋅ x 2 ≤ 18, 2⋅ x 1 + x 2 ≤ 16,
x 2 ≤ 5, 3⋅ 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, 3⋅ y 1 + y 2 + y 3 ≥ 3,
y i ≥ 0, i = 1, 4.
Ви переглядаєте статтю (реферат): «Двойственная задача линейного программирования» з дисципліни «Математична економіка»
