1.3. Основы линейного программирования

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

Развитию методов линейного программирования предшествовали формулирование и исследование в XIX веке свойств систем линейных неравенств. Среди первых учёных, заложивших основы линейного программирования как направления прикладной математики, был Джон фон Нейман. Из отечественных учёных, внёсших значительный вклад в развитие этого направления, следует назвать лауреата Нобелевской премии Л.В. Канторовича, Н.Н. Моисеева, Е.Г. Гольштейна и Д.Б. Юдина [4, с. 12].

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

Преодоление разрыва между теорией и практикой стало возможным с внедрением в управленческую деятельность информационных технологий. Возникшую ситуацию можно сравнить с использованием автомобиля. Обычный человек может садиться в него и ехать, не задумываясь о том как работают механизмы и какие при этом используются физические законы. Также и современный менеджер может сесть за компьютер и отыскать оптимальное управленческое решение, не вникая в тот математический аппарат, который он при этом использовал. Ему не обязательно знать, что такое симплекс-метод или линейная форма. Он может в простейшем случае обойтись знанием несложных правил составления моделей, подобных тем, что были изложены в подразделе 1.2. Поэтому, в последнее время, менеджеры и инженеры со студенческой скамьи начинают осваивать в значительных объёмах такие дисциплины, как исследование операций, прикладная статистика и инженерная экономика.

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

Различают три типа задач линейного программирования [4, с. 19]: 1) Стандартная задача; 2) Каноническая задача; 3) Общая задача линейного программирования. Рассмотрим их в общем виде по отдельности.

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

(1.28а)

достигает максимума (или минимума) при наличии ограничений

 , I = 1, …, m; (1.28б)

0, j = 1, …, n, (1.28в)

где a, b и c некоторые коэффициенты.

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

Каноническая задача заключается в нахождении таких переменных , при которых линейная форма

(1.29а)

достигает максимума (или минимума) при наличии ограничений:

 =  , I = 1, …, m; (1.29б)

0, j = 1, …, n. (1.29в)

Как видно из формул, отличие канонической задачи от стандартной заключается в замене знака неравенства в выражении (1.28б) на знак равенства в выражении (1.29б).

Интерес к канонической задаче связан с тем, что именно для неё разра­ботаны основные вычислительные методы и, в частности симплекс-метод.

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

(1.30а)

достигает максимума (или минимума) при наличии ограничений:

 , I = 1, …, k; (1.30б)

 =  , I = k+1, …, m; (1.30в)

0, j = 1, …, r, (1.30г)

где km и rn. Эту задачу можно рассматривать как некоторую комбинацию первых двух. При k = m и r = n общая задача сводится к стандартной, а при k = 0 и r = n − к канонической. Примерами общей задачи является рассмотренные нами проблемы нахождения оптимальной транспортной схемы и пропускной способности.

Рассмотренные задачи можно посредством преобразований переводить из одного вида в другой. Для этого применяют следующие приёмы [5]: 1) задачу на минимум можно свести к задаче на максимум, если в качестве целевой функции взять ту же функцию, умноженную на минус единицу: Z(X) = -Q(X), где Q(X) – целевая функция задачи на нахождение минимума, а X – совокупность переменных; 2) неравенство, выражающее дополнительное условие, можно превратить в равенство при помощи вспомогательной переменной. Например, если мы имеем неравенство  , то его можно перевести в равенство +y =  , вводя переменную y, удовлетворяющую дополнительному неравенству y0. В целевую функцию новая переменная войдёт с нулевым множителем. 3) Если для некоторой переменной не задано ограничение 0, то, вводя новые переменные: 0 и 0, мы можем заменить:  =  - .

Таким образом, без ограничения общности мы можем рассматривать задачи линейного программирования на нахождение максимума целевой функции с ограничивающими равенствами типа (1.28б), с неотрицательными свободными членами и системой ограничивающих неравенств: 0.

Чтобы получить наглядное представление о решении задач линейного программирования, рассмотрим целевую функцию с двумя переменными:

Z(x,y)=5x+4y, (1.31а)

при ограничивающих условиях:

3x+4y12,

15x+3y60, (1.31б)

x0,

y 0.

