umk_2001_028

Пример выходного файла

3

3 4 1

3.12. Äàíî N (1≤N≤100) пронумерованных объектов, которые охраняются и соединены K переходами (1<K<4950). С любого объекта на любой другой можно пройти переходами. Идти по каждому переходу можно в обе стороны. Необходимо разместить пост милиции так, чтобы минимизировать расстояние от поста до самого дальнего объекта. Пост должен находиться на одном из объектов. Напишите программу, которая находит оптимальное место для поста.

Входные данные: в первой строке натуральные числа N и K. В следующих K строках расположены по три натуральных числа F, T, S (объекты с номерами F и T соединены переходом длиной S метров, 1<S<10000; между F и T может быть не более одного прямого перехода).

Выходные данные: в одной строке 2 числа – D, L (расстояние до самого удаленного объекта равно D, пост расположен на объекте L). Если оптимальных мест расположения несколько, выведите их все в порядке возрастания номеров.

Пример входных данных

3 2

1 2 100

1 3 200

Пример выходных данных

200 1

3.13. «Вавилонская башня». У вавилонян было n типов блоков и неограниченное количество блоков каждого типа. Каждый блок k-го типа имел форму прямоугольного параллелепипеда со сторонами (xk, yk, zk). Блоки можно было поворачивать так, чтобы стороны основания определялись любой парой чисел из указанной для каждого блока тройки размеров. Вавилоняне хотели построить самую высокую башню, только ставя блоки один на другой. Для устойчивости башни необходимо, чтобы длина и ширина нижнего блока были соответственно строго больше длины и ширины верхнего блока. Это означает, что, например, два одинаковых куба нельзя ставить один на другой. Ваша задача – написать программу, которая по заданным описаниям блоков определяет высоту самой большой Вавилонской башни, которую можно было построить, используя этот набор блоков.

Входные и выходные данные

Входной файл будет содержать одно или более описаний набора блоков. Первая строка каждого описания содержит n – число, определяющее количество типов блоков (n≤30). Каждая из следующих n строк содержит 3 числа – длины сторон блоков. Входной файл окан- чивается значением 0 для числа n. Для каждого набора блоков выведите одну строку, содержащую номер описания набора блоков и максимальную высоту башни для этого набора в виде:

«Case case: maximum height = height»

Пример входных данных	Пример выходных данных
1	Case 1: maximum height = 40
10 20 30	Case 2: maximum height = 21
2	Case 3: maximum height = 28
6 8 10	Case 4: maximum height = 342

5 5 5

7

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

5

31 41 59

26 53 58

97 93 23

84 62 64

33 83 27

0

20

21

4.ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

ÈЕЕ ПРИЛОЖЕНИЯ

4.1.Найти максимальный поток f* от v1 ê v7 в графе, изображенном на рисунке для задачи 4.2, где пропускные способности дуг указаны стоящими около них числами.

4.2.Пусть в графе, изображенном на рисунке, потоки по дугам

(v2, v3), (v5, v4) è (v2, v3) ограничены снизу значениями d23=4, d54=7, d25=3. Найти максимальный поток от v1 ê v7 или показать, что такой

поток не существует.

	9	V2			6					V3	3
					4		7
	5					V4		5
					8
V1													V7
							4
	8
						2						14
										V6
		V5

4.3.Предложить метод решения задачи о максимальном потоке в

сети G=(V, E, c), имеющей несколько источников s1, …, sk и несколько стоков t1, …, tr.

4.4.С n платформ, находящихся в море, к конечной станции нефтепровода T, находящейся на берегу, перекачивается неочищенная нефть. Известна производительность скважин для каждой платфор-

ìû pi (i=1, …, n). Максимальный объем нефти, который может быть перекачан с платформы i к платформе j и к станции T, задается мат-

рицей Сij, i=1, …, n, j=1, …, n+1. Написать программу, определяющую максимально возможный объем нефти, который может быть перекачан со всех платформ на станцию.

4.5.C 7 платформ, находящихся в море, к конечной станции нефтепровода T, находящейся на берегу, перекачивается неочищенная нефть. Производительность скважин для каждой платформы различ- ная. Управляющий конечной станцией нефтепровода дает указание установить максимально допустимый поток нефти на каждой линии, ведущей к станции. Максимальный объем (в баррелях) неочищенной нефти, который может быть перекачан с платформы i к платформе j и к станции T, задается матрицей (элементы которой следует ум-

ножить на 105). Найти максимальный поток нефти, который можно перекачать с платформы 1 к конечной станции.

