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

 

Рассмотрим ещё раз общую задачу линейного программирования с ограничением в форме уравнений и неравенств.

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

Требуется найти экстремальное (максимальное или минимальное) значение функции

 

(5.1)

                             

при следующих линейных ограничениях:

 

(5.2)

 

.

(5.3)

                                   

Линейная функция L называется целевой функцией. В выражениях (5.1) – (5.3) х ₁ ,х ₂ ,…,х _n – искомые (неизвестные) величины. Ими могут быть, в зависимости от вида задачи, количество изделий первого, второго и т.д. типоразмера, количество материала соответствующей марки, количество оборудования какой-либо группы и т.п.

Коэффициенты при неизвестных в целевой функции (5.1) с ₁, с ₂ ,…, с _n – заданные постоянные величины. Их смысл также зависит от решаемой задачи и может представлять собой себестоимость, цену или прибыль от одного изделия соответствующего типоразмера, цену оборудования, материалов, недогрузку оборудования во времени (в часах) или отходы материала при раскрое и т.п. Проблема выбора показателей, определяющих значения с ₁, с ₂ ,…,с _n в целевой функции (5.1), зависит от выбора критерия и показателя оптимальности решаемых экономических задач.

Коэффициентами при неизвестных в линейных уравнениях (5.2) являются числа a_ij, где i – номер уравнения или строки, в котором находится данный коэффициент (i= 1,2 ,…, m), j – номер неизвестной, при которой стоит этот коэффициент (j = 1,2 ,…, n) (номер столбца).

Коэффициенты a_ij являются заданными постоянными числами и выражают те или иные затраты: времени на изготовление одного изделия по одной группе оборудования, материала на изготовление одного изделия и т.д.

Свободные члены в линейных неравенствах (5.2) b_i (i =1,2,…, m) обозначают, например, величину тех или иных ресурсов, которыми располагают или могут располагать предприятия, экономический район или народное хозяйство страны в целом. Ими может быть оборудование или время его работы, запасы материалов, численность рабочих, продолжительность рабочего времени и др. Выражение (5.3) означает, что искомые переменные величины x_j не могут быть отрицательными.

Каждое из решений системы (5.2) и (5.3) принято называть возможным или допустимым планом.

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

Из множества решений, удовлетворяющих условиям (5.2) и (5.3), необходимо найти такое, при котором целевая функция (5.1) принимала бы максимальное (или минимальное) значение.

Нахождение экстремума целевой функции (5.1) при условии, что переменные удовлетворяют линейным ограничениям (5.2) и (5.3), и составляет предмет линейного программирования.

 

Варианты решения задачи линейного программирования

 

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

1) условия задач (5.2) и (5.3) противоречивы, т.е. не существует набора чисел х ₁, х ₂ ,…,х _n, удовлетворяющих всем условиям задачи;

2) условия (5.2) и (5.3) непротиворечивы, но целевая функция не ограничена;

3) система условий (5.2) и (5.3) совместна, и экстремум целевой функции существует, т.е. значение максимума или минимума целевой функции (5.1) конечно.

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