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

6 Определение оптимального целочисленного решения

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

Задача№1

Задача№2		Задача№3

Задача№4

Задача№5

Нет решений

Задача№6		Задача№7

Рисунок 6.1 – Метод ветвей и границ

22

tbicr

Задача №1

не представляет целочисленного решения x1 = 366.667 ,

x2

= 683.333,

E = 708333.333, ее оценка равна 708333.333. Составим две дополнительные задачи, введя

в них ограничения. Задача №2: x1 ≤ 366 ; задача №3: x1 ≥ 367 .

Задача №2

представляет целочисленное решение

x1

= 366 ,

x2

= 684 ,

E = 708000 .

Ее оценка равна 708000 .

Задача

№3

не

представляет

целочисленного

решения

x1

= 367 ,

x2 = 682.5 ,

E = 708250 , ее оценка равна 708250 . Составим еще две дополнительные задачи, введя в

них ограничения. Задача №4: x2 ≤ 682 ; задача №5: x2 ≥ 683.

Задача

№4

не

представляет

целочисленного

решения

x1

= 367.2 ,

x2 = 682 ,

E = 708200 , ее оценка равна 708200 . Составим еще две дополнительные задачи, введя в

них ограничения. Задача №6: x1 ≤ 367 ; задача №7: x1 ≥ 368 .

Задача №6

представляет целочисленное решение

x1

= 367 ,

x2

= 682 ,

E = 708000 .

Ее оценка равна 708000 .

Задача №7

представляет целочисленное решение

x1

= 368 ,

x2

= 680 ,

E = 708000 .

Ее оценка равна 708000 .

Задача №5 не имеет решений.

Таблица 6.1 – Результаты решения задачи оптимизации

Переменная

Решение №1

Решение №2

Решение №3

x1

366

367

368

x2

684

682

680

x3

20

10

0

x4

1660

1710

1760

x5

9000

8500

8000

x6

0

1

2

E

708000

708000

708000

Мы нашли целочисленные решения, их получилось три с одинаковой прибылью. Решение №1.

Переменная x1 = 366 означает, что при данном решении на заводе будет выпускаться 366 автомобилей «Шторм».

23

tbicr

Переменная	= x2 = 684	означает, что при данном решении на заводе будет
выпускаться 684 автомобиля «Торнадо».
Остаточная	переменная	x3 = 32000 −50 ×366 −20 ×684 = 20	означает,	что	при
данном решении не используется 20 часов квалифицированного труда.
Остаточная	переменная	x4 = 40000 −30 ×366 −40 ×684 =1660	означает,	что	при
данном решении не используется 1660 часов неквалифицированного труда.
Остаточная	переменная	x5 = 900000 −1500 ×366 −500 ×684 = 9000 означает,			что

при данном решении возможны еще затраты на выпуск автомобилей в размере 9000 ден. ед.

Остаточная

переменная

x6

=1050 −366 −684 = 0

означает,

что

при

данном

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

Значение целевой функции

E = 708000

означает,

что при

данном

решении

прибыль автозавода составит 708000 ден. ед.

Решение №2.

Переменная

x1 = 367

означает,

что

при

данном

решении

на

заводе

будет

выпускаться 367 автомобилей «Шторм».

Переменная

x2 = 682

означает,

что

при

данном

решении

на

заводе

будет

выпускаться 682 автомобиля «Торнадо».

Остаточная

переменная

x3

= 32000 −50 ×367 −20 ×682 =10 означает,

что

при

данном решении не используется 10 часов квалифицированного труда.

Остаточная

переменная

x4 = 40000 −30 ×367 −40 ×682 =1710

означает,

что

при

данном решении не используется 1710 часов неквалифицированного труда.

Остаточная

переменная

x5 = 900000 −1500 ×367 −500 ×682 = 8500

означает,

что

при данном решении возможны еще затраты на выпуск автомобилей в размере 8500 ден. ед.

Остаточная переменная x6 =1050 −367 −682 =1 означает, что при данном решении

на заводе возможен выпуск еще одного автомобиля.
Значение целевой функции E = 708000	означает,	что при	данном решении
прибыль автозавода составит 708000 ден. ед.
Решение №3.
Переменная x1 = 368 означает, что при	данном	решении	на заводе будет
выпускаться 368 автомобилей «Шторм».

