решаю задачу, как распределить несколько объектов (называются модули), имеющие свою продолжительность, по разным станкам, чтобы минимизировать время загрузки наиболее загруженного станка. Решаю методом ветвей и границ, но почему-то в моей программе делается один проход по ветви, а другие ветви не рассматриваются. В чем дело?
насколько я понимаю неправильно работает цикл в 73 строчке, но почему, не понимаю
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <iostream>
#include<clocale>
using namespace std;
int const max_chislo_stankov=51;
int const max_chislo_modulei=51;
int chislo_stankov;
int chislo_modulei;
double obrabotka[max_chislo_stankov+1][max_chislo_modulei+1];
double perenaladka[max_chislo_stankov+1][max_chislo_stankov+1];
int isxodnoe_raspredelenie[max_chislo_modulei+1];
double isxodnaa_zagruzka[max_chislo_stankov+1];
int i,j,k;
double record;
void metod_vetvei_i_granic(int raspredelenie[],int uroven_grafa,double zagruzka_stankov[]);
double maximum (double num[max_chislo_stankov+1]);
int main ()
{
std:setlocale(LC_ALL,"Russian_Russia.1251");
cout<<"Максимальное число станков: "<<max_chislo_stankov-1<<"\n";
cout<<"Максимальное число станков: "<<max_chislo_modulei-1<<"\n";
mmm:
cout<<"введите число станков";
cin>>chislo_stankov;
if(chislo_stankov>max_chislo_stankov-1){
cout<<"ошибка"<<"\n"; goto mmm;
}
mmmm:
cout<<"введите число модулей";
cin>>chislo_modulei;
if(chislo_modulei>max_chislo_modulei-1){
cout<<"ошибка"<<"\n"; goto mmmm;
}
for(i=1;i<chislo_stankov+1;i++){
for(j=1;j<chislo_modulei+1;j++){
cout<<"Введите продолжительность модуля "<<j<< "на станке "<<i<<"\n";
cin>>obrabotka[i][j];
}
}
record=0;
for(i=1;i<chislo_stankov+1;i++){
for(j=1;j<chislo_modulei+1;j++){
record=record + obrabotka[i][j];
}
}
for(i=1;i<chislo_modulei+1;i++){
isxodnoe_raspredelenie[i]=0;
}
i=0;
for(i=1;i<chislo_stankov+1;i++){
isxodnaa_zagruzka[i]=0;
}
metod_vetvei_i_granic(isxodnoe_raspredelenie,1,isxodnaa_zagruzka);
return 0;
}
void metod_vetvei_i_granic(int raspredelenie[],int uroven_grafa,double zagruzka_stankov[]){
cout<<"\n"<<"запущен метод ветвей и границ для распределения"<<" ";
int novoe_raspredelenie[max_chislo_modulei+1];
double novaa_zagruzka_stankov[max_chislo_stankov+1];
double nizhnaa_otsenka;
for (j=1;j<chislo_modulei+1;j++){
novoe_raspredelenie[j]=raspredelenie[j];
cout<<novoe_raspredelenie[j]<<" ";
}
cout<<"\n"<<"и загрузки станков";
for (j=1;j<chislo_stankov+1;j++){
novaa_zagruzka_stankov[j]=zagruzka_stankov[j];
cout<<novaa_zagruzka_stankov[j]<<" ";
}
for(i=1;i<chislo_stankov+1;i++){
novoe_raspredelenie[uroven_grafa]=i;
cout<<"\n"<<"для распределения ";
for(j=1;j<chislo_modulei+1;j++){
cout<<novoe_raspredelenie[j]<<" ";
}
novaa_zagruzka_stankov[i]=novaa_zagruzka_stankov[i]+obrabotka[i][uroven_grafa];
nizhnaa_otsenka = maximum (novaa_zagruzka_stankov);
cout<<"нижняя оценка равна "<<nizhnaa_otsenka;
if (nizhnaa_otsenka<record) {if (uroven_grafa==chislo_modulei) {
cout<<"целевая функция от распределения ";
for(k=1;k<chislo_modulei+1;k++){
cout<<novoe_raspredelenie[k]<<" ";
}
cout<<"равна"<<nizhnaa_otsenka<<"\n";
record=nizhnaa_otsenka;
}
else metod_vetvei_i_granic(novoe_raspredelenie,uroven_grafa+1,novaa_zagruzka_stankov);}
novaa_zagruzka_stankov[i]=novaa_zagruzka_stankov[i]-obrabotka[i][uroven_grafa];
}
}
double maximum (double num[max_chislo_stankov+1]){//double
int i;
double j=num[1];
for(i=1;i<chislo_stankov+1;i++){
if(j<num[i]){j=num[i];}
}
return j;
} |
|
(
