Постановка и правила построения двойственной задачи

Двойственность в линейной оптимизации

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

Пусть дана общая задача линейной оптимизации (исходная задача):

произвольного знака при .

Двойственная к ней задача имеет вид:

произвольного знака при .

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

1) упорядочивается запись исходной задачи, т.е. если целевая функция задачи максимизируется, то ограничения неравенства должны быть вида £ , если минимизируется — то вида ³. Выполнение этих условий достигается умножением соответствующих ограничений на (-1);

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

3) каждой переменной двойственной задачи соответствует i-е ограничение исходной задачи, и, наоборот, каждой переменной прямой задачи соответствует j-e ограничение двойственной задачи;

4) матрица из коэффициентов при неизвестных двойственной задачи образуется транспонированием матрицы, составленной из коэффициентов при неизвестных системы ограничений исходной задачи;

5) если на j-ю переменную исходной задачи наложено условие неотрицательности, то
j-e ограничение двойственной задачи будет неравенством, в противном случае j-e ограничение будет равенством; аналогично связаны между собой ограничения исходной задачи и переменные двойственной.

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

Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами которые могут использоваться для выпуска п видов продукции. Пусть также известны стоимость единицы j-го вида продукции и норма потребления i-го ресурса на производство единицы j-й продукции — а_ij.

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

При этом расход ресурсов не должен превышать их наличия:

Все неизвестные по своему экономическому смыслу неотрицательны:

По исходным данным сформулируем другую экономическую задачу (двойственную).

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

Математическая модель задачи имеет вид

Здесь — общая оценка ресурсов. Каждое j-е ограничение из системы представляет собой неравенство, левая часть которого равна оценке всех ресурсов, расходуемых на производство единицы j-го вида продукции, а правая — стоимости единицы этой продукции.

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

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

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

В соответствии с указанными выше правилами запишем двойственную задачу:

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

Транспортная задача

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

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

Математически транспортная задача по критерию стоимости формируется следующим образом. Имеется п потребителей и т поставщиков однородного груза. Мощность i-гo поставщика (i = 1,m) обозначим а_i, спрос j-го потребителя (j = 1,п) b_j. Затраты на перевозку одной тонны груза от i-гo поставщика до j-го потребителя обозначим с_ij. Размер поставки продукции поставщиком i потребителю j обозначим х_ij; общую сумму затрат на перевозку груза обозначим через F.

Запишем математическую модель задачи:

1) объем поставок i-гo поставщика должен равняться количеству имеющегося у него груза:

2) объем поставок j-му потребителю должен быть равен его спросу:

3) запас груза у поставщиков должен равняться суммарному спросу потребителей:

4) размер поставок должен выражаться неотрицательным числом:

5) общая сумма затрат на перевозку груза должна быть минимальной:

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

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