Èç/â

1

2

3

4

5

6

7

T

1

–

6

4

1

–

–

–

–

2

–

–

–

–

4

–

–

–

3

–

–

–

1

1

3

–

–

4

–

–

–

–

–

4

–

–

5

–

–

–

–

–

–

4

–

6

–

–

–

–

–

–

9

4

7

–

–

–

–

–

–

–

6

4.6. Пять предприятий выпускают товары народного потребления. Известны мощности предприятий по выпуску товаров (единиц в день). По системе автодорог, связывающих предприятия и базу, эти товары попадают на базу. Максимальное количество товаров (единиц в день), которые могут быть перевезены от i-го к j-му предприятию, известно и задано в таблице. Числа в скобках рядом с номером предприятия указывают мощность предприятия (единиц в день). Элементы матрицы, задающие количество единиц товаров, следует умножить на 103.

Îò/äî	1	2	3	4	5	Áàçà
1 (6)	–	2	–	–	5	–
2 (3)	–	–	–	6	–	–
3 (5)	–	–	–	6	5	–
4 (2)	–	–	–	–	–	12
5 (4)	–	–	–	–	–	12

4.7. На железной дороге между узловыми станциями d0 è dn расположены промежуточные станции d1 … dn-1. Число товарных поездов, которые могут пройти по линиям от di ê dj (и обратно от dj ê di) за один день ограничено и задается таблицей Сij (i=0, …, n, j=0, …, n). Найти максимальное за один день число поездов, которые могут прой-

òè îò d0 ê dn.

Решить задачу для следующих численных данных: d0=0, dn=11.

22

23

	0	1	2	3	4	5	6	7	8	9	10	11
0		18	11		6
1	0			8	2		7
2	0				4	6
3		3					8
4	0	4	2			0	2	7		2
5			3		5			1
6		2		0	2				4	7
7					4	1				11	3
8							3			7		21
9					2		0	4	16		7	5
10								0		6		3
11									0	0	0

4.8. По компьютерной сети, состоящей из компьютеров C1, ..., Cn, требуется переслать данные с компьютера C1 íà Cn. Известны максимальные пропускные способности Dij КБайт/с для всех имеющихся каналов связи между компьютерами и конфигурация сети. Каким будет распределение потока данных по каналам сети при максимально возможной скорости пересылки информации с C1 íà Cn. Решить задачу для сети из десяти компьютеров, пропускные способности каналов связи которой представлены матрицей пропускных способностей. Есть ли в этой сети компьютеры и каналы, которые можно исключить из сети?

1		2	3	4	5	6	7	8	9	10
1		7	4	6
2					5		5
3						5
4						6	6
5								6		6
6							6		5
7										7
8										6
9										5
10

4.9. В некоторой стране протянута сеть железных дорог. Требуется наладить сообщение между двумя различными городами A и B, пустив наибольшее возможное число поездов от A до B. Из-за конструктивных особенностей поездов, нарушений расписания и прочих объективных причин необходимо, чтобы никакие два поезда не проезжали через один город, за исключением, конечно, городов A и B.

Входные данные

В первой строке входного файла записано целое число М – коли- чество городов в стране (2≤Ì≤25) и номера городов A и B (города нумеруются числами от 1 до М). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, т. е. ведущими из первого города пары во второй, но не наоборот.

Выходные данные

Выведите в первую строку выходного файла целое число K – максимальное количество поездов, которое можно пропустить из A в B. Далее выведите K маршрутов поездов по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.

Пример входного файла

5 2 4

21

23

1 3

3 1

1 4

3 4

3 5

Пример выходного файла

2

2 1 4

2 3 4

4.10. На железной дороге между узловыми станциями d0 è dn расположены промежуточные станции d1 … dn-1. Движение пассажирских поездов из d0 â dn происходит в строгом соответствии с заданным расписанием. На запасных путях промежуточной станции dj

24

25

может одновременно находиться не более ci товарных поездов. Путь между станциями di è di+1 занимает для товарного поезда ti минут (все ti кратны 5). Товарные поезда могут отправляться со станций, начи- ная с 0 часов с интервалом 5 минут. Ни с какой станции не могут одновременно отправиться более одного товарного поезда. Товарный поезд может отправиться в данный момент со станции dj лишь при условии, что он не помешает движению пассажирских поездов до момента, пока не достигнет станции, запасные пути которой заполнены не полностью.

Необходимо составить расписание товарных поездов так, чтобы общее число товарных поездов, вышедших в течение данных суток из do è dn, было максимальным.

