Содержательная постановка задачи.

На металлообрабатывающем оборудовании необходимо обработать 6 партий деталей(Рис. 3). Переход на обработку новой партии деталей требует переналадки оборудования. Время переналадки оборудования (мин) при переходе от обработки i-й.

(i-1,6) партий деталей к обработке j-й (j-1,6) поставлена матрицей (табл.1). Найти такую последовательность запуска партий деталей в обработку, при которой затраты времени на переналадку оборудования будут минимальными.

 

Рис. 3

j i ih

Таблица 1.

 

Примечание: При решении вручную методом ветвей и границ необходимо заменить a_ij=∞ (i=1,6).

 

2.2 Построение математической модели задачи .

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

Z=0x₁₁+20x₁₂+25x₁₃+30x₁₄+15x₁₂+10x₁₆+20x₂₁+0x₂₂+30x₂₃+15x₂₄+20x₂₅+ +18₂₆+30x₃₁+25x₃₂+0x₃₃+20x₃₄+40x₃₅+30x₃₆+25x₄₁+20x₄₂+20x₄₃+0x₄₄+30x₄₅+ +15x₄₆+35x₅₁+25x₅₂+30x₅₃+24x₅₄+0x₅₅+20x₅₆+15x₆₁+20x₆₂+30x₆₃+20x₆₄+18x₆₅+ +0x₆₆ min

 

 

Ограничения имеют вид:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₂+x₁₆=1,

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅+x₂₆=1,

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅+x₃₆=1,

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅+x₄₆=1,

x₅₁+x₅₂+x₅₃+x₅₄+x₅₅+x₅₆=1,

x₁₁+x₂₁+x₃₁+x₄₁+x₅₁+x₆₁=1,

x₁₂+x₂₂+x₃₂+x₄₂+x₅₂+x₆₂=1,

x₁₃+x₂₃+x₃₃+x₄₃+x₅₃+x₆₃=1,

x₁₄+x₂₄+x₃₄+x₄₄+x₅₄+x₆₄=1,

x₁₅+x₂₅+x₃₅+x₄₅+x₅₅+x₆₅=1,

x₁₆+x₂₆+x₃₆+x₄₆+x₅₆+x₆₆=1,

 

U₂-U₃+5*x₂₃ 4,

U₂-U₄+5*x₂₄ 4,

U₂-U₅+5*x₂₅ 4,

 

U₂-U₆+5*x₂₆ 4,

U₃-U₄+5*x₃₄ 4,

U₃-U₅+5*x₃₅ 4,

U₃-U₆+5*x₃₆ 4,

U₄-U₅+5*x₄₅ 4,

U₄-U₆+5*x₄₆ 4,

U₅-U₆+5*x₅₆ 4,

U₆-U₂+5*x₆₂ 4,

U₆-U₃+5*x₆₃ 4,

U₆-U₄+5*x₆₄ 4,

U₆-U₅+5*x₆₅ 4.

 

2.3 Решение задачи вручную.

Время переналадки оборудования при переходе от обработки i-ой партии деталей к обработке j-ой задано с помощью матрицы .

Находим минимум (A_i) в 1-ой строке (это 10) и вычитаем его из всех элементов 1-ой строки. Аналогичному действию подвергаются все оставшиеся строки. В результате получим матрицу (Таб. 2).

 

 

Таблица 2

							Ai

 

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

 

Таблица 3

Bj

 

Находим сумму констант приведения (минимумы в строках и столбцах). =10+15+20++15+20+15+5+5+3=108.

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

Для элемента (1, 6) это 2+0=2, для элемента (2, 4) это 2+0=2, для элемента (3, 2) это 0, для (3, 4) 0, для (4, 2) 0, для (4, 3) 5, для (4, 6) 0, для (5, 2) 0, для (5, 6) 0, для (6, 1) 5, для (6, 2) 0, для (6, 5) 2. Полученные суммы укажем в качестве верхних индексов для соответствующих нулей (таб. 4).

 