В случае функции двух переменных лучше проводить анализ задачи, не сводя её к каноническому виду. Сначала мы найдём область допустимых значений x и y. Для этого построим пря­мые    3x+4y = 12 и 15x+2y = 60 (рис. 1.31). Эти уравнения прямых получаются из ограничивающих неравенств заменой знака неравенства на знак равенства. Каждая прямая делит плоскость (x,y) на две полуплоскости. В одной из них соответствующее исходное неравенство выполняется, а в другой – нет. Чтобы найти, где находится интересующая нас область, надо взять координаты произвольной точки в одной из полуплоскостей, подставить их в неравенство и посмотреть, будет ли оно выполняться. Если да, то выбранная точка лежит в интересующей нас полуплоскости. Ту полуплоскость, координаты точек которой удовлетворяют ограничивающему неравенству, отметим штриховкой. Проделав описанные действия для каждого из четырёх ограничивающих неравенств, мы обнаружим, что область допустимых значений представляет собой треугольник с вершинами в точках O, A и B (рис. 1.31). Из рисунка видно, что неравенство 15x+3y60 является избыточным, так как оно не накладывает на область допустимых значений иных ограничений, чем те, которые определяются тремя другими неравенствами.

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

Целевую функцию (1.31а) можно изобразить в виде поверхности в трёхмерном пространстве. Для этого к имеющейся плоскости переменных (x,y) надо добавить перпендикулярную ей ось Z. Совокупность всех комбинаций трёх чисел x, y и z, удовлетворяющих уравнению (1.31а), составляет поверхность значений целевой функции в трёхмерном пространстве. В случае линейной формы типа (1.31а) искомая поверхность будет плоскостью. Если область допустимых значений не ограничена, то целевая функция может не достигать на ней минимума или максимума. Это можно понять, анализируя взаимное расположение поверхности, определяемой целевой функцией, и области допустимых значений. Во всех остальных случаях (кроме пустого множества допустимых значений) задача линейного программирования будет иметь решение и, возможно, не одно.

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

Покажем, как можно найти оптимальную точку графическим способом. Для этого в целевой функции (2.31а) положим Z(x,y)=0 и построим прямую Р, заданную получившимся уравнением 5x+4y=0 (рис. 1.32). Смысл этих построений заключается в том, что мы таким образом нашли область пересечения плоскости (x,y) и плоскости, изображающей целевую функцию. Если теперь построить в плоскости (x,y) семейство прямых, параллельных Р, то мы увидим, что существуют две точки касания линий этого семейства и области допустимых значений. Это очки О и В. В одной из них целевая функция на области допустимых значений достигает минимума, а в другой – максимума. Нетрудно проверить, что минимум достигается в точке О, а максимум − в точке В. Соответствующие минимальное и максимальное значения целевой функции равны нулю и двадцати. Таким образом, можно считать, что наша задача решена.

В первые разработкой методов решения задач линейного программирования начал заниматься советский математик Л.В. Канторович в конце 30-х годов. Однако в то время эти методы не были востребованы и не получили широкой известности. В применении к решению экономических задач симплекс-метод был независимо разработан Георгом Данцигом (George Dantzig) в конце 40-х годов. В то время это стало большим событием и послужило одним из оснований научного менеджмента. Нобелевский лауреат в области экономики Джордж Стиглер (George Stigler1982) начинал свою деятельность с решения типичной проблемы линейного программирования – задачи составления оптимального рациона [6].

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

Чтобы сократить время проведения расчетов, используют следующий алгоритм: 1) Находим любую угловую точку; 2) Находим соседние угловые точки и определяем ту из них, в которой целевая функция принимает наибольшее (или наименьшее) значение; 3) Повторяя предыдущее действие, переберём последовательность узловых точек, пока не придём к такой из них, для которой значение целевой функции будет больше (или меньше), чем для всех соседних. Найденная таким образом точка и является оптимальной точкой области допустимых значений задачи линейного программирования.

Мы не будем подробно останавливаться на технических приёмах нахождения угловых точек. Такую информацию при желании можно найти в специальной литературе [4, 5]. Отметим здесь лишь то, что при решении задач могут возникнуть осложнения, связанные с наличием нескольких решений. При этом указанный выше алгоритм может приводить к зацикливанию процедуры. Необходимо принять меры к его недопущению. Другое осложнение, которое надо предусмотреть, связано с возможной неограниченностью области допустимых значений задачи линейного программирования.