24

tbicr

Переменная	= x2 = 680	означает, что при данном решении на заводе будет
выпускаться 680 автомобилей «Торнадо».
Остаточная	переменная	x3 = 32000 −50 ×368 −20 ×680 = 0	означает,	что	при
данном решении используется весь квалифицированный труд.
Остаточная	переменная	x4 = 40000 −30 ×368 −40 ×680 =1760	означает,	что	при
данном решении не используется 1760 часов неквалифицированного труда.
Остаточная	переменная	x5 = 900000 −1500 ×368 −500 ×680 = 8000 означает,			что

при данном решении возможны еще затраты на выпуск автомобилей в размере 8000 ден. ед.

Остаточная переменная x6	=1050 −368 −680 = 2	означает,	что при	данном
решении на заводе возможен выпуск еще двух автомобилей.
Значение целевой функции	E = 708000 означает,	что при	данном	решении
прибыль автозавода составит 708000 ден. ед.

25

tbicr

7Постановка модифицированной аналитической модели и анализ результатов модификации

7.1Недостатки постановки задачи оптимизации

Проанализировав результаты решения задачи		оптимизации (раздел 6.
«Определение оптимального целочисленного решения»):
Таблица 7.1 – Использование ресурсов
Занятость квалифицированных рабочих		99.938%
Занятость неквалифицированных рабочих		95.85%
Затраты на выпуск от максимально возможного		99%
Вывоз автомобилей от максимально возможного		100%

можно выделить следующие недостатки в работе автозавода: занятость неквалифицированных рабочих составляет всего 95.85%.

7.2 Обеспечение полной занятости

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

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

E =

30x1		+40x2	≤ 40000;
50x1		+20x2	≤ 32000;
1500x1 +500x2				≤ 900000;
x1	≥ 0, x2		≥ 0;
x1	−целое,		x2	−целое.	(7.2.1)
1000x1 +500x2				→ max.

Решением этой задачи будет:

26

tbicr

	x		= 344;
	1		= 740;
	x2
	x3		= 0;
	x	4	=80;
	x5		=14000.
				(7.2.2)
E = 714000 .

При таком решении вывоз в неделю должен составлять 1084 автомобилей, это примерно 217 (1084/ 5 = 216.8 ) автомобилей в день. Решим задачу с новым ограничением на вывоз автомобилей:

	30x1 +40x2						≤ 40000;
	50x +			20x		2	≤ 32000;
		1
	1500x1 +500x2 ≤ 900000;
	x	+ x	2	≤1085;
	1
	x	≥ 0,		x			≥ 0;
	1				2
	x1	−целое,					x2 −целое.

E =1000x1 +500x2 → max .

Решением этой задачи будет:

	x		= 343;
	1		= 742;
	x2
	x3		=10;
	x4		= 30;
	x	5	=14500;
	x6		= 0.

E = 714000 .

217×5 =1085 ;

(7.2.3)

(7.2.4)

(7.2.5)

7.3 Обеспечение частичной занятостью

Допустим, что для эффективного производства необходимо, чтобы занятость рабочих составляла приблизительно 90%. Это может быть связанно с человеческим

27

tbicr

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

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

	занятость:	32000 −20	≈ 35533 часа и	40000 −1660	= 42600 часов соответственно. При
		0.9		0.9

этом количество часов квалифицированного труда возрастет приблизительно на 3533 часа, неквалифицированного – на 2600 часов. Это приблизительно соответствует увеличению числа рабочих на 90 ( 3533/ 40 =88.325 ) и 70 ( 2600 / 40 = 65 ) человек.

Если принять на работу 90 квалифицированных и 70 неквалифицированных рабочих, то количество часов квалифицированного и неквалифицированного труда увеличится на 40 ×90 = 3600 и 40 ×70 = 2800 часов соответственно и будет составлять

35600 и 42800 часов.

