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

Найти вектор пространства E_n который максимизирует (минимизирует) функцию цели

(1)

при следующих условиях

(2)

x₁,x₂,…,x_p≤0, (p≤n) (3)

1. 
   - функция цели
2. 
   - функциональные ограничения задачи (система линейных неравенств и уравнений)
3. 
   - прямые ограничения задачи

Условимся относительно терминологии, которую будем использовать в дальнейшем.

Вектор пространства E_n, координаты которого удовлетворяют всем ограничниям (2) и (3) общей задачи линейного программирования называется планом (допустимым планом) ЗЛП.

Множество всех планов ЗЛП называется областью допустимых планов ЗЛП и обозначается ОДП. Решение ЗЛП находится на границе области ОДП.

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

2. Задача о диете.

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

Имеется n видов продуктов питания и m химических элементов, необходимых для суточного потребления.
a_ij – содержание i-го (i=1,2,…,m) химического элемента в одной единице j-го (j=1,2,…,n) продукта питания.
b_i – минимальное суточное потребление i-го химического элемента.
c_j – стоимость одной единицы j-го продукта питания.
Требуется составить суточный рацион питания – сколько продуктов каждого вида нужно приобрести, чтобы рацион имел минимальную стоимость, и питание было разнообразным.
В задаче о диете стоимость можно заменить на калорийность продуктов питания, и сформулировать задачу в следующем виде: питание должно быть низкокалорийным, но содержать все необходимые для суточного потребления химические элементы.

^ Строим экономико-математическую модель.

Управляемая переменная x_j – количество продукта j-го вида, которое будем приобретать (j=1,2,…,n).

Функция цели – суммарная стоимость продуктов питания

(1)

Ограничения

(2)

x_j 0, j=1,2,…,n (3)³

Решить задачу – значит найти вектор , такой, что при условиях (2) и (3).

Эта задача также является задачей линейного программирования.

3. Задача планирования производства

Задача планирования производства содержательно ставится следующим образом.

Пусть имеется некоторый экономический объект (предприятие, цех, артель и т. п.). Необходимо спланировать производство n видов продукции, если известно:

1. 
   на производство всех видов продукции используется m видов ресурсов, причем запасы каждого из них ограничены, и пусть b_i (i=1,2,…,m) – это количество ресурса i-го вида, которое имеется в наличии;
2. 
   известна величина a_ij – количество i-го ресурса (i=1,2,…,m), которое затрачивается на производство одной единицы j-го продукта (j=1,2,…,n);
3. 
   известна стоимость c_j (j=1,2,…,n) реализации одной единицы j-го продукта.

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

^ Строим экономико-математическую модель задачи.

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

Введем переменную x_j (j=1,2,…n) – количество выпускаемой продукции j-го вида.

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

В нашем случае такой функцией является суммарная прибыль .

(1)

Мы будем максимизировать функцию цели.

1. 
   Введем ограничения на управляемые переменные – количество ресурсов каждого вида ограничено величиной bi (i=1,2,…,m).
   (2)
   К системе (2) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства:
   xj 0, j=1,2,…,n (3)³
   ^ Решить задачу – значит найти такой вектор ,который будет удовлетворять всем ограничениям (2), (3) и максимизировать функцию цели.
   
   Легко заметить, что функция - линейная, так как все переменные используются в ней только в первой степени. Ограничения (2) представляют собой систему линейных неравенств, (3) – также линейное неравенство. Такую задачу называют задачей линейного программирования (ЗЛП).
   Несмотря на явную условность рассматриваемой ситуации и кажущуюся простоту задачи (1)-(3), ее решение является далеко не тривиальным и во многом стало практически возможным только после разработки специального математического аппарата. Существенным достоинством используемых здесь методов решения является их универсальность, поскольку к модели (1)-(3) могут быть сведены очень многие как экономические, так и неэкономические проблемы.

4. Задача о раскрое

Постановка задачи. На раскрой поступает s различных материалов, требуется изготовить n различных видов изделий, причем продукция выпускается комплектами и в комплект входит b_k изделий k -го вида. Каждая единица j -го материала может быть раскроена p различными способами так, что при использовании i -го способа получается a_ij^k единиц изделий k -го вида. Известно, что материала j -го вида имеется c_j единиц. Найти план раскроя, обеспечивающий максимальное число комплектов при заданных ограничениях на материал.

Модель.

Пусть x_ij – число заготовок j -го материала, раскроенных i -м способом.

5.

Это задача нелинейного программирования. Размерность задачи s x p*s. Но ее можно привести к линейному виду. Введем еще одну переменную y – количество комплектов. Тогда получим модель:

6.

Полученная модель относится к классу ЛП (ЦЛП). Размерность задачи (s+n) x (p*s+1).

Методы решения: в зависимости от необходимости наложения условия целочисленности на переменные задачи либо методы ЛП, либо ЦЛП: метод Гомори, метод ветвей и границ для ЦЛП.

5. Графический метод решения задач линейного программирования

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

Найти минимальное значение функции

при ограничениях вида

и

Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми: .

Линейная функция (1) при фиксированных значениях является уравнением прямой линии: .

Пример графического решения задачи линейного программирования с 6 условиями.

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

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

Значения уменьшаются в направлении вектора , поэтому прямую передвигаем параллельно самой себе в направлении вектора .

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

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

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

Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.

Поиск по сайту: