Смислена изявление на проблема. Сдружението се N автомобили, всеки може да носи един месец Ки тона товари (I = 1,2, ..., N). С тяхна помощ, необходима за осигуряване на товари (дървен материал, винтове и т.н.) от доставчици до потребителите върху п пътеки в размер на тона на месец R * (к = 1,2, ..., N).
Целта е да се извършват всички натоварвания, на минимална цена, за да направите това, всяко превозно средство, пуснати на Своя Единороден маршрут. Ако възможността за кола в превозвайки товари под тази на потребностите на потребителите, по маршрута, не може да бъде назначен на колата. Ето защо, в една матрица C, характеризиращи разходите за аз-кар, ако той ще бъде назначен за J-ти път.
Унгарски метод за решаване на проблемите за присвояване
Унгарски метод алгоритъм.
Проблемът за възлагане е специален случай на проблема с транспортирането. така че можете да използвате всеки алгоритъм за линейното програмиране, но по-ефективна е унгарският метод за решаването му.
Специфични особености на заданието задача довели до възникването на ефективна унгарски метод за решаването им. Основната идея на унгарската метод е да се премине от първоначалната стойност на квадратна матрица С на еквивалентната матрица с не-отрицателни елементи Se и п независими системи нули, от които няма две принадлежат на един и същи ред или същата колона. За дадена п има н! възможни решения. Ако задача матрични X п единици разположени така, че всеки ред и колона е само един блок, подредени в съответствие с разположени п независимо нула матрица еквивалентна стойност Se, ние откриваме приемливи решения задача проблем.
Следва да се има предвид, че за всяко по неподходящ начин съответната стойност на контингента е определен на достатъчно голям брой M до минимум проблеми. Ако първоначалната матрица не е квадратна, е необходимо да се въведе допълнително желания брой редове и колони, и определя стойностите на елементите, определени условия на проблема, евентуално след редукция, но алтернатива доминиращ разходи за скъпи или изтрит.
Свързани статии