Таблица 4

							H(1)=10+15+20++15+20+ 15+5+5+3=
						02
				02
		00		00
		00	05			00
		00				00
	05	00			02

 

Для элемента (6, 1) эта сумма наибольшая. Поэтому все множество маршрутов распадается на два класса: {()} (не содержат дугу (6, 1)) и {(6, 1)} (содержат дугу (6, 1)).

Рассмотрим множество {()}. Исключение дуги (6, 1) проводится с помощью замены элемента (6, 1) на (таб. 5):

Таблица 5

							Ai	H()=5+ =113
Bj

 

В полученной матрице нужно определить сумму констант приведения (таб. 6).

Таблица 6

							Ai
Bj

 

 

Таблица 7

							H(6,1)=2+108=110
					05
				02
		00		00
		00	05			00
		00				00
	05	00			00

 

 

Рассмотрим множество {(6, 1)}. Включение дуги (6, 1) проводится с помощью исключения 6-ой строки и 1-го столбца; элемент (1, 5) заменяем на (исключаем возможность образования негамильтонова цикла). Определяем сумму констант приведения. Получим матрицу (таб. 8, 9):

 

Таблица 8

						Ai

 

Таблица 9

						H()=110+2+3=115
Bj

 

Так как H(6, 1) < H(), то в дальнейшем ветвим множество {(6, 1)}. Определим дугу, исключение которой максимально увеличило бы полученную оценку H{(6, 1)}=110. С этой цель заменяем поочередно каждый из нулей на и вычисляем сумму наименьших элементов в строке и столбце, содержащих этот новый элемент . Полученные суммы укажем в качестве верхних индексов для соответствующих нулей (таб. 10).

 

Таблица 10

					Ai	H (1,5)=110
			03
	00		00
	00	05		00
	05			00
Bj

 

Для элемента (5, 2) эта сумма наибольшая. Поэтому все множество маршрутов распадается на два класса: {(1, 5), ()}.

Рассмотрим {(1, 5), ()}. Исключение дуги (5, 2) проводится с помощью замены элемента (5, 2) на (таб. 11):

 

Таблица 11

					Ai	H()=110+4=
Bj

 

Нижняя граница {(1, 5), ()}=114. Заменяем поочередно каждый из нулей на и вычисляем сумму наименьших элементов в строке и столбце, содержащих этот новый элемент . Полученные суммы укажем в качестве верхних индексов для соответствующих нулей (таб. 12).

Таблица 12

					Ai	H(5,2)=110
			03
	00		00
	00	05		03
	04
Bj

 

 

Рассмотрим множество {(1, 5), (5, 2)}. Включение дуги (5, 2) проводится с помощью исключения 5-ой строки и 2-го столбца; элемент (4, 3) заменяется на (таб. 13).

Таблица 13

				Ai
Bj

 

Рассмотрим множество {(1, 5), (5, 2), ()}. Исключение дуги (4, 3) проводится с помощью замены элемента (4, 3) на (таб. 14, 15).

Таблица 14

				H()=110+5=115
	00	00
		010
			03

 

Таблица 15

				Ai
Bj

 

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

Таблица 16

				H(4,3)=110+5= 115
		03
			03

 

 

Рассмотрим {(1, 5), (5, 2), (4, 3), ()}. Включение дуги (4, 3) проводится с помощью исключения 4-ой строки и 3-го столбца; элемент (2, 4) заменяется на (исключаем возможность образования негамильтонова цикла). В полученной матрице нужно определить сумму констант приведения (таб. 17).

Таблица 17

			Ai

 

Оценка 115, полученная на предыдущем шаге, не меняется. Это минимальная длина маршрута.

Таблица 18

 

В этой матрице надо так выбрать нули, чтобы в каждой строке и каждом столбце был ровно один отмеченный нуль. Это элементы (2, 6) и (3, 6).