4.11. В заданной сети из источника s в сток t надо доставить 3 единицы продукта. Построить поток минимальной стоимости. На рисунке для каждой дуги даны три числа: верхнее ограничение по пропускной способности, нижнее ограничение по пропускной способности, стоимость единицы потока по дуге.

	2
2,0,2	1,0,1			4,0,3
s=1			1,0,1	4=t
4,0,5				2,1,6

3

4.12.Найти поток от s к t минимальной стоимости со значением

20.Возле соответствующей дуги на рисунке указаны пропускная способность и стоимость.

2					1 7,25	3
1 6,7					1 6,10	2 2,5
1 8,4					1 2,6		1 6,12		7 = t
						5
s= 1 1 1,13
		4		1 9,5	1 0,3	5 ,7
1 3,28				6

26

4.13. Найти максимальный поток с минимальной стоимостью от узла 1 до узла 8 в графе на рисунке, если первое число у дуги равно ее пропускной способности, а второе – стоимости.

1	2 ,2 5				2					4 ,6		3
	8 ,6		9 ,7				2 ,1 1				9 ,8
1 6 ,5														7 ,1 0
					3 ,1 0
			5							7
			3 ,8				8 ,9
	1 0 ,4									8 ,1 2
4						6							8
	4 ,3									6 ,4

4.14. Предприятия, производящие мебель, имеют четыре оптовые базы, с которых комплекты мебели распределяются по пяти различ- ным магазинам. Найти минимальную по стоимости схему транспортировки комплектов мебели при условии, что базы располагают 100, 200, 300 и 400 комплектами, а магазинам требуется 200, 250, 300, 100 и 150 комплектов соответственно. Затраты на транспортировку (в тыс.руб.) задаются матрицей стоимостей.

				Магазины
		À	Â	Ñ	Ä	Å
	1	5	7	3	15	9
Оптовые	2	6	2	8	5	6
áàçû	3	3	9	8	2	2
	4	7	6	8	7	4

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

27

			Завод			Предложение,ò
Шахта	1	2	3	4	5
1	10	9	8	9	7	500
2	4	8	12	7	9	900
3	6	3	4	2	8	700
4	7	6	5	4	3	600
Спрос	400	700	400	500	700

4.16. При добыче урана приблизительно 0,711 % его составляет U-235, а остальную часть – U-238. С рудника уран перевозится на три предприятия, где он обогащается, т. е. процент содержания U-235 возрастает, в результате чего образуется высокорадиоактивное вещество шестифтористый уран. Затем его доставляют десяти предприятиям, на которых оно должно быть переработано в топливо для ядерных реакторов. Правительство, исходя из соображений безопасности, разработало десятибалльную шкалу, характеризующую степень риска при транспортировке шестифтористого урана по различ- ным маршрутам (число 10 соответствует наибольшему риску). Соответствующие значения, а также величины спроса и предложения приводятся в таблице. Найти схему транспортировки, при которой общий риск минимален.

					Предприятия
	1	2	3	4	5	6	7	8	9	10
À	9	8	7	4	6	3	8	6	5	2
Â	1	7	9	10	8	3	6	7	5	4
Ñ	3	3	5	7	7	8	9	1	2	3

А, В, С – обогатительные фабрики.

Спрос (в фунтах) 100 100 300 150 200 90 110 50 50 100. Предложение (в фунтах) 600 400 250.

4.17. Задача о поставщике. Владелец предприятия должен иметь di единиц оборудования на каждый из n последовательных дней (i=1, …, n). Он может покупать новое оборудование или отдавать оборудование в ремонт, причем имеется два вида обслуживания: обычное (в местной мастерской) и срочное (в центральной). Оборудование, отданное в местную мастерскую, бывает готово через m дней, а обору-

дование, отданное в центральную мастерскую – через k дней (0<k<m). Новое оборудование, покупаемое в магазине, стоит a рублей за каждую единицу. Срочный ремонт обходится c рублей за каждую единицу, обычный ремонт – b рублей за каждую единицу (c>b).

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

n=4, k=1, m=2,

d1=100, d2=180, d3=70, d4=210, a=2000 ðóá., b=300 ðóá., c=600 ðóá.

5. ПАРОСОЧЕТАНИЯ В ДВУДОЛЬНЫХ ГРАФАХ

