Размещено на http://www.allbest.ru/

Введение

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

Задачи и методы, относящиеся к перечисленному кругу вопросов, в литературе именуются по-разному. Наибольшее распространение получил термин «целочисленное программирование», однако встречаются и такие как «дискретное программирование», реже «комбинаторное (или диофантово) программирование».

Существуют задачи линейного программирования, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач - транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).

Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.

Цель данной работы: В данной работе я рассмотрю Целочисленное линейное программирование(ЦЛП) ориентированное на решение задач линейного программирования, также рассмотрю задачу о назначениях. На их примере решу задачи из этой области.

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

Имеется n исполнителей, которые могут выполнять n различных работ. Стоимость выполнения i-работы j-м исполнителем известна и равна . Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

Известна полезность связанная с выполнением i-м исполнителем j-й работы.

,

Для составления математической модели задачи обозначим через факт назначения или не назначения i-го исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то должны принимать только два значения: 1 или 0. Такие переменные называют булевыми. Итак,

.

Приходим к задаче: найти план назначения , который максимизирует суммарную полезность назначений:



,.

при следующих ограничениях.

Каждый исполнитель назначается только на одну работу:

,

На каждую работу назначается только один исполнитель

,

Условия неотрицательности и целочисленности (булевости):

,

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

Задача о назначении имеет самое широкое применение. Например, при закреплении машин за маршрутами, распределении инструментов для обработки различных марок стали, рабочих или бригад и т. д. В каждом конкретном случае математическая модель задачи может иметь специфику. Например, в задаче распределения алгоритмов между вычислительными машинами число распределяемых алгоритмов, как правило, не равно числу машин. При назначении на должности для некоторых исполнителей существуют ограничения. Прежде всего необходимо отметить, что если задача о назначениях ставится при условии получения максимального эффекта, то ее сводят к задаче на минимум. Пусть дана матрица эффективности C=[].В каждом столбце найдем максимальный элемент . Построим матрицу С'=[ ].

Задача

,

где - область допустимых решений системы (1) - (3), эквивалентна задаче

,

В самом деле,

,

Функция Z' достигает минимума при условии, что Z достигает максимума,

Если в задаче о назначениях число исполнителей равно числу работ, то говорят о закрытой модели, в противном случае - об открытой модели задачи о назначениях. Если число m меньше числа исполнителей n (m<n) то вводят n-m фиктивных работ. Считается, что с назначением на фиктивные работы исполнителей не связаны затраты, т. е. соответствующие коэффициенты матрицы потерь равны нулю. В случае же m>n вводят m-n фиктивных исполнителей. Соответствующие элементы матрицы потерь можно полагать очень большими («блокируют бесконечностью»).

И еще одна деталь. Если по каким-либо причинам запрещается выполнение какой-либо работы каким-либо исполнителем, то и в этом случае соответствующую клетку «блокируют бесконечностью» (ставят большую стоимость М). Точное решение задачи о назначениях можно найти венгерским методом, методом динамического программирования и др. Существует также много приближенных методов. Хорошее приближение дает модификация способа Фогеля для определения опорного плана транспортной задачи. [3]



1. Решение задачи о назначениях

1.1 Симплексный алгоритм

Рассмотрим задачу о назначениях, условия которой приведены на рисунке1

2 1	10	15	0	1
10 0	18 1	20 0	9 0	1
15	24	26 1	10	1
12	25	27	8 1	1
1	1	1	1