Таким образом, получили такую последовательность запуска партий деталей: 1-5-3-2-4-6-1 (Рис. 4) и минимальное время на переналадку оборудования T_min=115.

 

4

5 3

 

 

Рис. 4

 

2.4 Решение задачи в Excel

Вид электронной таблицы, созданной для решения задачи, представлен на рис. 5. Значения переменных x_ij располагаются в блоке B7:G12. В данном блоке ячейки, расположенные по диагонали обнулены (пункт назначения не может быть одновременно пунктом прибытия) и выделены, для удобства задания ограничений. Дано время переналадки оборудования (блок B18:G23). Для вычислений необходимо задать размерность задачи n (количество партий деталей)- ячейка J17.

Целевая функция расположена в ячейке H14. Ограничения находятся в блоках B13:G13 (коммивояжер въезжает один раз в каждый город) и H7:H12 (коммивояжер выезжает из каждого города один раз) (см. рис. 5 и 6). Вид электронной таблицы в режиме отображения формул представлен на рис. 41. В задаче коммивояжера есть ряд специфических ограничений по дополнительным переменным u_i (см. мат модель). Формулы этих ограничений находятся в блоке ячеек B27:G32. Значения самих переменных располагаются в блоке B14:G14.

 

 

Рис. 5

На рис. 7 представлена запись условий задачи в окне "Поиск решения". Как известно, дополнительные переменные не относятся к целевой функции, но они, также как и x_ij, являются изменяемыми, поэтому адреса содержащих их ячеек должны быть введены в поле Изменяя ячейки одновременно с адресами переменных целевой функции.

Операцию ввода удобно проводить с помощью мыши. Необходимо установить курсор ввода в поле Изменяя ячейки, затем выделить мышью блок ячеек переменных целевой функции, нажать <Ctrl> и, удерживая эту клавишу, выделить мышью блок ячеек рабочего листа, отведенный для переменных u_i. В поле ввода адреса блоков отделяются ";" (см. рис. 7).

Рис. 6

Перечислим ограничения, которых не видно на рис. 7: $C$8=0; $D$9=0; $E$10=0; $F$11=0; $G$12; $H$7:$H$12=1.

Рис. 7

Первая запись в группе Ограничения представляет собой совокупность ограничений по дополнительным переменным u_i. Каждая ячейка блока в левой части неравенства содержит формулу одного ограничения (см. рис. 6 и мат. модель), правую часть представляет одно значение, равное n-2, содержащееся в J18. Такая запись означает, что каждая ячейка блока $B$27:$G$32 меньше либо равна 4 (6-2=4).

В поиске решения нельзя явно задать ограничение ij. Исходя из смысла переменных x_ij, можно предположить, что значения тех x_ij, для которых i=j (расположенных по диагонали в блоке переменных), всегда должны быть равны 0 и ввести соответствующие ограничения. В группе Ограничения таких ограничений четыре: $B$7=0, $C$8=0, $D$9=0, $E$10=0, $F$11=0, $G$12=0.

 

По результатам поиска решения найден ответ задачи: (см. рис. 7).

 

Рис. 8

 

2.5 Описание работы программы

 

Программа реализована в среде Borland Pascal 7.0. Она включает несколько процедур и функций по обработке матриц согласно алгоритму метода ветвей и границ:

1) function in0 - функция получает нули в строках и столбцах матрицы и выдает сумму вычтенных ей элементов;

2) procedure choosezero - выбор нуля, по которому будем ветвиться;

3) procedure addedge - добавление ребра i к частичному решению;

4) procedure process - обход узла;

5) procedure readdata – чтение данных из текстового файла input.txt;

6) procedure out – вывод результатов на экране

В главной процедуре вызываются только две: readdata - чтение из файла и process - вывод на экран.

От пользователя требуется создать файл с исходными данными input.txt и запустить программу в среде Borland Pascal 7.0. Конечный результат представляет собой оптимальный маршрут и длину пути, выводимый на экране компьютера.

 