5.1. Паросочетание называется максимальным, если оно не содержится ни в каком другом паросочетании. Ясно, что всякое наибольшее (по числу ребер) паросочетание является максимальным. Приведите пример двудольного графа и максимального паросочетания в нем, не являющегося наибольшим.

5.2. Двудольный граф G=(X, Y, E) называется выпуклым на X, если множество X можно упорядочить в последовательность x1, …, xp так, чтобы для каждого yОY множество A(y)={xОX: {x, y}ОE} образовывало отрезок вида {xp(y), xp(y)+1, …, xk(y)}. Аналогично определяется выпуклость на Y. Предложить эффективный алгоритм построения наибольшего паросочетания в выпуклом на X двудольном графе.

5.3. Доказать, что наибольшее паросочетание в двудольном графе G=(X, Y, E) выпуклом на X можно построить за время O(|X|+|Y|log|Y|) и за время O(|X|+|Y|), если G – выпуклый как на X, так и на Y.

5.4. В школе работают k учителей x1, …, xk и имеется m классов y1, …, ym. Известно, что учитель xi должен провести в классе yj cij уроков. Необходимо составить расписание таким образом, чтобы время проведения занятий было наименьшим из возможных.

5.5. Пусть {A1, …, An} – произвольная последовательность множеств (необязательно непересекающихся и необязательно различных).

Системой различных представителей для семейства {A1, …, An} называется произвольная последовательность элементов {a1, …, an} такая, что aiÎ Ai äëÿ i=1, …, n è ai¹aj ïðè i¹j.

28

29

Найти систему различных представителей для заданной последовательности множеств, если она существует.

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

5.7.Вершинным покрытием графа называется множество вершин V* такое, что каждое ребро графа инцидентно хотя бы одной вершине v из V*. Наименьшее по мощности вершинное покрытие называется наименьшим.

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

5.8.Куплено N открыток и M конвертов. К сожалению, конверты

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

Входные данные

В первой строке входного файла записаны числа M и N (0≤M, N≤100). Далее записаны высота и ширина каждого из M конвертов, затем высота и ширина каждой из N открыток. Размеры конвертов и открыток являются натуральными числами, не превосходящими 32767, и разделяются пробелами и/или символами перевода строки.

Выходные данные

Выведите в выходной файл целое число K – максимальное число открыток, которые можно разложить по конвертам. Далее выведите K пар целых чисел, означающих номер открытки и номер конверта, в который ее необходимо положить.

Пример входного файла

4 4

3 3 141 282 282 141 200 100

3 1 140 280 141 282 201 1

Пример выходного файла

4

1 1 2 3 3 2 4 4

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

Входные данные