Если применить метод выбора исходного решения для вычислительных оценок (1. Вычесть наименьший коэффициент строки i из всех остальных коэффициентов затрат в этой строке, что даст новый вектор коэффициентов. 2. Вычесть наименьшую компоненту этого нового вектора из всех элементов столбца /, вследствие чего получается таблица относительных затрат. 3.

Исходный базис показан на рисунке 1. Отметим, что три маршрута (во второй строке) имеют нулевые значения переменных, что указывает на вырожденность. Можно проследить за всеми итерациями, рассмотрев рисунки 3-9, содержащие последовательности полученных оценок и пробные решения. Отметим также, что значение целевой функции не меняется вплоть до отыскания последнего решения.



1.2 Метод, основанный на алгоритме максимального потока/минимальной стоимости

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

Алгоритм сводится к следующим шагам.

Шаг 1. При заданных оценках строк , i = 1, 2, . . ., п, и столбцов , j = 1, 2, . . ., п, дающих неотрицательные относительные оценки () ? 0, определяется, существует ли допустимое решение, в которое входят только маршруты с нулевыми относительными оценками. В случае положительного ответа на этот вопрос -- останавливаемся, так как решение оптимально. В противном случае осуществляется переход к шагу 2.

Шаг 2. Оценки и изменяются таким образом, чтобы относительная оценка по крайней мере одного нового маршрута была равна нулю. Возвращаются к шагу 1. Шаг 1 всегда можно начать, используя значения оценок, определяемые с помощью метода выбора исходного решения (В данном примере относительные оценки являются элементами таблицы на рис. 2.) Однако для сравнения рассматриваемого метода с симплексным алгоритмом удобно начать со значений, приведенных в таблице на рис. 10. Алгоритм максимального потока используется на шаге 1 для определения существования допустимого решения, содержащего только маршруты с нулевыми элементами таблицы на рис. 10. Имеются упрощенные табличные приемы реализации этого алгоритма, но поскольку основной целью в данном случае является разъяснение эффективности алгоритма максимального потока для решения задачи о назначениях, в последующем изложении эти приемы, позволяющие сокращать объем вычислений, не применяются.

Сеть, содержащая маршруты (дуги) с нулевыми относительными

оценками, соответствующими элементам таблицы на рис. 10, построена на рис. 12. Обозначения узлов соответствуют строке i таблицы на рис. 10, и аналогично обозначения соответствуют столбцу j

Рис. поток в сети модели назначений.

этой таблицы. Все дуги, исходящие из источника и входящие в сток, имеют пропускную способность, равную единице, что соответствует ограничениям по строкам и столбцам задачи о назначениях. Если бы максимальный поток в сети был равен четырем, то соответствующее этому потоку решение являлось бы оптимальным, поскольку единичный поток по дуге () означает, что = 1. Пробное решение, в котором величина потока равна трем, показано на рис. 12. Алгоритм максимального потока реализован на рис. 13, показывающем, что в такой сети поток увеличить нельзя. Поэтому необходимо перейти к шагу 2.

Рациональный путь изменения значений величин и заключается в следующем. Поскольку поток в сети, изображенной на рисунке 13, максимален, но меньше четырех единиц, необходимо ввести по крайней мере одну новую дугу ( , ). Исходя из характера потокового алгоритма, целесообразно ограничиться только такими дугами, у которых узел помечен, а узел не помечен. Если ввести в сеть такую дугу, то шаги потокового алгоритма можно продолжить, что позволит просмотреть по крайней мере еще один узел .

Однако, изменяя значения величин и , необходимо проявлять осмотрительность, чтобы не нарушить равенства - - = 0 для дуг, по которым в текущем решении проходит ненулевой поток, а также для дуг, помеченных знаком + в процессе просмотра сети. В противном случае может оказаться невозможным продолжение просмотра после реализации шага 1.

Рис. просмотр сети для обнаружения возможности увеличения потока.

Кроме того, необходимо сохранить соотношение - - ? 0 для всех i и j.

Правило, обеспечивающее выполнение всех этих условий, формулируется следующим образом.

1) Прибавить величину к , если помечен узел .

2) Вычесть величину из , если помечен узел .

Здесь -- наименьшая относительная оценка для дуг между каждым помеченным узлом и непомеченным узлом

На рис.13 узлы и помечены, а узлы не помечены.

