Заказать работу
Узнать стоимость

 


 


 


 


 


 


 


 


 

Математическое программирование

на тему «МЕТОДВЕТВЕЙ И ГРАНИЦ ДЛЯ ЗЦЛП.

ВЕНГЕРСКИЙ МЕТОД ДЛЯ ЗАДАЧИ О НАЗНАЧЕНИЯХ»


 


 


 


 


 


 

Цель работы

понимать смысл, различать, осознанноиспользовать следующие понятия: релаксированная ЗЦЛП; разбиениемножества решений ЗЦЛП на подмножества; оценка подмножества решений;дерево решений, рекорд в методе ветвей и границ для ЗЦЛП;

получить навыки, уметь решать ЗЦЛП методомветвей и границ; строить дерево решений; интерпретировать полученныерезультаты в терминах решаемой задачи;

различать общие и частные задачи ЗЦЛП, выбиратьметоды решения, анализировать полученные результаты.


 

Условие задачи:

п/п

V

v1

v2

v3

v4

c1

c2

c3

c4

9

78

12

15

9

7

35

40

25

15


 

35x1+40x2+25x3+15x4max

12x1+15x2+9x3+7x4≤78

xj≥0(j=1,2,3,4)

xj≤10

xj– целые


 


 

Постановказадачи для венгерского метода для задачи о назначениях.

Предположим, что имеется n различных работA1,A2,..An и механизмов B1,B2…Bn,каждый из которых может выполнять любую работу, но с неодинаковойэффективностью. Производительность механизма B(i)при выполнении работы A(j)обозначим C(I,j),и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы поработам, чтобы суммарный эффект от их использования был максимален.Такая задача называется задачей выбора или задачей о назначениях.

Формально она записывается так. Необходимо выбрать такуюпоследовательность элементов {C(1,j1),C(2,j2)….}из матрицы


 

чтобысумма элементов была максимальна и при этом из каждой строки истолбца С был выбран только один элемент.

Введемследующие понятия.

Нулевыеэлементы z1, z2, z(k) матрицы С называются независимыми нулями, если для любого i строка и столбец, на пересечении которых расположен элемент Z(j),не содержат другие такие элементы z(k).

Описаниеалгоритма венгерского метода


 

Алгоритм состоит из предварительного этапа и не более чем (n-2)последовательно проводимых итераций. Каждая итерация связана сэквивалентными преобразованиями матрицы, полученной в результатепроведения предыдущей итерации, и с выбором максимального числанезависимых нулей. Окончательным результатом итерации являетсяувеличение числа независимых нулей на единицу. Как только количествонезависимых нулей станет равным n, проблему выбора оказываетсярешенной, а оптимальный вариант назначений определяется позицияминезависимых нулей в последней матрице.

Предварительный этап. Разыскивают максимальный элемент в j – мстолбце и все элементы этого столбца последовательно вычитают измаксимального. Эту операцию проделывают над всеми столбцами матрицыС. В результате образуется матрица с неотрицательными элементами, вкаждом столбце которой имеется, по крайней мере, один нуль.

Далее рассматривают i – ю строку полученной матрицы,разыскивают ее минимальный элемент ai и из каждого элемента этойстроки вычитают минимальный. Эту процедуру повторяют со всемистроками. В результате получим матрицу С0 (С0 ~ C), в каждой строке истолбце которой имеется, по крайней мере, один нуль. Описанныйпроцесс преобразования С в С0 называется приведением матрицы.

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

(k+1)-ая итерация. Допустим, что k–я итерация уже проведена и врезультате получена матрица Сk. Если в ней имеется ровно n нулей созвездочкой, то процесс решения заканчивается. В противном случаепереходим к (k+1) – й итерации.

Каждая итерация начинается первым и заканчивается вторым этапом.Между ними может несколько раз проводиться пара этапов: третий –первый. Перед началом итерации знаком “+” выделяютстолбцы матрицы Сk, которые содержат нули со звездочками.

Первый этап. Просматривают невыделенные столбцы Сk. Если среди них неокажется нулевых элементов, то переходят к третьему этапу. Если женевыделенный нуль матрицы Сk обнаружен, то возможен один из двухслучаев: 1) строка, содержащая невыделенный нуль, содержит также инуль со звездочкой; 2) эта строка не содержит нуля со звездочкой.

Во втором случае переходим сразу ко второму этапу, отметив этот нульштрихом.

В первомслучае этот невыделенный нуль отмечают штрихом и выделяют строку, вкоторой он содержится (знаком “+” справа от строки).Просматривают эту строку, находят нуль со звездочкой и уничтожаютзнак “+” выделения столбца, в котором содержится данныйнуль.

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

Этот процесс за конечное число шагов заканчивается одним из следующихисходов:

1) всенули матрицы Сk выделены, т.е. находятся в выделенных строках илистолбцах. При этом переходят к третьему этапу;

2)имеется такой невыделенный нуль в строке, где нет нуля со звездочкой.Тогда переходят ко второму этапу, отметив этот нуль штрихом.

Второй этап. На этом этапе строят следующую цепочку из нулей матрицыСk: исходный нуль со штрихом, нуль со звездочкой, расположенный водном столбце с первым нулем со штрихом в одной строке спредшествующим нулем со звездочкой и т.д. Итак, цепочка образуетсяпередвижением от 0’ к 0* по столбцу, от 0* к 0’ по строкеи т.д.

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

Далее над элементами цепочки, стоящими на нечетных местах ( 0’) –, ставим звездочки, уничтожая их над четными элементами ( 0*). Затем уничтожаем все штрихи над элементами Сk и знаки выделения“+”. Количество независимых нулей будет увеличено наединицу. На этом (k+1) –я итерация закончена.

Третий этап. К этому этапу переходят после первого, если все нулиматрицы Сk выделены. В таком случае среди невыделенных элементов Сkвыбирают минимальный и обозначают его h (h>0). Далее вычитают h извсех элементов матрицы Сk, расположенных в невыделенных строках иприбавляют ко всем элементам, расположенным в выделенных столбцах. Врезультате получают новую матрицу С'k, эквивалентную Сk. Заметим, чтопри таком преобразовании, все нули со звездочкой матрицы Сk остаютсянулями и в С'k, кроме того, в ней появляются новые невыделенные нули.Поэтому переходят вновь к первому этапу. Завершив первый этап, взависимости от его результата либо переходят ко второму этапу, либовновь возвращаются к третьему этапу.

После конечного числа повторений очередной первый этап обязательнозакончится переходом на второй этап. После его выполнения количествонезависимых нулей увеличится на единицу и (k+1) – я итерациябудет закончена.


 

  1. На первой стадии решаем ЗЦЛП без учета целочисленности:

Выводы:


 

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


 


 


 


 

Популярные запросы:


Онлайн помощь на экзамене, заказывать?
Решение ТОЭ
Решение теормеха
РГР по теормеху
Решение сопромата
Расчет по сопромату
Онлайн помощь бухучет
Решение статистики на заказ
Решение задач по экономике
Решение задач по эконометрике на заказ
Тесты по экономике
Заказать решение теормеха
Помощь онлайн сопромат
Решение физики
Пройти тест по бухучету
Карта сайта

РЕШИТЬ-МАТЕМАТИКУ.РФ

Помощь при сдаче экзаменов, срочное решение заданий (1-3 часа). КРУГЛОСУТОЧНАЯ консультация.