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

Линейное программирование (ЛП) – математический метод отыскания максимума или минимума линейной функции при наличии ограничений в виде линейных неравенств или уравнений («линейные» здесь означает, что на графике функции будут изображаться в виде прямых, обозначающих первые степени соответствующих величин). [11]

В общем виде постановка задачи ЛП заключается в следующем. Требуется найти экстремум (максимум или минимум) линейной целевой функции

f(х) = с1х1 + с2х2 + … + сnхn (4.3)

где х = (х1, х2, … , хn), при ограничениях (условиях), представленных с помощью системы линейных уравнений или неравенств:

а11х1 + а12х2 + … а1nхn {? , = , ?} b1 ,

а21х1 + а22х2 + … а2nхn {? , = , ?} b2 , (4.4)

………………………………………

аm1х1 + аm2х2 + … аmnхn {? , = , ?} bm ,

хj ? 0, j = 1, n .

где хj – искомые величины, содержащие решение поставленной задачи, bi и сj (i = 1, m, j = 1, n) – заданные постоянные величины, характеризующие условия задачи. [12]

Обычно включаемое в систему тривиальное условие [13] неотрицательности переменных хj ? 0 (j = 1, n) вытекает из реального экономического смысла разрешаемости задач.

Систему ограничений (4.4) называют функциональными ограничениями задачи ЛП, а ограничения хj ? 0 – прямыми. [14]

Наиболее часто встречается две разновидности задач ЛП: [15]

1) Каноническая задача ЛП. В этом случае система ограничений, помимо тривиальных ограничений (2.2.5) включает в себя только уравнения. В этом случае задача имеет следующий вид: найти экстремум функции

n

f(х) = a cjхj

j = 1 (4.5)

при наличии ограничений

а11х1 + а12х2 + … а1nхn = b1 ,

а21х1 + а22х2 + … а2nхn = b2 , (4.6)

……………………………..

аm1х1 + аm2х2 + … аmnхn = bm ,

хj ? 0, bi ? 0, i = 1, m, j = 1, n .

2) Стандартная задача ЛП. Это означает, что система условий состоит только из неравенств, в число которых входят тривиальные ограничения:

n

max (min) f(x) = a cjxj

j = 1

при наличии ограничений

а11х1 + а12х2 + … а1nхn {? , ?} b1 ,

а21х1 + а22х2 + … а2nхn {? , ?} b2 , (4.7)

……………………………..

аm1х1 + аm2х2 + … аmnхn {? , ?} bm ,

хj ? 0, bi ? 0, i = 1, m, j = 1, n .

Стандартная задача ЛП может быть сведена к канонической. Добавив в систему ограничений некоторые дополнительные переменные хn+k ? 0 со знаком "-" в случае ограничений типа ? и со знаком "+" в случае ограничений типа ?, можно превратить ее из системы неравенств в систему уравнений.

Переход от задачи на минимум к задаче на максимум (и наоборот) осуществим путем умножения целевой функции на – 1.

В качестве примера можно привести следующую задачу.[16]

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

Общая формулировка задачи соответствует условиям (4.5) и (4.6). Первая строка системы уравнений (4.6)

а11х1 + а12х2 + … а1nхn = b1,

в данном случае будет означать следующее:

а11 – количество единиц производственного ресурса вида 1, используемых на предприятии первого типа;

а12 – количество единиц ресурса вида 1, используемых на предприятии второго типа и т. д.

b1 – общее количество ресурса вида 1 (для предприятий всех типов);

х1, х2 и т. д. – искомое количество предприятий типов 1, 2 и т. д.

Вторая строка упомянутой системы содержит аналогичные величины для ресурса вида 2 и т. д.

Функция цели соответствует формуле (4.5). Требуется обратить в минимум величину

y = с1х1 + с2х2 + … + сnхn ,

где сj (j = 1, n) – показатель, характеризующий издержки предприятия.

Пусть m – общее число различных видов ресурсов, которыми располагает собственник, а n – число типов предприятий, между которыми эти ресурсы должны быть распределены. При этом известно, какое количество однородных ресурсов различного вида (i = 1, m) может быть реализовано на каждом из предприятий данного типа (j = 1, n). Известно также относительное значение издержек на каждом из предприятий (ij).

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

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

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

Таблица 4.1 Относительные издержки на предприятиях

Тип предприятия 1 2 3 4 5 6 Издержки 0,4 0,5 0,2 0,8 0,6 0,3

Пусть система уравнений, учитывающая ряд ограничений, сопряженных с распределением ресурсов по предприятиям, имеет вид, аналогичный условиям (4.6):

4х1 + х4 = 16,

2х2 + х5 = 10,

х3 + 2х4 + 6х5 = 76,

4х1 + 3х2 + х6 = 24,

хj ? 0, bi ? 0, i = 1, m, j = 1, n . – для 1-го вида ресурсов

– для 2-го вида ресурсов

– для 3-го вида ресурсов

– для 4-го вида ресурсов

Смысл уравнений является следующим: первое означает, что ресурс вида 1 может быть размещен на предприятии 1-го типа в количестве 4 единицы и на предприятии 4-го типа в количестве 1 единица при общем лимите 16 единиц, второе – ресурс вида 2 может размещаться в количестве 2 на предприятии типа 2 и в количестве 1 единица на предприятии 5-го типа при лимите в 10 единиц. Аналогично раскрывается смысл остальных уравнений-ограничений. Последнее условие говорит о том, что число предприятий не может быть отрицательным.

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

y = 0,4•х1 + 0,5•х2 + 0,2•х3 + 0,8•х4 + 0,6•х5 + 0,3•х6 .

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

y = 0,4•х1 + 0,5•х2 + 0,2•х3 + 0,8•х4 + 0,6•х5 + 0,3•х6 > min.