Курсовая работа: Дискретное программирование

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

Тогда система ограничений задачи (D(q), f) может быть представлена как

а получаемая на ее основе система ограничений задачи (1(q), f) как

Или

где хn+1 ≥ 0 — фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для преобразования неравенства в строгое равенство.

Очевидно, что 1≤k≤m, т. к. небазисные компоненты оптимального плана (m+1≤j≤n) равны нулю, т. е. являются заведомо целочисленными. Тогда с учетом сделанных предположений о виде базиса можно записать:

Как видно из 35, в k-м столбце имеется всего два отличных от нуля элемента: в k-й и (m+1)-й строках. Если вычесть из (m+1)-го уравнения k-e, то, учитывая, что [άk] – άk =-{άk}, получим эквивалентную систему:

Проведенные преобразования системы ограничений D1(q) позволили явно выделить сопряженный базис, образуемый столбцами с номерами 1,..., m, n+1, и соответствующий ему псевдоплан (ά1, ..., άm, 0,...., 0, -{άk}), т.е. для решения задачи (D1(q), f) может быть применен алгоритм двойственного симплекс-метода. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис.5.

Для случая задачи (D2(q), f) преобразование симплекс-таблицы, получаемое на базе аналогичных рассуждений, приведено на рис.6.

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

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

6. Заключение

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

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