2. Линейное программирование

Термин «линейное программирование» впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному программированию (основные задачи и приложения, критерий оптимальности, экономическая интерпретация, методы решения, геометрическая интерпретация результатов решения) были проведены в конце 30-х годов в СССР в Ленинградском университете Л. В. Канторовичем.

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

Линейное программирование широко применяется в сфере военной деятельности, сельском хозяйстве, промышленности, управлении производственными процессами и запасами, в экономике и на транспорте.

1. Общая задача линейного программирования.

Общей задачей линейного программирования (ОЗЛП) называют задачу: Максимизировать (минимизировать) функцию

(2.1)

при ограничениях: (2.2)

где c_j, a_ij, b_i -заданные действительные числа, (2.1) - целевая функция, (2.2) - ограничения, - план задачи.

Экономическая интерпретация модели ЛП состоит в следующем. Моделируемая система характеризуется наличием нескольких видов «производственной деятельности» , для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы Расход i-го ресурса на единицу продукта j-го вида производственной деятельности равен a_ij. В свою очередь при таком потреблении результат j-го вида производственной деятельности для единицы соответствующего продукта (удельная стоимость или прибыль) характеризуется величиной c_j.

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

Оптимальным решением (или оптимальным планом) задачи ЛП называется решение системы ограничений (2.2), при котором линейная функция (2.1) принимает оптимальное значение.

Термины «решение» и «план» - синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй - о содержательной стороне (экономической интерпретации).

Симметричной формой записи ЗЛП называют задачу

или задачу (2.3)

2. Линейное программирование в экономике

1. Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, фирма и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров) П_j, Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Все эти виды ограничивающих факторов называют ингредиентами R_i, Они ограничены, и их количества равны соответственно b₁,b₂,...,b_m условных единиц. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.д. Примем в качестве такой меры, например, цену реализации c_j, j= . Известны также технологические коэффициенты a_ij, , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Обозначим через план производства, показывающий, какие виды товаров П₁, П₂, ..., П_n нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Математическая модель задачи имеет следующий вид:

(2.4)

Так как переменные x_j входят в целевую функцию Z( ) и систему ограничений только в первой степени, а показатели a_ij, b_i, c_j являются постоянными в планируемый период, то (2.4) - задача линейного программирования.

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

Модель задачи о наилучшем составе смеси рассмотрим на примере задачи формирования минимальной потребительской продовольственной корзины. Задан ассортимент продуктов , имеющихся в продаже. Каждый продукт содержит определенное количество питательных веществ, обозначаемые номерами 1,2,..., m (углеводы, белки, жиры, витамины, микроэлементы и др.). Единица j-го продукта содержит a_ij единиц i-го питательного вещества. Для нормальной жизнедеятельности в заданный промежуток времени нужно потреблять не менее b_i единиц i-го питательного вещества. Обозначим через c_j стоимость единицы продукта j-го вида. Необходимо определить требуемую потребительскую продовольственную корзину, имеющую минимальную стоимость.

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

Математическая модель задачи имеет следующий вид:

(2.5)

3. Задача о раскрое материалов. Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы ( по длине, площади, объему, массе или стоимости) сводятся к минимуму.

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

Пусть n - число различных видов материала, поступающего на раскрой; d_j - количество материала j-го вида, m - число различных видов изделий, которые надо изготовить; b_i - число изделий i-го вида, ; l -число различных способов раскроя; a_ijk - число изделий i-го вида, которое можно получить из единицы материала j-го вида при k-м способе раскроя, ; c_jk - себестоимость раскроя единицы материала j-го вида k-м способом, .

Обозначим через x_jk - количество единиц материала j-го вида, раскраиваемых k-м способом, .

Математическая модель задачи имеет следующий вид:

.

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

2.3. Геометрическая интерпретация и графическое решение ЗЛП.

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

Случай двух переменных не имеет особого практического значения, но его рассмотрение проясняет свойства ОЗЛП, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации.

Пусть дана задача:

Z=c₁x₁+c₂x₂ max (2.6)

(2.7)

(2.8)

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

Введем на плоскости декартову прямоугольную систему координат x₁Ox₂ и сопоставим каждой паре чисел (x₁,x₂) точку плоскости с координатами x₁ и х_2. Выясним сначала, что представляет собой множество точек, соответствующих допустимым решениям данной задачи.

Рассмотрим одно линейное неравенство .

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

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

Каждое из ограничений (2.7), (2.8) задает на плоскости х₁Oх₂ некоторую полуплоскость. Нас интересуют те точки плоскости, координаты которых принадлежат всем полуплоскостям. Следовательно, допустимое множество ЗЛП геометрически изображается пересечением (общей частью) полуплоскостей, определяемых отдельными ограничениями. Полуплоскость - выпуклое множество. Множество называется выпуклым, если ему вместе с двумя произвольными точками принадлежит и прямолинейный отрезок, их соединяющий. Пересечение любого числа выпуклых множеств является выпуклым множеством. Таким образом, область допустимых решений задачи (2.6) - (2.8) есть выпуклое множество. На рис.2.1 представлены возможные ситуации, когда область допустимых решений ЗЛП - выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), прямая линия (г), луч (д), отрезок (е), пустое множество (ж).

X₂

X₂ X₂

б)

0 а) X₁ 0 X₁

Х₂ Х₂ Х₂

в) 1 д)

г)

0 Х₁ 0 Х₁ 0 Х ₁

Х₂ Х₂

е) ж)

Х₁

0

х

0 Х₁

Рис.2.1

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП - непустое множество, например, многоугольник ABCDE рис.2.2.

X₂

B C

M

A

D

E

0 X₁

Рис.2.2 N

Выберем произвольное значение целевой функции Z=Z₀. Получим

