Решение задачи коммивояжера методом ветвей и границ

Контроль знаний

1. Сформулируйте транспортную задачу линейного программирования и напишите ее математическую модель.

2. Поясните теорему о существовании решения транспортной задачи.

3. Как построить транспортную задачу на рабочем листе электронной таблицы? 4. Объясните предназначение надстройки «Транспортное моделирование».

5. Перечислите алгоритмические правила решения транспортных моделей.

6. Укажите порядок заполнения окна Поиска решений для транспортного моделирования.

Лабораторная работа № 6 Тема: Дискретноепрограммирование

Цельработы:

ƒ освоить методы дискретного программирования;

ƒ выявить особенности дискретного программирования;

ƒ освоить использование Поиска решения для дискретного программирования. Времяработы: 4 часа

Задание

1. Решить задачу коммивояжера (загрузки оборудования) методом ветвей и границ; 2. Решить задачу о назначениях с помощью Поиска решения.

Имеются 5 вариантов загрузки оборудования. Известны затраты связанные с пере-наладкой оборудования Cij (от i -го варианта в j- ый).

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

Таблица 6.1 Исходные данные 1 2 3 4 5

1 ¥ 1 4 2 3 2 4 ¥ 2 3 1 3 1 4 ¥ 1 4 4 3 3 1 1 5 1 2 4 4 ¥

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

В каждой строке находим наименьший элемент hi (постоянная приведения по i -ой строке). Вычитаем hi из всех элементов i -ой строки. В полученной матрице в каждом столбце находим минимальный элемент qj (постоянная приведения по j -му столбцу). Вы-читаем qj из всех элементов j -го столбца.

h 1=1 h 2=1 h 3=1 h 4=1 h 5=1

	¥
		¥
			¥
				¥
					¥
	q 1=0	q 2=0	q 3=0	q 4=0	q 5=0

Получаем следующую результирующую матрицу, для которой суммарные издержки

составляют Н.

i

H 1 = å h + å qj = (1+1+1+1+1)+(0+0+0+0+0) = 5 i j

1 2 3 4 5

2.

¥ 0 3 1 2

1. 3 ¥ 1 2 0

0. 1.

0 3 ¥ 0 3 1. 0.

2 2 0 ¥ 0 1.

0 1 3 3 ¥

k

Для каждого элемента "0", стоявшего в i -ой строке и j -ом столбце, находим оценку D ke = P + Qe, где Pi – наименьший элемент в i -ой строке, исключая оцениваемый "0", Qj –

наименьший элемент в j -ом столбце, исключая оцениваемый "0".

Выбираем "0" с наибольшей оценкой D12 2. В качестве первой пары вариантов за-грузки выбираем переход от 1-го типа ко 2-му. Вычеркиваем из матрицы 1 строку и 2 столбец. Записываем новую матрицу, полученную после вычеркивания. Для запрета пере-хода обратно от 2-го варианта к 1-му вместо элемента С21 ставим ¥.

h 2=0 h 3=0 h 4=0 h 5=0

	¥
		¥
			¥
				¥
	q 1=0	q 3=0	q 4=0	q 5=0

Подсчитываем оценки нулевых элементов.

	¥				1.
		0.		¥		2.
			1.		¥		0.
		3.				¥

Суммарная позиция составляет Н 2 = Н 1 = 5. Вновь находим оценки "0"-вых элемен-тов. В качестве третьей пары загрузки выбираем пару 5-1, для которой D51= 3.

Вычеркиваем пятую строку и первый столбец. Записываем новую матрицу, полу-ченную после вычеркивания. Принимаем С 25 =.

			¥
	¥
		¥

h 2=1 h 3=0 h 4=0

			¥
	¥
		¥
	q 3=0	q 4=0	q 5=0

n

ï

ï

ï

å

ï

{

ï

В качестве третьей пары загрузки выбираем пару 3-4. H 3 = H 2 + 1 = 5 + 1 = 6.

		1.			¥
	¥		4.
		0.		¥		3.

Вычеркиваем третью строку и четвертый столбец. Записываем новую матрицу, по-лученную после вычеркивания. Принимаем С43=¥.

h 2=0 h 4=0

В качестве четвертой пары загрузки выбираем пару 2-3, в качестве пятой пары – па-ру 4-5. H 4 = H 3 = 6 Итак, оптимальный вариант переналадки оборудования: 1-2-3-4-5-1 и суммарные издержки: H min = H 4 = 6.

Дата добавления: 2014-11-25