Области применения линейного программирования

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

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

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

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

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

(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) конечно.

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

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

Данные задачи могут быть подразделены на две основные группы. Первая группа – задачи, область применения которых ограничивается отдельным предприятием. К ним относятся задачи, связанные:

1) с технологией производства или технологическим планированием;

2) с оперативно-производственным планированием;

3) с технико-экономическим планированием.

В первую подгруппу входят задачи, получившие в литературе по линейному программированию названия: станковая, раскройная и о смесях. Это были задачи, решённые впервые методом линейного программирования в 1939 г. в работе Л.В.Канторовича, пока единственного российского учёного, удостоенного Нобелевской премии по экономике в 1975 г. вместе с американским экономистом Т. Купмансом за вклад в развитие теории оптимального распределения ресурсов.

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

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

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

Рассмотрим станковую задачу кратко. Эту задачу впервые поставил и решил методом разрешающих множителей Л. В. Канторович на примере задачи фанерного треста.