Решим задачу с новыми ограничениями на количество часов квалифицированного и неквалифицированного труда:

	30x1 +40x2						≤ 42800;
	50x +			20x		2	≤ 35600;
		1
	1500x1 +500x2 ≤ 900000;
	x	+ x	2	≤1050;
	1
	x	≥ 0,		x			≥ 0;
	1				2
	x1	−целое,					x2 −целое.

E =1000x1 +500x2 → max .

Решением этой задачи будет:

	x		= 375;
	1		= 675;
	x2
	x3		= 3350;
	x4		= 4550;
	x	5	= 0;
	x6		= 0.

E = 712500.

(7.3.1)

(7.3.2)

При этом занятость квалифицированных и неквалифицированных рабочих будет

составлять 90.59% и 89.369% соответственно.
28	tbicr

8Примеры постановок и решения оптимизационных задач

8.1Пример №1 – Задача о выборе оборудования

На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.

Пусть x1 – количество станков типа А, а x2 – количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы

максимизировать производительность E участка (в тыс. единиц за смену):
E = 7x1 +3x2 → max .	(8.1.1)

При этом должны быть выполнены следующие ограничения: по стоимости (в тыс. долларов США):

5x1	+2x2	≤ 20 ,	(8.1.2)
и по занимаемой площади (в м2 ):
8x1	+4x2	≤ 38 ,	(8.1.3)
а также ограничения на неотрицательность и целочисленность:
x1 ≥ 0 , x2 ≥ 0 ,	x1 и x2 - целые числа.		(8.1.4)
Решим задачу при помощи MS Excel. Максимальная производительность			E = 29

(тысяч единиц продукции за смену) достигается при x1 = 2 ,	x2 = 5. Следовательно, надо
покупать 2 станка типа А и 5 станков типа Б.
29	tbicr

8.2 Пример №2 – Задача о производстве изделий

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

Таблица 8.2 – Необходимые трудовые затраты и потребности сырья

Тип изделия	Необходимое время	Необходимое сырье
	(час./ед.)	(фунты/ед.)
1	3	4
2	4	3
3	5	6
Наличный дневной объем	100	100

Доходы от производства единицы каждого из трех типов изделий равны 25 , 30 и 45 долларов соответственно. Если будет производится изделие типа 3 , то его ежедневный объем производства должен быть не мание 5 единиц. Составить план производства предприятия, при котором ежедневная прибыль компании будет максимальной.

Пусть x1 – количество изделий типа 1, x2 – количество изделий типа 2 , x3 –

количество изделий типа 3 . Требуется составить план производства предприятия, при котором ежедневная прибыль E будет максимальной.

E = 25x1 +30x2 + 45x3 → max .

(8.2.1)

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

3x1 +4x2	+5x3	≤100 ,	(8.2.2)
и по необходимому сырью (в фунтах):
4x1 +3x2	+6x3	≤100 ,	(8.2.3)
а также ограничения на неотрицательность и целочисленность:
	30		tbicr

x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 , x1 , x2 и x3 - целые числа.

(8.2.4)

Задача также имеет условие, говорящее о том, что детали типа 3 либо не производятся вообще, либо их должно производится более 5 шт. Это можно представить

как:
x3 = 0 или x3 ≥ 5 .	(8.2.5)

Для нахождения решения необходимо решить задачу дважды: первый раз с условием x3 = 0 , а второй с условием x3 ≥ 5 .

Решим задачу с помощью MS Excel. Максимальная прибыль E =825 достигается при производстве 11 изделий типа 2 и 11 изделий типа 3 , при этом изделия типа 1 не производятся.

8.3 Пример №3 – Задача об объемах производства мебельной фабрики

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

Таблица 8.3 – Нормы затрат ресурсов

Наименование				Расход ресурса
Ресурса			на единицу продукции					Запас
		(в указанных единицах измерения)						ресурса
	Стол	Шкаф		Диван-	Кресло-		Тахта
				кровать	кровать
Трудозатраты (чел.-ч.)	4	8		12	9		10	3690
Древесина (м3)	0.4	0.6		0.3	0.2		0.3	432
Ткань (м)	0	0		6	4		5	2400
Прибыль от выпуска	8	10		16	13		17	-
1 изделия (у.е.)
Предельный объем	480	80		180	120		100	-
выпуска (шт.)
			31					tbicr