Тема 1. Модели линейного программирования

1.1. Формулировка классической з адачи линейного программирования

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

В задачах линейного программирования требуется найти экстремум (максимум или минимум в зависимости от содержательной постановки задачи) линейной функции

Эта функция, называемая целевой, неограниченна, и поэтому искать ее максимум или минимум, не налагая никаких ограничений на область изменения вектора Х с компонентами бессмысленно. Интерес представляет задача максимизации этой функции при условии, что вектор Х принадлежит некоторому множеству, причем выбор значений вектора Х определяется условиями типа линейных неравенств.

В общем случае задача линейного программирования формулируется следующим образом: найти величину вектора Х, доставляющего максимум линейной функции

на множестве значений удовлетворяющих ограничениям вида

В более компактной форме:

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

1. 2. Задача о выпуске продукции

Рассмотрим некоторую производственную систему, в которой m ресурсов S₁, S₂,…, S_m участвуют в производственном процессе (сырье, топливо, материалы, инструменты и т.д.). Продукты производятся или потребляются с помощью линейных или технологических процессов. Линейная модель производства, в которой участвуют m ресурсов, состоит из набора технологических процессов P₁, P₂,…, P_n. Она полностью описывается числами a_ij, где a_ij – количество ресурса S_i, потребляемого при a_ij> 0 или производимого при a_ij< 0 при единичной интенсивности использования процесса P_j. Под интенсивностью процесса P_j понимается такое число x_j, если в результате работы этого процесса потреблено a_ij x_j единиц ресурса S_i. Через c_j обозначим доход от реализации единицы продукции, получаемой при использовании процесса P_j с единичной интенсивностью. В более простой интерпретации в качестве P₁, P₂,…, P_n можно рассматривать список производимой продукции. Запасы ресурсов каждого вида ограничены и равны b₁, b₂,…, b_m. Требуется определить, в каком количестве выпускать продукцию каждого вида, чтобы доход от реализации этой продукции был максимален с учетом ограничений на ресурсы. Другими словами нужно определить производственный план. Общий доход от реализации выпущенной продукции будет равен  .

Ограничениями в этой задаче являются требования, чтобы расход ресурсов вида S_i на выпуск всех видов продукции не превышал имеющихся запасов

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

Таблица 1

Виды машин Виды изделий	Первый	Второй	Третий
Первое изделие	0,5	2	0
Второе изделие	1	1	1
Время работы машин	12	30	9

Построим математическую модель этой задачи. Пусть х₁число изделий первого вида, а х₂– число изделий второго вида.

 

 

Вместе с исходной (прямой) задачей рассматривается двойственная к ней задача, которую можно сформулировать следующим образом.

Предположим, что некоторая организация решила закупить ресурсы S₁, S₂,…, S_m фирмы и необходимо определить цены на эти ресурсы у₁, у₂,…, у _m. Естественно, что покупающая организация заинтересована в том, чтобы затраты на покупку ресурсов в объеме b ₁, b ₂,…, b_m по ценам у₁, у₂,…, у _m  были минимальны, то есть

Z = b₁y₁ + b₂y₂ + … +b_my_m ® min.

Предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не меньше той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции j-го вида расходуется сырье S₁ в объеме а_{1 j}, сырье S₂ в объеме а_{2 j} …, сырье S_m в объеме   а _mj по цене у₁, у₂,…, у _m  соответственно, то есть затраты на изготовление продукции P_j должны быть не меньше, чем цена ее реализации. Приходим к ограничениям следующего вида:

а_{1 j} у₁ + а_{2 j} у₂ + … + а _mj у _m ≥ с _j, j =1,2,..., n.

Учитывая условия неотрицательности цены единицы i-го ресурса, приходим к следующей задаче:

Найти такой вектор Y = (у₁, у₂ ,..., у _m) – цен ресурсов, удовлетворяющий системе неравенств

                                     a₁₁ у ₁ + a₂₁ у ₂ + … + a_m1 у _m ≥ c₁,

                                     a₁₂y₁ + a₂₂y₂ + … + a_m2y_m ≥ c₂,

                                      … … … … … … …

                                     a_1jy₁ + a_2jy₂ + … + a_mjy_m ≥ c_j,

                                     … … … … … … …

                                     a_1ny₁ + a_2ny₂ + … + a_mny_m ≥ c_n,

                                          y_i ³ 0, i = 1, 2, …, m,

 

при котором функция Z (Y) = b ₁ y ₁ + b ₂ y ₂ + …+ b_my_m   принимает минимальное значение.

Цены ресурсов в экономической литературе имеют различные названия: учетные, неявные, теневые, объективно-обусловленные оценки (о-о оценки). Смысл этих названий состоит в том, что это условные (ненастоящие) цены. Эти цены определяются в ходе решения задачи, их называют  еще  ценностью ресурсов.

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

Пусть y ₁ – ценность первого ресурса, y ₂ – ценность второго ресурса, а y ₃ – ценность третьего ресурса. Тогда

 

 

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

 

