Laby_Mat_metody

101

ЛАБОРАТОРНАЯ РАБОТА 12

Метод Гомори решения задачи целочисленного линейного программирования

12.1 Цель работы

Приобретение навыков применения метода Гомори для решения задачи целочисленного линейного программирования.

12.2Порядок выполнения работы

1.Согласно номеру своего варианта выберите условие задачи.

2.Найдите оптимальное решение задачи методом Гомори.

3.Найдите оптимальное решение задачи с помощью Excel и продемонстрируйте его преподавателю.

4.Оформите отчет по лабораторной работе, который должен содержать:

•титульный лист;

•решение задачи.

12.2.1 Образец оформления решения
Задача 0.					(12.1)
f(x) = 20x1 + 40x2 → max;
2x1 + 5x2 ≤ 1600,					(12.2)
1			1		(12.3)
		x1 +		x2 ≤ 100,
	6		5
	x1 ≥ 0, x2 ≥ 0,				(12.4)
	x1, x2 — целые.				(12.5)
Решение. Преобразуем задачу (12.1)-(12.5), умножив обе части неравенства
(12.3) на 30 . Получим задачу
f(x) = 20x1 + 40x2 → max;					(12.6)

2x1 + 5x2 ≤ 1600,

(12.7)

102

5x1 + 6x2 ≤ 3000,	(12.8)
x1 ≥ 0, x2 ≥ 0,	(12.9)
x1, x2 — целые.	(12.10)

По методу Гомори для определения оптимального плана задачи (12.6)- (12.10) решаем задачу (12.6)-(12.9) симплекс-методом. Приведем ее к каноническому виду:

−f(x) = −20x1 − 40x2 → min;		(12.11)
2x1 + 5x2 + x3	= 1600,	(12.12)
5x1 + 6x2 + x4	= 3000,	(12.13)
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.		(12.14)

В таблицах 13.1-13.3 реализован симплекс-метод нахожднеия оптимального решения задачи (12.11)-(12.14).

Таблица 13.1

БП	СЧ	x1		x2		x3	x4
x3	1600	2		5		1	0
x4	3000	5	6			0	1
−f	0	−20	−40			0	0

Таблица 13.2

БП	СЧ		x1		x2	x3		x4
x2	320	2			1	1		0
		5				5
x4	1080		13		0	−	6	1
			5				5
−f	12800		−4		0	8		0

Таблица 13.3

БП	СЧ					x1	x2	x3					x4
		11				0	1	5					2
x2	153												−
		13						13							13
		5				1	0	6					5
x1	415							−
		13								13			13
−f		7				0	0	80					20
	14461
			13					13					13

Табл. 13.3 — оптимальная симплексная таблица, x =							415	5	; 1531311	— опти-
								13
мальный план задачи (12.6)-(12.9). Так как оптимальный						план задачи (12.6)-(12.9)
							(			)
нецелочисленный, он не является оптимальным			планом задачи (12.6)-(12.10). Сле-
					e