Следовательно, в таблице на рис. 13 нужно просмотреть элементы на пересечении строк 3 и 4 со столбцами 1, 2, 3, в результате чего получаем

,



В таблице на рис. 11 приведены измененные значения и , а также новые значения относительных оценок. Отметим, что теперь дуга (, ) имеет относительную оценку, равную нулю, хотя дуге () соответствует положительная относительная оценка. Сеть, отображающая это решение, показана на рис. 14. Алгоритм максимального потока на такой сети продолжает работать и помечаются узлы и, наконец, сток. Знаки + и - на дугах определяют путь, увеличивающий поток, который приводит к оптимальному решению, показанному на рис. 15.

Повторим еще раз вкратце рассмотренный алгоритм. Начав с пробных значений и на шаге 1, нужно применить алгоритм максимального потока к соответствующей сети. Если полученная в результате величина общего потока в сети равна п, то решение оптимально и вычислительная процедура заканчивается. В противном случае следует перейти к шагу 2, на котором значения и изменяются в соответствии с правилами (5) и (6). Далее возвращаются к шагу 1 и несколько измененной в результате выполнения этого шага сети, в которую введена по крайней мере одна новая дуга (в предположении, что соответствующий коэффициент для этой дуги равен ), а некоторые неиспользуемые дуги могут быть исключены. Затем вновь возвращаются к алгоритму максимального потока, применяя его к схеме потока, полученной на предыдущем шаге. Вновь проверяют, равна ли величина потока, общего в сети, числу п и т. д.

Рис.14. измененная сеть.



Рис.15. окончательное решение.

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

1. Всякий раз при реализации шага 2 по крайней мере один узел оказывается просмотренным на последующем шаге 1. Поскольку число узлов в сети конечно, шаг 2 в конце концов приводит к прорыву на последующем шаге 1.

2. Может иметь место лишь конечное число прорывов, так как каждый из них обусловливает увеличение потока, а величина общего потока в сети ограничена сверху.

Одним из следствий доказательства сходимости является то, что для получения решения не требуется применять шаг 2 более чем