c₁x₁+c₂x₂=Z₀

Это уравнение прямой линии (рис.2.2 - прямая MN). В точках прямой MN целевая функция сохраняет одно и то же постоянное значение Z₀.

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

Возникает вопрос: как установить направление возрастания (убывания) целевой функции по x₁ и х₂ :

(2.9)

(2.10)

Частная производная (2.9) и (2.10) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, с₁ и с₂ - скорости возрастания вдоль осей Oх₁ и Oх_2. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор - указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Вектор перпендикулярен к прямым Z = const семейства

Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.

1, С учетом системы ограничений строим область допустимых решений.

2. Строим вектор наискорейшего возрастания целевой функции.

3. Проводим произвольную линию уровня Z=Z_0, перпендикулярную к вектору так, чтобы она пересеклась с областью допустимых решений.

4. При решении задач на max перемещаем линю уровня Z=Z₀ в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точки) (на рис.2.2 точка С). В случае решения задачи на min линию уровня Z=Z₀ перемещают в направлении вектора - (на рис .2.2 - точка Е).

Определяем оптимальный план и экстремальное значение целевой функции .

Пример 2.1.

Предприятию необходимо изготовить два вида продукции А и В,

с использованием трех видов ресурсов R_1, R₂, R₃ количество которых ограничено. Исходные данные задачи представлены в таблице:

Вид ресурсов	Количество ресурсов, идущих на изготовление единицы продукции		Запасы ресурсов
	А	В
R1	6	6	36
R2	4	2	20
R3	4	8	40
Доходы от реализации продукции	12	15

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции видов А и В, планируемых к выпуску.

Известно, что доход от реализации единицы продукции А составляет 12 усл. ед. и количество этой продукции - х₁. Следовательно, доход от реализации всей продукции А составит 12х₁ усл. ед. Аналогично, доход от реализации всей продукции В составит 15х₂ усл. ед. Учитывая, что доход от реализации продукции должен быть максимальным, целевая функция задачи будет иметь вид:

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

Смысл первого ограничения состоит в том, что фактический расход ресурса R₁ на производство продукции А и В, равный 6х₁+6х₂ (здесь 6х₁ - количество единиц ресурса R₁, идущего на изготовление х₁ единиц продукции A; 6х₂ - количество единиц ресурса R_1, идущее на изготовление х₂ единиц продукции В) не должен превышать запаса этого ресурса на предприятии, равного 36 ед. Аналогичный смысл имеют 2-е и 3-е ограничения только для ресурсов R₂ и R₃ соответственно.

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

Таким образом, построена математическая модель нашей задачи как задачи линейного программирования:

Начнем решение задачи с построения области допустимых решений (рис.2.3)

В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных. В двумерном пространстве уравнению соответствует прямая линия, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Прямые х₁=0 и х₂=0 совпадают с осями координат. Полуплоскости x₁>0,x₂>0 лежат соответственно справа от оси Oх₂ и выше оси Oх₁. Множество точек, удовлетворяющих одновременно неравенствам представляют собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти.

Теперь рассмотрим ограничения задачи. Построим по порядку прямые:

` 6x₁+6x₂=36 или х₁+х₂=6 (а)

4х₁+2х₂=20 или 2х₂+х₂=10 (б)

4х₁+8х₂=40 или х₁+2х₂=10 (в)

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

6x₁+6x₂<36

4x₁+2x₂<20

4x₁+8x₂<40

Для определения полуплоскости решений первого неравенства возьмем произвольную точку плоскости, не лежащую на прямой 6х₁+6х₂=36, например (0;0), и подставим ее координаты в неравенство .

В результате подстановки получили верное числовое неравенство 0< 36, и это означает, что начало координат лежит в полуплоскости решений первого неравенства. Сторона, в которой располагается полуплоскость от прямой, указывается штриховой.

Аналогично строим полуплоскость решений остальных неравенств.

[x

X₂

б)

a) N₂

в) M

*6

в

0 N

C x₁

6

D

Рис.2.3

Заштрихованная часть плоскости и представляет собой искомый многоугольник допустимых решений задачи (рис.2.3)

Теперь нужно среди точек построенного многоугольника найти такую, в которой целевая функция Z=12x₁+15x₂ достигает максимального значения. Для этого построим прямую, заданную уравнением 12х₁+15х₂=0, которая является линией нулевого уровня функции Z.

Направление возрастания линейной функции Z=12x₁+15x₂ указывает вектор с началом в точке (0;0) и концом в точке М₁(12,15), координаты которой равны коэффициентам при соответствующих переменных функции Z.

Для нахождения оптимального плана нужно «передвигать» линию нулевого уровня Z параллельно самой себе в направлении вектора до точки ее «последней встречи» с многоугольником, которая и является оптимальным планом задачи. В нашем случае это вершина В многоугольника OABCD - точка пересечения прямых (а) и (в). Координаты ( ) точки найдем, решив систему уравнений.

откуда х₁^*=2, х₂^*=4.

Найдем соответствующее значение целевой функции:

усл. ед.

Ответ. Для обеспечения максимального дохода от реализации готовой продукции предприятию необходимо выпустить 2 ед. продукции вида А и 4 ед. продукции вида В. При таком плане доход от реализации составит 84 усл. ед.

Геометрический метод решения ЗЛП обладает рядом достоинств: он прост, нагляден, позволяет быстро и легко получить ответ. Однако только геометрический метод решения никак не может удовлетворить ни математиков, ни экономистов. Возможны «технические» погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов производства, избыток питательных веществ и т.п.), не выявляются при геометрическом решении задач. Но самое главное - геометрический метод неприемлем для решения практических задач. Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных и выявить экономический смысл входящих в них величин.