дуя методу Гомори, находим	} ,	{15313		}}	= 13.
max {{41513
5		11			11

103

По первой строке табл. 13.3 строи дополнительное линейное ограничение:

						5																						2																				11
						{						} x3 + {−																								} x4 ≥																				.												(12.15)
									13																								13																				13
Так как
5			5			2																	2													2																						2									11
{		} =			, {−						} = −																			− [−														]					= −														− (−1) =					,
	13		13					13																	13														13																		13										13
ограничение (12.15) примет вид
															5													11								11																																(12.16)
																			x3				+									x4				≥												.
														13														13													13
Введем в ограничение (12.16) дополнительную переменную
						5																	11				x4 − x5 =																					11																				(12.17)
													x3 +																																							.
										13													13																										13
Домножим ограничение (12.17) на −1 :
						5																	11																									11																				(12.18)
						−							x3 −														x4 + x5 = −																												.
										13														13																											13
Припишем ограничение (12.18) к табл. 13.3, получим табл. 13.4.
																																	Таблица 13.4
					БП		СЧ															x1									x2								x3														x4									x5
					x2	153									11								0								1									5										−					2						0
															13																						13																		13
															5								1								0						6													5											0
					x1	415																															−
															13																												13							13
					x5					−1311													0								0						−						5							−1311											1
																																											13
					−f										7								0								0						80													20											0
						14461
																	13																				13													13
Следуя методу Гомори, выполним симплексные преобразования табл. 13.4 с
разрешающим элементом −1311 . Получим табл. 13.5.
																													Таблица 13.5
					БП		СЧ														x1								x2								x3													x4								x5
					x2		154																0						1									5										0								−					2
																																				11																									11
																							1						0							7																						5
					x1		415																														−											0
																																								11																		11
					x5		1																0						0									5										1								−					13
																																				11																									11
					−f		14460																0						0							60												0										20
																																				11																						11

Имеем оптимальный целочисленный план расширенной задачи. Тогда оптимальный план исходной задачи (12.1)-(12.5)

x = (415; 154).

104

12.3 Варианты заданий к лабораторной работе

f = 3x1 + x2 → max;

f = x1 + x2 → max;

4x1 + 11x2

≤

44,

8x1 − 3x2 ≤ 24,

1)

{x1 ≤ 5,

2)

{3x1 + 2x2 ≤ 13,

x1 ≥ 0, x2 ≥ 0,

x1 ≥ 0, x2 ≥ 0,

x1, x2 — целые.

x1, x2 — целые.

f = 2x1

−

8x2

→

max;

f = 7x1 − 9x2 → max;

3x

17,

2x1 + x2

9,

1

+ 5x

2

≤

3x2 ≤ 7, ≤

3)

x2

4,

4)

{x1

≤

0, x2

≥

0,

4x1 + 5x2 ≤ 5,

≥

x1

≥

0,

x2

≥

0,

x1, x2 — целые.

x1, x2 — целые.

f = x1 − 7x2 → max;

f = x1 − 7x2 → max;

3x1 + x2

≤

8,

7x1 − x2 ≥ 5,

5)

x1

3x2

2,

6)

2x1 + 3x2

≤

11,

x1

−

6,

≥

x2

≤

5,

≤

x

≥

0

,

x

,

x

1

≥

,

x

2

≥ 0

,

1

2 ≥ 0

0

x1, x2 — целые.

x1, x2 — целые.

f = x1 + 5x2 → max;

f = x1 + 2x2 → max;

x1 + x2 ≤ 7,

x1 + x2 ≤ 5,

7)

−3x1 + 2x2 ≤ 5,

8)

−x1 + 2x2 ≤ 3,

x1 ≤ 6,

x2 ≤ 6,

x1 ≥ 0, x2 ≥ 0,

x1 ≥ 0, x2 ≥ 0,

x1, x2 — целые.

x1, x2 — целые.

f = 2x1 + 5x2 → max;

f = 2x1 + 3x2 → max;

3x1 + 4x2

25,

2x1 + 2x2

1,

9)

2x1

x2

≤1,

10)

4x1

x2

≥15,

x1

−5,

≥

x1 +−3x2

≤

16,

≤

≤

x1 ≥ 0, x2 ≥ 0,

x1 ≥ 0, x2 ≥ 0,

x1, x2 — целые.

x1, x2 — целые.

f = x1 + 2x2 → max;

f = 2x1 + 4x2 → max;

7x1 + 5x2 ≤ 35,

2x1 + 3x2 ≤ 20,

11)

{−2x1 + 3x2 ≤ 6,

12)