0,5( раз. Эта верхняя граница, как правило, намного превышает действительное число повторений шага 2. Вместе с тем следует подчеркнуть, что даже такая верхняя граница значительно меньше, чем , которая является верхней оценкой сходимости симплексного алгоритма, выраженной через число возможных базисных решений.

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

Чтобы приступить к шагу 1 изложенного выше метода, нужно найти оценки и , такие, чтобы все относительные оценки были не отрицательными. Без потери общности можно предположить, что все , поскольку всегда можно прибавить некоторую положительную константу с* к каждому коэффициенту . Тогда шаг 1 изложенного ранее метода можно начать, положив . Если выполнить это условие, то оказывается, что последовательность получаемых решений содержит минимальную стоимость по сравнению со всеми остальными значениями при одной и той же величине потока в сети. Это обстоятельство позволяет изменить структуру алгоритма, что в свою очередь обеспечивает возможность обобщения потокового метода для решения более сложных сетевых задач. Смысл алгоритма заключается в том, чтобы увеличивать общую величину потока таким образом, чтобы это увеличение происходило при минимальных приращениях затрат. Так, если F единиц потока распределяются по сети, с помощью излагаемого метода отыскивается путь минимальной стоимости, увеличивающий поток, причем увеличение потока производится именно на этом пути. Метод отыскания пути минимальной стоимости основан на алгоритме выбора кратчайшего маршрута.

Алгоритм минимальной стоимости/максимального потока сводится к выполнению следующих шагов.

Шаг 1. Исходя из текущего решения, строится новая сеть следующим образом. В эту сеть включается каждая дуга, имеющая в исходной сети нулевой поток, и принимается за длину дуги.



Рис. сеть, соответствующая методу минимальной стоимости максимального потока.

Если между узлами и существует поток, то вводится дуга () и ее длина принимается равной -. При таком принципе построения сети можно увеличить поток из источника в сток по любому пути новой сети по сравнению с величиной потока в исходной сети.

Шаг 2. Найти кратчайший маршрут из источника в сток в новой сети. По стандартным правилам увеличить поток по этому маршруту (пути) в исходной сети. Если все ограничения модели назначений удовлетворяются, то вычислительная процедура заканчивается. В противном случае осуществляется переход к шагу 1.

Изложенный метод демонстрируется на примере рис. 1. Предположим, что в результате применения алгоритма найдено решение минимальной стоимости для величины потока в три единицы. Это решение совпадает с рис. 12, а его стоимость составляет 28(= 2 + 18 + 8).

Новая сеть, построенная на шаге 1, показана на рис. 16. Отметим, что источник связан только с узлом , а сток -- только с узлом поскольку все остальные дуги являются насыщенными. Сеть содержит дуги (), () и (), так как в текущем решении поток имеет противоположное направление. В текущем решении потоки по всем остальным дугам равны нулю.



Рис. кратчайший маршрут.

Далее к этой сети применяется алгоритм выбора кратчайшего маршрута, который приводит к результату, показанному на рис. 17. Направление единичного потока по указанному маршруту дает оптимальное решение, согласующееся с рис. 15. Отметим, что направление единичного потока по дуге () означает, что в исходной сети поток по дуге () должен быть снят. Поскольку длина кратчайшего пути равна 24, общая стоимость окончательного решения составляет 52 (=28 + 24). Длина кратчайших маршрутов из каждого узла является оптимальным значением -, и аналогично длина кратчайшего маршрута из каждого узла есть оптимальное значение .[2]

1.3 Метод кратчайшего маршрута

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

схеме, добавляя на каждой итерации по одной строке и одному столбцу, пока не получают решения задачи размерности п x п. При заданном решении задачи размерности р x р для формирования задачи размерности

(р + 1) x(р + 1) можно выбрать любую из оставшихся строк и любой из оставшихся столбцов.

строка		столбец
		1	2	4
	1	(2)	10	0	1
	2	10	(18)	9	1
	4	12	25	(8)	1
		1	1	1

Как и прежде, этот метод поясняется на примере рис. 1. Предположим, что решена задача размерности 3 X 3, в которую вошли строки 1, 2 и 4 и столбцы 1, 2 и 4 (таблица рис. 1). Для удобства на рис. 18 приведена соответствующая таблица, в которой обведенные кружками величины соответствуют оптимальному решению этой задачи. Отметим, что решение не отличается от решения, показанного на рис. 12.

Для формирования задачи размерности 4 x 4 добавим оставшиеся третью строку и третий столбец таблицы на рис. 1, в результате чего получим таблицу на рис. 19.

Вычислим далее относительные оценки , где для новой строки, а остальные величины являются значениями для оптимальных маршрутов в задаче размерности 3 x 3 . Полученный результат приведен в таблице на рис. 20. Сеть, в которой обозначения узлов соответствуют таблице на рис. 20, показана на рис. 21.

строка	столбец
		1	2	4	3
	3	15	24	10	26	1
	1	2	10	0	15	1
	2	10	18	9	20	1
	4	12	25	8	27	1
		1	1	1	1

Узел узел
	1	2	3	4	,
0	15	24	10	26	0
1	0	8	-2	13	2
2	-8	0	-9	2	18
3	4	17	0	19	8

Рис. сеть, соответствующая методу решения задачи о назначениях размерности 4х4.

Применим алгоритм выбора кратчайшего маршрута для отыскания наилучшего пути из узла 0 в узел 4 на сети, представленной на рис. 21. Решение, показанное на рис. 22, соответствует оптимальному решению исходной задачи о назначениях.

Чтобы показать эффективность предложенного метода, требуется доказать неотрицательность длины любого пути вдоль каждого контура, содержащегося в сети, где отыскивается кратчайший маршрут. Напомним, что это условие является обязательным для применения алгоритма отыскания кратчайшего маршрута. Анализируя рис. 21, приходим к выводу, что единственными возможными контурами являются контуры, проходящие через узлы 1, 2 и 3, соответствующие строкам и столбцам задачи размерности 3 x 3 . Как обычно, оптимальное решение задачи размерности 3 x 3 должно оставаться оптимальным, если выразить его в относительных оценках таблицы на рис. 20. Контур, проходящий через узлы 1, 2 и 3, равносилен некоторому решению задачи 3 x 3 . Следовательно, ни один контур не может иметь отрицательной стоимости (длины), поскольку оптимальное решение задачи 3 x 3 , приведенное в таблице на рис. 20, имеет нулевую стоимость.

Рис. кратчайший маршрут из узла 0 в узел 4. [2]

1.4 Венгерский метод

Рассмотрим следующий пример. Пусть для выполнения пяти различных работ имеется пять человек. Из отчетных данных известно, какое время требуется каждому из них для выполнения каждой работы. Эти данные приведены в таблице.

исполнители	работы	наличие
	1	2	3	4	5
1	2	9	2	7	1	1
2	6	8	7	6	1	1
3	4	6	5	3	1	1
4	4	2	7	3	1	1
5	5	3	9	5	1	1
потребности	1	1	1	1	1	5

В данном случае величины представляют собой затраты времени каждого работника на выполнение каждой из работ, а величины равны либо 1, либо 0, причем равен 1, если работник i назначен на работу j, и 0 во всех остальных случаях. Таким образом задача сводится к минимизации функции. стоимость маршрут линейный программирование

,



при следующих ограничениях.

,

,

,

Ясно, что если отбросить последнее условие и заменить его условием

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

Однако вследствие вырожденности методы решения транспортных задач в случае задачи о назначении оказываются малоэффективными. При любом назначении всегда автоматически совпадают поставки по строке со спросом по столбцу и поэтому вместо 2n-1 получаем n ненулывых значений . В связи с этим необходимо заполнить матрицу n-1 величинами е, и может оказаться, что ненулевые значения определяют оптимальное решение, однако проверка его не обнаруживает, так как величины е расставлены неверно.

Метод решения задачи о назначении основан на двух довольно очевидных теоремах. Первая из них утверждает, что решение не изменится, если прибавить к любому столбцу или строке матрицы некоторую константу или вычесть ее из них. Эта теорема точно формулируется следующим образом:

Теорема 1.

Если минимизирует



,

по всем , таким что и

,

то минимизирует также функционал

,

где при всех

Теорема 2.

Если все и можно отыскать набор такой, что

,

то это решение оптимально.

Вторая теорема очевидна. Для доказательства первой теоремы заметим, что

,

,

Вследствие того что величины, вычитаемые из Z с целью получения , не зависят от , достигает минимума всегда, когда минимизируется Z, и наоборот.

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

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

Таблица А)

