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

 

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

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

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

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

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

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

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

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

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

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

 

Пример решения станковой задачи

 

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

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

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

Здесь х – количество станков первой группы оборудования, закреплённых за изделием 1, а у – за изделием 2.

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

Решение этой системы линейных уравнений даёт х =2, а у =1, т.е. за первым изделием нужно закрепить 2 единицы, а за вторым – одну единицу оборудования первой группы. Суммарная производительность оборудования этой группы, соответствующая данному закреплению, и показана в таблице 5.1 в столбцах первого варианта решения.

 

 

Таблица 5.1 – Пример решения станковой задачи

 

 

Группа обо ру-дов.	Коли-чество ед. оборуд. в группе	Произ-водитель-ность ед. оборудо-вания		Первый вариант решения (на каждой группе изготавливают одинаковое количество изделий)		Оптимальный вариант решения (количество изделий, изготавливаемых по группам оборудования)		Оптимальный вариант решения (количество ед. оборудования, занятых изготовлением изделий)
		1-е изд.	2-е изд.	1-е изд.	2-е изд.	1-е изд.	2-е изд.	1-е изд.	2-е изд.	Итого
I	3	10	20	20	20	26	6	8/3	1/3	3
II	3	20	30	36 (x=1,8)	36 (y=1,2)	60	-	3	-	3
III	1	30	80	»21 (x=8/11)	»21 (y=3/11)	-	80	-	1	1
Всего:				77	77	86	86	-	-	-

 

Вычислим отношение производительностей по второму и первому изделиям для каждой группы оборудования и расположим их в порядке убывания (или возрастания) – 8/3(III), 2(I) и 3/2(II). Для группы, у которой это отношение имеет наибольшую величину, все единицы оборудования закрепим за вторым изделием, а у которой это отношение наименьшее – за первым. В оставшейся группе оборудование распределяется так, чтобы выровнять суммарное производство по изделию каждого вида. В данном примере это означает, что III группу оборудования, у которой отношение производительностей максимальное (8/3), нужно целиком закрепить за вторым изделием, а II группу с наименьшим отношением производительностей – за первым изделием. Группа I распределяется так, чтобы выровнять объём производства по обоим изделиям.

Для данного примера это выравнивание происходит путём решения системы двух линейных уравнений с двумя неизвестными.

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

 

10 х +60=20 у +80,

 

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

Второе уравнение составляется исходя из условия, что суммарное количество единиц оборудования I группы, закреплённое за первым и вторым изделиями, не должно превышать имеющегося количества, т.е. для данного случая х+у =3.

Найденное оптимальное решение позволяет увеличить выпуск изделий до 86, что по сравнению с первым возможным вариантом дает увеличение на 11,7% без каких-либо дополнительных затрат. Одновременно это приведёт и к снижению себестоимости изготовленных изделий.

Для задач большего объёма (с большим числом групп оборудования и видов изделий) найти решение значительно труднее и возможно лишь с использованием методов линейного программирования.

Запишем задачу в следующем виде:

максимизировать целевую функцию

 

L =10 x ₁₁+20 x ₂₁+30 x ₃₁→max

при условиях

 

 

 

где x_ij – количество единиц оборудования i -й группы, занятое изготовлением изделий j -го вида.

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

где х _ij – время, затрачиваемое i -й группой оборудования на изготовление изделий j -го вида;

а _ij – суммарная производительность всех единиц оборудования i -й группы в единицу времени при изготовлении изделий j -го вида;

N_j – заданное количество изделий j -го вида, которое требуется изготовить.

Так, если для рассматриваемого примера будет задано, что N ₁= N ₂=50, то задача запишется так:

минимизировать L= x ₁₁+ x ₁₂ при условиях:

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

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

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

Задача оптимального раскроя материала (задача по раскрою) является одним из частных случаев задачи по оптимальному использованию комплексного сырья.