Лекция 2 линейное программирование

 

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

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

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

 

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

 

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

Максимизировать (минимизировать) функцию

 

                                                               (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)

 

 

Примеры задач линейного программирования в экономике

 

Пример 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 -м способом, .

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

 

.

 

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