исполнители	работы	вычитается
	1	2	3	4	5
1	1	8	1	6	0	1
2	5	7	6	5	0	1
3	3	5	4	2	0	1
4	3	1	6	2	0	1
5	4	2	8	4	0	1

Таблица Б)

исполнители	работы
	1	2	3	4	5
1	0	7	(0)	4	0
2	(4)	6	5	3	0
3	2	4	3	(0)	0
4	2	(0)	5	0	0
5	3	1	7	2	(0)
вычитается	1	1	1	2	0

Из столбцов и строк было вычтено всего 10 единиц. Поэтому для правильной оценки любого решения, получаемого при использовании таблицы (Б), необходимо прибавить к результату 10 единиц

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

Заметим предварительно, что любое дальнейшее вычитание из строки или столбца, хотя и может приводить к появлению новых нулей, неизбежно приводит в появлению отрицательных элементов, так что нулевое решение теперь не обязательно будет оптимальным. Однако отрицательные элементы можно исключить, прибавляя соответствующие числа к строкам или столбцам. Так например, если вычесть 2 из столбца 1 в таблице (Б), то в строке 1 появится элемент - 2. Если теперь прибавить 2 к строке 1, то вновь получим матрицу с неотрицательными элементами. Задача заключается в том, чтобы получать новые нули указанным способом, но вместе с тем в конечном счете получить матрицу, содержащую решение среди одних нулей. Можно доказать, что описываемый ниже алгоритм обеспечивает решение этой задачи.

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

