Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.10.2014, 22:08   #1
kirillkucelap
 
Регистрация: 06.04.2014
Сообщений: 8
По умолчанию метод ветвей и границ на с++

решаю задачу, как распределить несколько объектов (называются модули), имеющие свою продолжительность, по разным станкам, чтобы минимизировать время загрузки наиболее загруженного станка. Решаю методом ветвей и границ, но почему-то в моей программе делается один проход по ветви, а другие ветви не рассматриваются. В чем дело?
Код:
#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;
}
kirillkucelap вне форума Ответить с цитированием
Старый 13.10.2014, 22:09   #2
kirillkucelap
 
Регистрация: 06.04.2014
Сообщений: 8
По умолчанию

насколько я понимаю неправильно работает цикл в 73 строчке, но почему, не понимаю?
kirillkucelap вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Метод ветвей и границ для задачи "Багдадский вор" Zavoorchik Помощь студентам 0 01.05.2012 12:04
Коммивояжера метод ветвей и границ kop Помощь студентам 2 21.10.2011 23:30
задача коммивояжера метод ветвей и границ AngelMarik Помощь студентам 0 04.11.2010 12:03
Поиск кратчайшего пути в графе методом полного перебора в глубину. Метод ветвей и границ Олинька Помощь студентам 1 24.12.2008 16:22