Таблица 2

Прямая задача	Двойственная задача
Максимизировать F = при ограничениях ; i=1,2,...,m xj ³ 0, j = 1, 2, …, n,	Минимизировать Z = при ограничениях ; j = 1, 2, …, n yi ³ 0, i=1,2,...,m

Сравнивая рассмотренные примеры видно, что двойственная задача по отношению к исходной составляется согласно следующим правилам:

1. Если первая задача имеет размеры  (m–ограничений с n неизвестными), то вторая – размеры .

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

3. В правых частях ограничений в каждой задаче стоят коэффициенты при неизвестных в целевой функции другой задачи.

4. В прямой задаче все ограничения представляют собой неравенства типа «», причем в этой задаче требуется достичь . Напротив, в двойственной задаче все ограничения суть неравенства типа «», причем требуется достичь .

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

Пример 3. Решим графическим методом задачу ЛП из примера 1.

Решением линейного алгебраического неравенства относительно двух переменных является совокупность точек плоскости, координаты которых удовлетворяют этому неравенству. Графически – это полуплоскость. Решением системы таких неравенств является их пересечение. Для нахождения такой полуплоскости необходимо знак неравенства заменить на знак равенства, построить соответствующую этому уравнению прямую на плоскости и выбрать из двух образовавшихся полуплоскостей нужную.

 В прямоугольной декартовой системе координат (рис. 1.1.) строим прямую , соответствующую ограничению (1) по двум точкам, например, (24; 0) и (0; 12). Находим, какая из полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (1). Для этого достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Так как прямая не проходит через начало координат, подставляем координаты точки  в первое ограничение . Получаем строгое неравенство . Следовательно, точка О лежит в полуплоскости решений. Штриховкой отмечаем полуплоскость, содержащую точку О. Аналогично строим прямую   по двум точкам (0;30) и (15; 0) и определяем область решений ограничения (2). Третья прямая будет параллельна оси .

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

 

                                        х₂

 

                                         D      C

                                                                                       B

                                                                                           

                                                                                            A

                                           O      F=0                         15                     24                х₁

 

Рис. 1.1. Графическое решение задачи

Множество допустимых решений представляет собой многоугольник ОАВСD (рис. 1.1). Среди точек многоугольника ОАВСD найдем оптимальную.

Строим нормаль линий уровня . Так как решается задача на отыскание максимума целевой функции, то линию уровня  перемещаем в направлении нормали до угловой точки В, которая расположена на прямой, называемой опорной. Эта опорная прямая проходит через точку В пересечения прямых, ограничивающих область допустимых решений и соответствующих неравенствам (1) и (2), перпендикулярно нормали.

В этой точке пересекаются две прямые:

Найдем координаты точки В:

Полученное решение будет оптимальным производственным планом, дающим заводу максимальную прибыль, а именно,

 

 

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

Теорема равновесия. Пусть Х^* – какое-нибудь допустимое решение прямой задачи, а Y ^* – какое-нибудь допустимое решение двойственной задачи. Для одновременной оптимальности этих решений необходимо и достаточно выполнение равенств:

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

Применим теорему равновесия для решения задачи из примера 2.

Пример 4. Запишем прямую и двойственную задачу в таблицу

Прямая задача	Двойственная задача

Тогда теорема равновесия запишется в виде:

Третье ограничение прямой задачи на оптимальном плане выполняется как строгое неравенство, следовательно, соответствующая переменная двойственной задачи равна нулю: y₃^*= 0.

Первое и второе ограничение прямой задачи обращается в точное равенство, следовательно, соответствующие переменные двойственной задачи положительны: y₁^* > 0 и y₂^* > 0.

Условия равновесия можно записать в виде равенств:

Подставляя y₃^*=0 в последнюю систему уравнений, получим систему:

откуда получаем, что y₁^* = , y₂^*= .

Оптимальное решение двойственной задачи Y ^* = (; ; 0), при этом минимум целевой функции двойственной задачи: Z_min = Z(Y^*) = 12· +30· =84.

 

 

Существует определенная связь между значениями целевых функций прямой и двойственной задачи на допустимых решениях. Она определяется следующими теоремами теории двойственности:

Теорема (основное неравенство). Пусть Х – какое-нибудь допустимое решение прямой задачи, а Y – какое-нибудь допустимое решение двойственной задачи. Тогда справедливо неравенство .

Следствие 1 (достаточный признак оптимальности). Если для каких-то допустимых решений  и  соответственно прямой и двойственной задач выполняется равенство , то  есть оптимальное решение прямой задачи, а  – оптимальное решение двойственной задачи.

Следствие 2. Если в одной из пары двойственных задач целевая функция не ограничена с соответствующей стороны (т.е.  в прямой задаче или  в двойственной задаче), то другая задача не имеет допустимых решений.

Основная теорема. Если разрешима одна из пары двойственных задач, то разрешима и другая задача, причем .

Действительно, для разобранных в примерах задачах мы получили соотношение