Таблица 1

	1	2	3	4	5
1	0	7	0	4	0
2	4	6	5	3	0
3	2	4	3	0	0
4	2	0	5	0	0
5	3	1	7	2	0

Заметим, что в данном случае используется только четыре линии, а следовательно, нулевые клетки не содержат оптимального решения.

2. Выбрать наименьший элемент, через который не проведена линия. В примере это 1 в клетке (5,2).

3. Вычесть это число из всех элементов, через которые не проведена ни одна линия, и прибавить его ко всем элементам, через которые проведены две линии. В данном примере получается результат, показанный в таблице 2.



Таблица 2

	1	2	3	4	5
1	0	7	0	4	1
2	3	5	4	2	0
3	2	4	3	0	1
4	2	0	5	0	1
5	2	0	6	1	0

Этот шаг должен приводить к появлению нуля в клетке, где его ранее не было. В рассматриваемом примере это клетка (5,2).

4. Определить, имеется ли решение среди нового набора нулей. Если решение не обнаруживается (в данном примере оно отсутствует), то вернуться к шагу 1 и выполнить все последующие шаги, пока не будет найдено решение . продолжая рассматривать данный пример, получаем результат, приведенный в таблице 3.

Таблица 3

	1	2	3	4	5
1	0	7	0	4	1
2	3	5	4	2	0
3	2	4	3	0	1
4	2	0	5	0	1
5	2	0	6	1	0

Наименьшее незачеркнутое число в таблице теперь равно2, поэтому далее получаем таблицу 4.

Таблица 4.

	1	2	3	4	5
1	0	9	(0)	6	3
2	1	5	2	2	(0)
3	0	4	1	(0)	1
4	0	(0)	2	0	1
5	(0)	0	4	3	0



В этой таблице уже содержится решение, помеченное скобками и имеющее значение 13, что на 1 лучше исходного допустимого решения. [1], [5].

Пример 2.

Представлено четыре студента и четыре вида работ. Следующая таблица соответствует матрице стоимостей для этой задачи.

	Уборка гаража	Мойка машин	Подстрижка газонов	Выгул собак
Даша	1	4	6	3
Катя	9	7	10	9
Алла	4	5	11	7
Саша	8	7	8	5

Выполним первый шаг алгоритма.

	Уборка гаража	Мойка машин	Подстрижка газонов	Выгул собак	Минимумы по строкам
Даша	1	4	6	3
Катя	9	7	10	9
Алла	4	5	11	7
Саша	8	7	8	5

Теперь вычтем минимальные стоимости из элементов соответствующих строк.

	Уборка гаража	Мойка машин	подстрижка газонов	Выгул собак
Даша	0	3	5	2
Катя	2	0	3	2
Алла	0	1	7	3
Саша	3	2	3	0
Минимум по столбцам	,	,	,	,



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

	Уборка гаража	Мойка машин	подстрижка газонов	Выгул собак
Даша	0	3	2	2
Катя	2	0	0	2
Алла	0	1	4	3
Саша	3	2	0	0

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

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

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

В задаче данного примера требуется провести три прямых, это приводит к следующей таблице:

	Уборка гаража	Мойка машин	подстрижка газонов	Выгул собак
Даша	0	3	2	2
Катя	2	0	0	2
Алла	0	1	4	3
Саша	3	2	0	0

Наименьший невычеркнутый элемент равен 1. Этот элемент вычитаем из остальных невычеркнутых элементов и прибавляем к элементам, стоящим на пересечении прямых. В результате получим матрицу, представленную в следующей таблице.

	Уборка гаража	Мойка машин	подстрижка газонов	Выгул собак