{9x1 + 7x2 ≤ 40,

x1 ≥ 0, x2 ≥ 0,

x1 ≥ 0, x2 ≥ 0,

x1, x2 — целые.

x1, x2 — целые.

105

ЛАБОРАТОРНАЯ РАБОТА 13

Целочисленное линейное прогрммирование. Задача о назначениях

13.1 Цель работы

Приобретение навыков построения математических моделей задач о назначении и решения этих задач в Microsoft Excel.

13.2Порядок выполнения работы

1.Согласно номеру своего варианта выберите условие задачи.

2.Постройте модель задачи, включая транспортную таблицу.

3.Найдите оптимальное решение задачи с помощью Excel и продемонстрируйте его преподавателю.

4.Оформите отчет по лабораторной работе, который должен содержать:

•титульный лист;

•транспортную таблицу и модель задачи с указанием всех единиц измерения;

•результат решения задачи с указанием единиц измерения.

13.3Исходные параметры модели задачи о назначениях

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

Рассмотрим в общем виде исходные параметры модели задачи о назначени-

ях.

1.n — количество ресурсов, m — количество работ.

2.ai = 1 — единичное количество ресурса Ai (i = 1, n) , например: один работник; одно транспортное средство; одна научная тема и т.д.

3.bj = 1 — единичное количество работы Bj (j = 1, m) , например: одна должность; один маршрут; одна лаборатория.

106

4. cij — характеристика качества выполнения работы Bj с помощью ресурса Ai . Например, компетентность i -го работника при работе на j -й должности; время, за которое i -е транспортное средство перевезет груз по j -му маршруту; степень квалификации i -й лаборатории при работе над j -й научной темой.

Искомые параметры

1. xij — факт назначения или неназначения ресурса Ai на работу Bj :

{

0, если i-й ресурс не назначен на j-ю работу, xij = 1, если i-й ресурс назначен на j-ю работу.

2. f(x) — общая (суммарная) характеристика качества распределения ресурсов по работам.

Таблица 12.1 Общий вид транспортной матрицы задачи о назначениях

		Работы, Bj				Количество
Ресурсы, Ai	B1	B2	. . .	Bm		ресурсов
A1	c11	c12	. . .		c1m		1
A2	c21	c22	. . .		c2m		1
. . .	. . .	. . .	. . .	. . .			. . .
An	cn1	cn2	. . .		cnm	∑	1
							∑
Количество работ	1	1		1		n	m
			. . .				ai = bj
						i=1	j=1

Модель задачи о назначениях

∑n ∑m

f(x) = cijxij → min,

i=1 j=1

		m
	∑
			xij = 1, i = 1, n,
		j=1		(13.1)
		n
		∑		0,
			xij = 1, j = 1, m,
				{
	i=1
			=	1, , i = 1, n, j = 1, m.
	xij

В некоторых случаях, например, когда cij — это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ, в отличие от (13.1). В этом случае ЦФ f(x) заменяют на fe(x) = −f(x) и решают задачу с ЦФ fe(x) → min , что равносильно решению задачи с ЦФ f(x) → max .

107

13.4 Варианты заданий к лабораторной работе

Постановка задачи

Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности. На эти новые места (НМ) претендуют 3 прежних сотрудника (ПС), уже работающие в других отделах, и 4 новых сотрудника (НС). Номера новых сотрудников, новых и прежних мест выбираются по вариантам из табл. 12.2. Номера прежних мест являются номерами прежних сотрудников.

Отдел кадров оценил по десятибалльной шкале компетентность новых сотрудников (табл. 12.3) и прежних сотрудников (табл. 12.4) для работы и на новых местах, и на прежних местах (ПМ), то есть занимаемых прежними сотрудниками. Необходимо учесть, что руководство предприятия, во-первых, предпочитает, чтобы прежние сотрудники не претендовали на места друг друга, и, во-вторых, не намерено увольнять прежних сотрудников.

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

Рекомендации к решению задачи о назначениях

1.Процесс приведения задачи о назначениях к сбалансированному виду имеет свои особенности по сравнению с транспортной задачей. Если условие сбалансированности задачи (13.1) не выполняется из-за нехватки работ или исполнителей

вколичестве kab , то для создания баланса надо ввести такое же количество kab фиктивных строк или столбцов.

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

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

4.Значения "тарифов" cзij выбираются в зависимости от направления оптимизации ЦФ задачи о назначениях ( f(x) → max или f(x) → min ). При этом

руководствуются принципом "невыгодности" запрещенных назначений. Так, ес-

ли f(x) — это общая компетентность работников, то в качестве запрещающих надо выбирать нулевые компетентности cзij . А если f(x) — это общее время про-

хождения машинами транспортных маршрутов, то в качестве запрещающих надо выбирать значения cзij , превосходящие по величине максимальные реальные зна-

чения cij .

5. При решении задач о назначении в Excel необходимо учитывать, что переменные xij являются булевыми.

108

13.4.1 Особенности решения задач с булевыми переменными

Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные xj могут принимать только одно из двух значений: 0 или 1. Такие переменные в честь предложившего их английского математика Джорджа Буля называют булевыми. На рис. 13.1 представлена экранная форма с решением некоторой двухиндексной задачи с булевыми переменными.

Рис. 13.1: Решение двухиндексной задачи с булевыми переменными

Помимо задания требования целочисленности при вводе условия задач с булевыми переменными необходимо:

•для наглядности восприятия ввести в экранную форму слово "булевы" в качестве характеристики переменных (см. рис. 13.1);

•в окне "Поиск решения" добавить граничные условия, имеющие смысл ограничения значений переменных по их единичной верхней границе (рис. 13.2).

Рис. 13.2: Добавление условия единичной верхней границы значений переменных

Вид окна "Поиск решения" для задачи с булевыми переменными, представленной на рис. 13.1, приведен на рис. 13.3.

109

Рис. 13.3: Окно "Поиск решения" для задачи с булевыми переменными

Варианты

Таблица 12.2 Номера сотрудников и мест их работы для конкретного варианта

№	Новые сотрудники	Места работы прежних	Новые места
варианта	(НС)	сотрудников (ПМ)	(НМ)
1	3, 4, 7, 8	1, 2, 3	1, 2
2	1, 2, 5, 6	2, 5, 6	2, 3
3	5, 6, 7, 8	1, 2, 5	3, 4
4	3, 4, 5, 6	4, 5, 6	1, 4
5	1, 2, 3, 4	2, 3, 4	2, 4
6	2, 4, 6, 8	3, 4, 6	1, 3
7	1, 3, 5, 7	2, 3, 6	1, 4
8	2, 3, 6, 7	3, 4, 5	2, 3
9	1, 4, 5, 8	2, 3, 5	3, 4
10	2, 3, 4, 5	1, 2, 6	1, 2
11	4, 5, 6, 7	1, 3, 5	2, 4
12	1, 2, 7, 8	2, 4, 6	1, 3

110

Таблица 12.3

Компетентность новых сотрудников

	НМ1	НМ2	НМ3	НМ4	ПМ1	ПМ2	ПМ3	ПМ4	ПМ5	ПМ6
НС1	6	5	7	6	5	6	7	6	7	5
НС2	5	5	8	8	7	6	4	5	8	8
НС3	6	7	5	6	4	5	4	5	6	6
НС4	7	8	7	6	5	7	6	8	5	5
НС5	7	6	6	5	5	4	5	5	4	6
НС6	8	8	9	7	6	7	8	7	9	8
НС7	9	8	9	9	8	7	8	9	8	7
НС8	7	7	8	9	7	8	9	6	7	8

					Таблица 12.4
	Компетентность прежних сотрудников
	НМ1	НМ2	НМ3	НМ4	Занимаемое место
ПС1	7	6	6	7	7
ПС2	8	9	7	7	8
ПС3	6	5	6	6	6
ПС4	7	9	6	8	8
ПС5	8	7	8	8	7
ПС6	4	5	6	4	5