В первой строке входного файла записано количество вершин графа N (1≤N≤25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.

Выходные данные

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

Пример входного файла

4

12

13

2 3

2 4

Пример выходного файла

2

1 2 4

3

5.10. Доктор Борменталь часто гуляет с собакой Шариком. Доктор идет с постоянной скоростью, его маршрут является ломаной линией (возможно, самопересекающейся), вершины которой заданы N парами целых чисел (Xi, Yi) – их декартовыми координатами.

Шарик бежит своим путем, но всегда встречается с хозяином в указанных N точках. Собака начинает свое путешествие одновременно с Борменталем в точке (X1, Y1) и заканчивает его также одновременно с доктором в точке (XN, YN).

Шарик может передвигаться со скоростью не выше, чем удвоенная скорость его хозяина. Пока Борменталь двигается по прямолинейному участку пути от одной точки до другой, жизнерадостная собака исследует деревья, кусты, пеньки и прочего рода интересные места местного ландшафта, которые обозначены M парами целых чисел (X’j, Y’j). Однако между тем как оставить своего хозяина в точ-

êå (Xi, Yi) (ãäå 1≤i≤N) и встретить его снова в точке (Xi+1, Yi+1), собака может посетить не более одного интересного места.

30

31

Ваша задача найти маршрут собаки, который удовлетворяет указанным выше требованиям и дает возможность посетить как можно больше интересных мест. Ответ должен быть представлен как ломаная линия, представляющая маршрут Шарика. Вершинами этого маршрута должны быть все точки (Xi, Yi) и максимальное число интересных мест (X’j, Y’j). Последние могут посещаться (т. е. участвовать в маршруте) не более одного раза. Пример маршрута Борменталя (сплошная линия), множество интересных мест (точки) и один из лучших маршрутов Шарика (пунктирная линия) представлены на следующем рисунке:

	Y
	2
4	1
	3
	X

Входные данные

Первая строка входного файла содержит два целых числа N и M, разделенных пробелом (2≤N≤100, 0≤M≤100). Вторая строка содержит N пар целых чисел X1, Y1, ..., XN, YN, разделенных пробелами, эти числа представляют маршрут Борменталя. Третья строка содержит M пар целых чисел X’1, Y’1, …, X’M, Y’M, разделенных пробелами, эти числа представляют интересные места.

Выходные данные

Первая строка выходного файла должна содержать единственное целое число K – число вершин лучшего маршрута собаки.

Вторая строка должна содержать K пар координат X’’1, Y’’1, …, X’’K, Y’’K, разделенных пробелами и представляющих этот маршрут. Если существует несколько таких маршрутов, можете указать любой из них.

Пример входного файла

4 5

1 4 5 7 5 2 –2 4 –4 –2 3 9 1 2 –1 3 8 –3

Пример выходного файла

6 1 4 3 9 5 7 5 2 1 2 –2 4

5.11. Задача об устойчивом бракосочетании. Пусть B – множество из n юношей, а G – множество из n девушек. Каждый юноша оценивает девушек числами от 1 до n, давая разным девушкам разные оценки, и каждая из девушек оценивает аналогично юношей числами от 1 до n. Паросочетанием называется взаимно однозначное соответствие между юношами и девушками. Паросочетание устой- чиво, если для любых двух юношей b1 è b2 и соответствующих им в этом паросочетании девушек g1 è g2 выполняются следующие два условия:

ëèáî b1 оценивает g1 âûøå, ÷åì g2 , ëèáî g2 оценивает b2 âûøå,

÷åì b1;

ëèáî b2 оценивает g2 âûøå, ÷åì g1, ëèáî g1 оценивает b1 âûøå,

÷åì b2.

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

Входные данные

Первая строка входного файла содержит целое число N (1≤N≤200). В строках с номерами от 2 до N+1 находятся наборы из N чисел, которыми юноши с номерами от 1 до N оценивают девушек. В строках с номерами от N+2 до 2N+1 находятся наборы из N чисел, которыми девушки оценивают юношей. Числа в наборах разделяются пробелами.

Выходные данные

В выходной файл выведите номера девушек, соответствующих номерам юношей от 1 до N по порядку. Числа должны быть разделены пробелами и/или символами перевода строки.

32

33

Пример входного файла

3

1 2 3

2 3 1

1 2 3

1 2 3

2 3 1

3 1 2

Пример выходного файла

3 2 1

5.12.Подмножество X’ множества X в двудольном графе G=(X, Y, E) называется Y-доминирующим, если каждой вершине y из Y смежна хотя бы одна вершина x из X’.

1.Докажите, что задача построения минимального по числу элементов Y-доминирующего множества NP-полна.

2.Предложите эффективный алгоритм построения минимального по числу элементов Y-доминирующего множества в Y-выпуклом двудольном графе.

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

1.Построить наибольшее паросочетание М.

2.Если все вершины графа М-насыщены, то СТОП (М – реберное покрытие).

3.Иначе, выбрать произвольную М-свободную вершину и любое ребро е, ей инцидентное, добавить е к М и вернуться на 2.

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

5.14.Дан взвешенный двудольный граф G=(X, Y, E, c), |X|=|Y|=n. Найти полное паросочетание минимального веса. Решить задачу для следующих графов, заданных матрицами весов:

1	9	8	6
14	3	13	7
12	13	15	10
3	14	12	18

8	5	∞	7	6	9
6	3	9	1	∞	7
5	∞	3	6	8	8
9	1	8	∞	5	4
1	2	1	∞	2	3
∞	∞	3	5	3	10

5.15. Имеется m видов оборудования и n работ (m³n). Известно время выполнения j-й работы на i-м оборудовании Cij (i=1, …, m, j=1, …, n). Распределить работы так, чтобы суммарное время выполнения работ было наименьшим. На данном оборудовании можно выполнять только одну работу. Возможно, m>n.

3	3	2	0	8
10	1	8	9	1
10	3	6	8	4
7	8	4	6	9
1	9	4	3	8
9	2	3	6	1

5.16. Имеется n работников и n работ. Cij – прибыль от выполнения i-м работником j-й работы. Распределить работы между сотрудниками так, чтобы общая прибыль была максимальной. Каждый сотрудник должен выполнять определенный вид работы.

6	2	2	8	8	9
4	1	9	3	5	1
6	0	5	9	0	6
3	3	8	9	11	4
7	4	0	2	2	1
8	3	8	2	9	6

5.17. Имеется m предприятий и n магазинов (m£n). Известно время доставки продукции i-го предприятия j-му магазину Cij (i=1, …, m, j=1, …, n). Распределить доставку продукции от предприятия в магазины так, чтобы суммарное время доставки было наименьшим.

34

35

Данное предприятие может работать только с определенным магазином. Возможно, m<n.

2	3	1	∞	7	10	5
7	∞	6	8	5	5	7
5	6	9	7	∞	3	4
9	5	10	2	10	∞	∞
8	5	8	1	10	10	10

5.18. Задача размещения производства. Промышленная корпорация планирует выпуск n новых видов продукции. Производство может быть организовано на m принадлежащих корпорации предприятиях (n<m), на каждом не более одного вида продукции. Для каждого i-го вида продукции и j-го предприятия известны:

pij – производственные затраты на единицу продукции; qij – затраты сбыта единицы продукции;

si – продажная стоимость единицы i-й продукции; vi – объем выпуска i-й продукции.

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

Решите следующие конкретные задачи:

1. Корпорация имеет четыре предприятия и планирует выпуск трех новых видов продукции.

Производственные затраты на единицу продукции:

		Предприятия
Виды продукции	1	2	3	4
1	20	25	15	10
2	15	30	20	5
3	25	20	10	15

Затраты сбыта на единицу продукции:

	Предприятия
Виды продукции
1	2	3	4

1			10	5	5	15
2			5	25	15	10
3			15	20	25	30
Âèä		Стоимость единицы				Объем выпуска
продукции		продукции				продукции
1		45				3000
2		55				4000
3		80				6000

2. Компания разрабатывает план выпуска трех новых видов продукции. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукции – по одному виду на одно предприятие. Указаны издержки производства и сбыта продукции, соответствующие каждой паре «вид продукции – предприятие».

Издержки производства единицы продукции (дол.):

			Предприятия
Виды продукции	1	2	3	4	5
1	20	23	38	15	35
2	8	29	6	35	35
3	5	8	3	4	7

Издержки сбыта единицы продукции (дол.):

			Предприятия
Виды продукции	1	2	3	4	5
1	20	50	20	10	13
2	7	90	8	35	60
3	5	5	4	15	6

36

37

Плановый объем годового производства, который позволил бы удовлетворить спрос, и плановая стоимость единицы продукции каждого вида следующие:

Âèä	Плановая стоимость,	Плановый объем
продукции	äîëë.	производства
1	55	35 000
2	50	160 000
3	30	54 000

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

			Изделия
		1	2	3	4
	1	7	9	7	13
	2	11	5	5	9
Станки	3	5	3	3	9
	4	3	7	11	7
	5	9	5	13	9

5.20. Платы. Имеются компоненты, которые надо расположить в n ячейках на плате. Число соединений между парами компонент задается матрицей C, в которой C[i, j] – число связей между i-й и j-й компонентами. Расстояние между парами мест задается матрицей D, в которой D[k, m] – расстояние между k-й и m-й ячейками. Таким образом, в терминах общей длины использованного провода размещение i-й компоненты в k-й ячейке и j-й компоненты в m-й ячейке стоит C[i, j]D[k, m]. В каждой ячейке можно поместить только одну компоненту, и каждая компонента может находиться только в одной ячейке. Найдите размещение компонент в ячейках, минимизирующее общую длину использованного провода.

6.ЗАДАЧА КОММИВОЯЖЕРА

6.1.Приведите пример графа, в котором алгоритм «БЛИЖАЙШИЙ СОСЕД» дает решение, вес которого более чем в два раза превосходит вес оптимального.

6.2.Методом ветвей и границ решить задачу коммивояжера для матрицы весов

∞	0	90	10	30	6	54
1	∞	74	39	18	13	31
42	14	∞	33	13	25	22
36	87	77	∞	53	4	88
25	43	85	30	∞	22	54
0	85	15	43	89	∞	4
41	23	30	24	81	36	∞

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

–	20	36	9	23	19
7	–	16	1	30	30
20	13	–	35	5	0
21	16	25	–	13	18
12	46	27	48	–	5
23	5	5	9	5	–

6.4. Для изготовления изделия в механическом цехе необходимо выполнить восемь операций на станке. Эти операции могут производиться в любой последовательности. Однако время переналадки станка зависит от того, какой именно была предыдущая операция по изготовлению изделия. Длительности переналадок даны в матрице C, где C[i, j] означает время переналадки от i-й операции к j-й.

38

39