Даша	0	2	1	1
Катя	3	0	0	2
Алла	0	0	3	2
Саша	4	2	0	0

Оптимальное решение, показанное в таблице, предлагает Даше убрать гараж, Кате стричь газоны, Алле мыть машины, а Саше выгуливать собак. Соответствующее значение целевой функции равно 1+10+5+5=21. Такое же значение можно получить путем суммирования значений и и значения элемента, наименьшего среди всех невычеркнутых:

(1+7+4+5)+(0+0+3+0)+(1)=21.

1.5 Метод отсечения. Алгоритм Гамори

Рассмотрим полностью целочисленную задачу линейного программирования

,

,

,

,

Алгоритм Гамори состоит из нескольких этапов:

1. Решается задача (1) - (3) с отброшенным условием целочисленности.

2. Полученное оптимальное решение (если оно существует) проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение задачи (1) - (4) совпадает с оптимальным решением задачи (1) - (3). Если это решение не выполняется хотя бы по одной переменной, то переходят к третьему этапу. Если задача (1)-(3) оказывается неразрешимой, то задача (1)-(4) тоже не имеет решения.

3. Строится дополнительное ограничение, отсекающее часть области, в которой содержится оптимальное решение задачи (1) - (3) и не содержится ни одного допустимого решения задачи (1) - (4).

Последний этап предусматривает возвращение к задаче линейного програмирования с отброшенным условием целочисленности, но с расширенной системой ограничений, в которую включено дополнительное ограничение, полученное на третьем шаге. К расширенной системе ограничений вновь применяется симплексная процедура. Если найденное таким образом решение будет опять нецелым, то формируется новое дополнительное ограничение и процесс вычислений повторяется.

Алгоритм Гамори позволяет за конечное число шагов прийти к оптимальному целочисленному решению, если оно существует.

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

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

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

Для лучшего понимания существа вопроса обратимся к наглядной иллюстрации случая n=2 (рис. 1). Ограничения задачи определяют на плоскости некоторый многоугольник М, в вершине которого, если не учитывать условия целочисленности, достигается максимум целевой функции. Внутри этого многоугольника имеется конечное множество точек, которым соответствуют решения с целочисленными значениями переменных (на рисунке они обозначены кружочками). На рисунке показаны три прямые l1 ,l2 ,l3 соответствующие трем дополнительным линейным ограничениям. Каждая из прямых отсекает часть области допустимых решений. Так, после отсечения части области прямой оптимальной оказывается вершина ,и, наконец, оптимальной становится целочисленная вершина .Основное в алгоритме - составление дополнительного ограничения, т. е. отсекающей гиперплоскости, которая называется правильным отсечением. Правильное отсечение должно удовлетворять следующим условиям:

1. быть линейным;

2. отсекать найденное оптимальное нецелочисленное решение задачи (1) - (3);

3. не отсекать ни одной из целочисленных точек задачи (1) - (5).



Формирование правильного отсечения. После каждой итерации система ограничений имеет вид

,

где {БП} - множество базисных переменных.