Текст программы

 

program commivoyagerMVG;

const

Max=20; {максимальное количество элементов матрицы}

Infty=30000; {бесконечность, которая ставится в клетки}

ToInfty=20000; {если такое число появилось в клетке, то это бесконечность}

 

MaxSpace=65535; {максимальное пространство Pascal выделяемое для матрицы}

type

tmatrix=record {подматрица исходной}

size:byte; {размер}

endi,endj,endirev,endjrev:array [1..Max] of byte; {объявление ограничивающей матрицы}

database:array [1..Max,1..Max] of word;

end;

pmatrix=^tmatrix; {указатель на подматрицу}

tperm=record

size:byte;

dir,rev:array [1..Max] of 0..Max;

end;

pperm=^tperm;

task=record

mas:pmatrix;

solv:pperm; {перестановка}

est,got:word;

end;

var

bestresult:word; {лучший результат}

bsolv:pperm; {лучшая перестановка}

main:task; {основная задача}

function in0(var mas:tmatrix):word; {функция получает нули в строках и}

 

{ столбцах матрицы и выдает сумму вычтенных ей элементов}

Var

i,j:byte;

m,res:word;

begin

res:=0;

with mas do

begin

for i:=1 to size do

begin

m:=MaxSpace;

for j:=1 to size do

if database[i,j]<=m then

m:=database[i,j];

for j:=1 to size do

dec(database[i,j],m);

inc(res,m);

end;

for j:=1 to size do

begin

m:=MaxSpace;

for i:=1 to size do

if database[i,j]<=m then

m:=database[i,j];

for i:=1 to size do

 

dec(database[i,j],m);

inc(res,m);

end;

end;

in0:=res;

end;

procedure choosezero(const mas:tmatrix;var im,jm:byte);

var {выбор нуля, по которому будем ветвиться}

i,j,k:byte;

m,m1:word;

begin

m:=0;

im:=0;

jm:=0;

with mas do

begin

for i:=1 to size do

begin

for j:=1 to size do

if database[i,j]=0 then break;

m1:=MaxSpace;

for k:=1 to size do

if (database[i,k]<=m1) and (j<>k) then

m1:=database[i,k];

if m1>=m then

 

begin

m:=m1;

im:=i;

jm:=j;

end;

end;

end;

end;

procedure addedge(p:pperm;i,ip:byte;var res:pperm);

begin {добавление ребра i->ip к частичному решению}

new(res);

res^:=p^;

res^.dir[i]:=ip;

res^.rev[ip]:=i;

end;

procedure process(var n:task); {обход узла}

var

i,j,k,l,i1,j1:byte;

n1,n2:task;

first:boolean;

los:word; {потери на данном шаге}

begin

with n do

begin

if mas^.size=1 then {если осталась матрица 1х1 (в ней всегда 0)}

 

begin

if bestresult>=got then

begin

bestresult:=got;

if bsolv<>nil then dispose(bsolv);

with n.mas^ do

addedge(n.solv,endi[1],endj[1],bsolv);

end

end

else

begin

if est<bestresult then {если текущая оценка меньше лучшего результата}

begin

choosezero(mas^,i,j);

new(n1.mas); {составляем матрицу с вычеркнутыми строкой и столбцом}

n1.mas^.size:=n.mas^.size-1;

fillchar(n1.mas^.endi,sizeof(n1.mas^.endi),0);

fillchar(n1.mas^.endj,sizeof(n1.mas^.endj),0);

fillchar(n1.mas^.endirev,sizeof(n1.mas^.endirev),0);

fillchar(n1.mas^.endjrev,sizeof(n1.mas^.endjrev),0);

i1:=0;

first:=true;

for k:=1 to n.mas^.size do

if (k<>i) then

 

begin

inc(i1);

n1.mas^.endi[i1]:=n.mas^.endi[k];

