Лекция 7. Содержательная интерпретация прямой и двойст¬венной задачи


Содержание лекционного занятия:

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

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

· Основное неравенство теории двойственности

Прямая задача. Для изготовления n видов продукции предприятие ис­пользует m видов ресурсов, которые имеются на предприя­тии в количестве: b1, b2,..., bm. При этом количество каждо­го из ресурсов i (i=l...m), которое идет на производство единицы продукции j-го вида (j=l...n), задается технологи­ческими коэффициентами аij. Выручка, получаемая пред­приятием от продажи единицы изготовленной продукции j-го вида (j=l...n), составляет соответственно c1,c2,...cn. Не­обходимо составить такой план производства продукции X=(x1,x2,...xn), при котором выручка предприятия от реали­зации всей продукции, изготовленной в соответствии с данным планом, будет максимальной, а количество каждо­го из ресурсов, используемых для выполнения заданного плана, не превысит имеющегося на предприятии запаса каждого из них.

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

целевая функция: F = c1x1, + c2x2 + c3x3 +... + cn xnmax отражает цель предприятия, которая заключается в макси­мизации выручки от продажи продукции, изготовленной в соответствии с оптимальным планом X=(x1,x2,...xn);


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

отражает требования, предъявляемые к данному плану, ко­торые состоят в том, что количество каждого из видов ре­сурсов i (i=l...m), необходимых для производства каждого j-ro вида продукции (j=l...n) в количестве xj, не должно превышать запасов bj каждого из ресурсов, имеющихся на предприятии;

каждое из неравенств, входящих в систему прямых ог­раничений: х1³0,х2³0,...,хn³0 отражает требования, состоящие в том, что количество каж­дого j-ro вида продукции (j=l...n) не может быть отрица­тельным.

Двойственная задача. Предположим, что то же предприятие, которое для про­изводства n видов продукции использует m видов ресурсов, при тех же самых технологических коэффициентах aij хочет минимизировать затраты на используемые ресурсы. Для этого ему необходимо найти такие оценки (цены) каждого из ресурсов — уi (i=l.. .m), при которых затраты на них бы­ли бы минимальны, при этом искомые оценки (цены) ресурсов должны быть установлены таким образом, что за­траты на производство единицы продукции каждого j-ro вида не превышали бы выручки от ее реализации.

В данном случае под оценками (ценами) подразумева­ются объективно обусловленные оценки (понятие, впервые введенное Л. Канторовичем), которые, в отличие от цен, задаются не извне, а определяются самим предприятием для внутреннего пользования.

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

целевая функция: Z(y) = y1 b1, + у2b2 +... + ymbmmin отражает цель предприятия, которая заключается в мини­мизации затрат;

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


отражает требования, предъявляемые к искомым оценкам — y1, y2, …, ym которые выражаются в том, что затраты на производство единицы каждого j-го (j=l...n) вида продук­ции не превышают выручки от ее реализации (т.е. ее цены);

каждое из неравенств, входящих в систему прямых ог­раничений: У1³0,у2³0,...,уm³0

отражает требования, предъявляемые к оценкам, которые заключаются в том, чтобы каждая из них — уi (i = l...m) должна быть неотрицательной.

Основное неравенство теории двойственности

Для любых допустимых решений Х=(хь x2,..., хn) и Y =(y1, y2,…,ym) исходной и двойственной задач справедли­во неравенство:


Теорема. (Достаточный признак оптимальности)

Если X*=(x*1,x*2,...,x*n) и У*=(y*1,y*2,-..,y*m) — допус­тимые решения взаимодвойственных задач, для которых выполняется равенство: F(X*)=Z(Y*),

то X* — оптимальное решение исходной задачи, а Y* — оптимальное решение двойственной.

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

Первая (основная) теорема двойственности

Если одна из взаимодвойственных задач имеет опти­мальное решение, то его имеет и другая, причем оптималь­ные значения их линейных функций равны: Fmax(X) = Zmin(X) F(X*)=Z(Y*).

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

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

Вопросы для самоконтроля:

1.Как строится математическая модель.

2.Основные элементы модели.

Рекомендуемая литература:

1.Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высш. шк., 1986.

2.Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. М.: Наука, 1984.