Если выполняется условие оптимальности задачи, то находим оптимальное решение. Если, все компоненты оптимального плана целочисленны, то задача решена. Предположим, что некоторые (- нецелые. Пусть компонента - нецелая. Рассмотрим равенство системы (5), для которой выполняется условие оптимальности, т.е.

,

Напомним, что наибольшая целая часть числа а, его не превосходящая, обозначается [а], а дробная положительная- {а}. Причем

,



Например, пусть а = 3,2.

Имеем [3,2] = 3; {3,2}=0,2;

3,2 =3+0,2.

Пусть а= - 4,3.

Имеем [-4,3]=-5, {-4,3}=0,7,

-4,3=-5 + 0,7.

Перейдем к дальнейшему изучению уравнения (6). Найдем целую и дробную части его коэффициентов и .Согласно равенству (7), имеем:

,

,

Так как, по предположению

Кроме того, . Подставив выражение (8) в равенство (6), получим

,

Так как первое слагаемое равенства (9) есть целое число, то, для того чтобы было целым, необходимо, чтобы второе слагаемое также было целым, т. е. величина

,

должна быть целым числом. Так как - координата допустимого целочисленного решения задачи (1) - (4), то -всегда целое число. Покажем, что ?0. В самом деле, величина

,

не может быть отрицательной. Из условия (47) следует 0? Так как -целое, то из предположения,что > 0, должно следовать , что противоречит определению дробной части числа. [4]

Итак, доказано, что любое допустимое решение задачи (1) - (4) должно удовлетворять неравенству

,

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

Идея метода динамического программирования состоит в том, чтобы идти от последних решений к более ранним.

Пусть для решения некоторой комбинаторной задачи нам нужно принять последовательность из n решений, скажем . Тогда, если эта последовательность оптимальна, последние k решений должны быть оптимальны. То есть завершающая часть оптимальной последовательности решений должна быть оптимальной. Это утверждение часто называют принципом оптимальности.

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

Рассмотрим на примере:

Пусть даны множества S ? и k?S. Обозначим через

С(S, k) оптимальную стоимость пути, начинающегося из города 1, проходящего по всем городам множества S и заканчивающегося в городе k. Начнем с нахождения С(S, k) для , что дает просто

для всех k=2,…,n.

Для вычисления С(S, k) для мы используем тот факт, что для нахождения наилучшего маршрута из города 1 в город k, проходящего через все города множества S, достаточно рассмотреть для каждого m вариант, в котором m посещается непосредственно перед k, и обратиться к . Таким образом,

,

Этот минимум можно вычислить для всех множеств S данной мощности и для каждого возможного города m из S ( при этом необходимо хранить город m, для которого достигается минимум, с тем, чтобы можно было восстановить оптимальный обход обратным просмотром). Если считать, что для каждого значения C(S,k) требуется одна ячейка памяти, то в целом требуется память

,

ячеек, а число сложений и сравнений равно

,

Эти функции экспоненциальны относительно размера задачи n и могут показаться недопустимо большими. Однако, если вспомнить тот факт, что при простом переборе имеется (n-1)! Различных обходов, можно понять, что на самом деле этот подход дает огромный выигрыш.

Как видно из примера, динамическое программирование является очень общей идеей и может требовать большей или меньшей изобретательности для нахождения хороших способов разбиения задачи на этапы, при которых можно найти удобное рекуррентное соотношение. [4]



Вывод по работе

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

Узнала, что:

Метод назначений - это один из методов линейного программирования, который предназначен для оптимального подбора n "предложений" к n "потребностям", например, для назначения вида работы машине, назначения вида работы производственному отделу, назначения человека на должность и т.д.

Метод назначений применяется при решении задач, имеющих следующие характеристики:

Имеется n "предметов", которые должны быть распределены по n "пунктам назначения".

Каждый "предмет" должен быть назначен единственному "пункту назначения". В понятие "предмет" и "пункт назначения" может вкладываться различное смысловое значение, определяемое конкретной задачей менеджмента. Так в качестве предмета может выступать определенный вид деятельности (работы), должность, человек и т.д.

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

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



Список используемой литературы

1. Акоф Р. «Основы исследования операций»: Мир, Москва 1971.-531с.

2. Вагнер Г. «Основы исследования операций т.1»: Мир, Москва 1972. - 336 с.

3. Волков И.К. «Исследование операций»: МГТУ им. Баумана, Москва 2000.-436с.

4. Пападимитриу Х. «Комбинаторная оптимизация»:Мир, Москва 1984.-512с.

5. Таха А. «Введение в исследование операций»:Вильямс, 2001.-912с.

Размещено на Allbest.ru

...