n1.mas^.endirev[n.mas^.endi[k]]:=i1;

j1:=0;

for l:=1 to n.mas^.size do

if (l<>j) then

begin

inc(j1);

if first then

begin

n1.mas^.endj[j1]:=n.mas^.endj[l];

n1.mas^.endjrev[n.mas^.endj[l]]:=j1;

end;

n1.mas^.database[i1,j1]:=n.mas^.database[k,l];

end;

first:=false;

end;

with n.mas^ do

begin

k:=endi[i];

l:=endj[j];

end;

addedge(n.solv,k,l,n1.solv); {новое частичное решение}

if n1.mas^.size>1 then {здесь ищем начало и конец участка пути}

 

begin {и запрещаем замыкать его, если, конечно,}

with n1.solv^ do {не получится полный цикл}

begin

i1:=k;

while rev[i1]>0 do

i1:=rev[i1];

j1:=l;

while dir[j1]>0 do

j1:=dir[j1];

end;

with n1.mas^ do

if (endirev[j1]>0) and (endjrev[i1]>0) then

database[endirev[j1],endjrev[i1]]:=Infty;

end;

los:=in0(n1.mas^);

if los<ToInfty then

begin

n1.est:=n.est+los; {посчитали оценку для новой матрицы}

n1.got:=n.got+los;

process(n1); {и сделали шаг вперед}

end;

n.mas^.database[i,j]:=Infty; {теперь запрещаем выбор варианта i->j}

los:=in0(n.mas^);

if los<ToInfty then

begin

 

inc(n.est,los); {посчитали оценку}

inc(n.got,los);

process(n); {и сделали шаг вправо (вперед и вбок)}

end;

end;

end;

end;

end;

procedure readdata(var main:task);{производим чтение из файла}

var

i,j:byte;

begin

assign(input,'input.txt');

reset(input);

new(main.mas);

new(main.solv);

with main.mas^ do

begin

read(size);

for i:=1 to size do

begin

endi[i]:=i; {изначально все индексы указывают на себя}

endj[i]:=i;

endirev[i]:=i;

endjrev[i]:=i;

 

end;

for i:=1 to size do

for j:=1 to size do

begin

read(database[i,j]);

if i=j then

database[i,j]:=Infty; {сразу запрещаем петли}

end;

end;

with main.solv^ do

begin

size:=main.mas^.size;

fillchar(dir,sizeof(dir),0); {пустое частичное решение}

fillchar(rev,sizeof(rev),0);

end;

main.est:=in0(main.mas^);

main.got:=main.est;

bestresult:=MaxSpace;

new(bsolv);

close(input);

end;

procedure out;

var

i:byte;

begin

 

write('Полученный оптимальный вариант перестановок: ');

i:=1;

repeat

write(i,' ');

i:=bsolv^.dir[i]; {проходимся по прямой перестановке}

until i=1;

writeln;

writeln('Минимальное время на переналадку: ',bestresult);

end;

Begin

readdata(main);

process(main);

out;

end.

 

 

ЗАКЛЮЧЕНИЕ

В данной курсовой работе были рассмотрены основные теоретические вопросы по задаче коммивояжера. Приведено решение вручную задачи методом ветвей и границ (методом Литтла). Приведено решение задачи в среде MicroSoft Office Excel 2000. Изучено практическое применение задачи коммивояжера в экономике и производстве. Приведен текст программы, позволяющей решить задачу коммивояжера методом ветвей и границ, написанный на языке Turbo Pascal 7.0.

 

 

Список литературы

 

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.

2. Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.

3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2002. – 208 с.

4. Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. – М.: Издательство РДЛ, 2004. – 160 с.

5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004. – 144 с.

6. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.

7. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.

 

Приложение (листинг программы)

CommivoyagerMVG на Turbo Pascal 7.0:

 

 

input.txt (из него загружается информация о n-мерности матрицы и сама матрица):

 

Результат вычислений: