Целочисленное программирование
Основные понятия целочисленного программирования. Суть симплекс-метода, поэтапное заполнение таблицы. Применение алгоритмов Гомори для решения задач. Метод ветвей и границ. Метод решения задачи о назначениях, задачи коммивояжера и задачи о ранце.
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 09.12.2011 |
| Размер файла | 213,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Якутский государственный университет им. М.К. Аммосова»
Технический институт (филиал) в г. Нерюнгри
Педагогический факультет
Кафедра Математики и Информатики
Курсовая работа
по дисциплине «Экономико-математические модели»
на тему: «Целочисленное программирование»
Студентка
В.А. Водолазская, гр. МО-04
Нерюнгри 2008г.
Введение
При рассмотрении целого ряда задач финансового менеджмента и бизнеса необходимо учитывать требование целочисленности используемых переменных. Такие задачи называются задачами целочисленного программирования.
Под задачей целочисленного программирования понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Особый интерес к задачам целочисленного програмирования вызван тем, что во многих практических задачах необходимо находить целочисленное решение ввиду дискретности ряда значений искомых переменных.
Цель работы: Рассмотреть методы решения задач целочисленного линейного программирования.
Задачи работы: С помощью методов решения задач целочисленного программирования научиться решить:
а) задачу о назначениях;
б) задачу коммивояжёра;
в) задачу о ранце.
1.Теоретический аспект целочисленного программирования
1.1 Предпосылки появления целочисленного программирования
Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики - главным образом в работах американских математиков Дж.Данцига и Р.Гомори. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего линейного программирования. Однако в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.
Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. С появлением ЭВМ, ростом их производительности повысился интерес к задачам такого типа и к математике в целом.
1.2 Основные понятия целочисленного программирования
Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач.
1.3 Целочисленное программирование как метод оптимизации
Оптимальность - выбор наилучшего варианта из множества допустимых или имеющихся в наличии вариантов. Суть принципа оптимальности состоит в выборе такого планового управленческого решения, где его компоненты расположены в наилучшем порядке и учитывают внутренние возможности и внешние условия.
Принцип оптимальности в практике планирования и управления - это решение экстремальной задачи вида . Функция, указанная в данном определении является целевой функцией. Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Для реализации условия оптимальности необходимы указания системы ограничений
(1)
Задача оптимизации в общем случае, включает три компоненты - целевую функцию F, ограничения gi и граничные условия, и имеет следующую математическую постановку:
(2)
где aj и bj --нижнее и верхнее предельно допустимые значения хj.
Задачу (2) можно представить в еще более общей компактной форме записи
(3)
Граничные условия показывают предельно допустимые значения искомых переменных, и в общем случае они могут быть двусторонними типа
Задачи оптимального программирования классифицируются:
1. по характеру изменения переменных:
- линейные;
- нелинейные.
2. по характеру изменения переменных:
- непрерывные;
- дискретные.
3. по учету фактора времени:
- статические;
- динамические.
4. по наличию информации о переменных:
- полная определенность;
- в условиях неполной информации;
- задачи в условиях неопределенности.
5. по числу критериев оценки альтернативы:
-однокритериальные;
- многокритериальные.
Частный раздел оптимального программирования являющийся в свою очередь разделом прикладной математики изучающий задачи условной оптимизации является - линейное программирование.
Задача линейного программирования, для которой используются возможные способы решения, должна быть записана в канонической форме.
Целевая функция имеет вид:
(4)
Ограничения имеют вид
(5)
Вектор удовлетворяющий системе ограничений называется допустимым решением (планом задачи линейного программирования). План, который доставляет максимум или минимум целевой функции называется оптимальным планом задачи линейного программирования.
Наиболее распространенным методом решения линейного программирования является симплекс-метод.
И так, целочисленным программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых решение задач оптимизации должны быть целые числа, тогда такие задачи называются задачами целочисленного программирования, но в том случае если ограничения и целевая функция задачи представляют собой линейные зависимости.
2. Методы решения задач целочисленного программирования
2.1 Симплекс-метод
Симплекс-метод является универсальным методом решения задач линейного программирования. Суть данного метода заключается в построении допустимого ограничения (начало - опорное решение и последовательное улучшение этого плана при помощи определенного количества итераций). Симплекс-метод применяется для решения задач линейного программирования записанных в канонической форме. Нахождение начального опорного плана и переход к следующему опорному решению осуществляется при помощи метода Жордана-Гаусса для системы линейных уравнений.
Итак, рассмотрим задачу линейного программирования с ограничениями в форме уравнений. Дана система
(6)
m линейных уравнений с n неизвестными и линейная функция
(7)
Среди неотрицательных решений системы (6) нужно найти такое, которое минимизирует функцию (7).
Для начала работы по симплекс-методу требуется, чтобы заданная система уравнений была приведена к допустимому виду. Это означает, что какие-то из неизвестных должны быть выражены через остальные неизвестные, причем свободные члены этих выражений неотрицательны.
Пример допустимой системы:
(8)
здесь свободные члены равны соответственно 5,4 и 0.
Неизвестные в допустимом виде системы, которые выражены через остальные, называются базисными, а весь набор этих неизвестных - допустимым базисом неизвестных. Остальные неизвестные называются небазисными или свободными. Например, в системе (8) допустимый базис образован неизвестными х1, х2, х3; неизвестные же х4 и х5 - свободные.
По поводу возможности приведения системы (6) к допустимому виду заметим пока только следующее. Если система (6) совместна, то метод Гаусса позволяет выделить в ней базис неизвестных. Весь вопрос в том, будет ли этот базис допустимым, т. е. будут ли все свободные члены в правых частях уравнений неотрицательными. Можно, конечно, попытаться перебрать все возможные базисы неизвестных, чтобы отыскать среди них допустимый базис, но это весьма трудоемкая работа.
После того как выделен допустимый базис неизвестных, можно в выражении (7) для целевой функции заменить каждое базисное неизвестное его выражением через свободные. В итоге функция f запишется через одни лишь свободные неизвестные.
Например, если
а система ограничений приведена к виду (7), то новое выражение для f будет
Чтобы упростить дальнейшие записи, будем считать, что имеется всего
пять неизвестных х1, х2, х3, х4, х5 и система ограничений приведена к допустимому виду с базисом {x1, х2, х3 }:
(9)
а целевая функция - к виду
(10)
Напомним, что решается задача о минимизации f при ограничениях (9) и условиях
, , , ,
Положим все свободные неизвестные равными нулю:
,
и найдем из системы (4) значение базисных неизвестных:
Полученное таким путем решение системы (9):
(11)
будет неотрицательным. Оно называется базисным решением, отвечающим базису {х1, х2, х3 } . Для базисного решения значение функции f равно f В =.
Возможны три случая:
1. Все коэффициенты при свободных неизвестных в выражении для f неотрицательны:
Тогда для любого неотрицательного решения системы (9) имеем , значит, .Таким образом, , т. е. базисное решение является оптимальным -- задача решена.
2. Имеется свободное неизвестное, коэффициент при котором в выражении f отрицателен, а все коэффициенты при этом неизвестном в уравнениях (9) - неотрицательны.
Пусть, например, а , . Тогда, отправляясь от базисного решения (11), будем наращивать значение х4 (не меняя х5=0). Значения базисных неизвестных также будут меняться; мы получим:
т. е. решение (х1, х2, х3, х4, 0,0) будет оставаться неотрицательным. При этом , и ввиду 4<0 значение f с ростом х4 будет неограниченно уменьшаться. Таким образом, в этом случае т. е. задача решения не имеет.
3. Имеется свободное неизвестное, коэффициент при котором в f отрицателен, но и среди коэффициентов при этом неизвестном в уравнениях (9) также есть отрицательные.
В этом случае производится шаг, а именно, от базиса В мы переходим к новому базису В', с таким расчетом чтобы значение fв уменьшилось или по крайне мере не увеличилось: Разумеется, изменение базиса влечет за собой соответствующую перестройку системы (9) ограничений и выражений (10) для функций f.
Опишем конкретно содержание шага. Пусть, например, и отрицательны, а
- положительно или равно 0:
(12)
Если снова, как в случае II, наращивать значение х4 то будем иметь:
Ввиду и значения и будут уменьшаться, а значение будет оставаться неотрицательным (так как по-прежнему ). При наращивании наступит момент, когда одно из неизвестных и обратиться в нуль: для таким моментом будет , а для - . Выберем из этих отношений наименьшее. Пусть, например, это будет . Тогда наращивание возможно только от 0 до . При неизвестное обратиться в нуль, а при дальнейшем росте неизвестное станет уже отрицательным , что не допускается. Пологая в системе (4) и , получим решение:
, , , , (13)
для которого значение функции f будет , (поскольку и ).
Таким образом, с ростом х4 первым из базисных неизвестных обращается в нуль неизвестное x1. Это служит для нас сигналом к замене базиса B = {х1, х2 , х3 } на B' = {x4 , х2 , х3 } , а именно: из старого базиса удаляется неизвестное х1 и вместо него в базис вводится неизвестное х4 ( из числа прежних свободных).
Смена базиса, как уже говорилось, влечет за собой перестройку системы (9). Из первого уравнения (для х1) выражаем:
(14)
и подставляем это выражение для х4 в остальные два уравнения.
В итоге получаем систему вида:
(15)
с базисным решением:
, , , , (16)
которое должно совпадать с решением (13), поскольку, как видно из самой системы (14), двух разных решений с х1,=0, х5=0 быть не может. Таким образом, базисное решение (15) является снова неотрицательным. Что же касается нового значения функции f , то оно равно:
(17)
и, таким образом, (следует учесть, что и поэтому ). Итак, с переходом от базиса В к В' система ограничений сохранила допустимую форму (10), где а0,b0,с0, а значение функции f для базисного решения уменьшилось или осталось прежним.
Переход от базиса В к новому базису В' и означает шаг, который делается в случае III. Разумеется, старое выражение для f, т. е. (10) , должно быть теперь заменено новым:
(18)
которое получается из (10) заменой неизвестного х4 по формуле (14).
Если для полученной задачи (15), (18) снова имеет место случай III, то делаем следующий шаг, т. е. переходим к новому базису В", для которого и так до тех пор, пока не придем к одному из случаев I или II. Тогда процесс заканчивается.
Производя расчеты по симплекс - методу, нет необходимости выписывать все вычисления столь подробно, как мы делали это в предыдущих примерах. Оказывается, весь процесс можно записать в виде последовательности однотипно заполняемых таблиц, причем каждому шагу будет отвечать переход к следующей таблице.
Описание симплекс - таблиц произведем на примере задачи (9), (10), где требуется минимизировать функцию (10) при ограничениях (9) и условиях хj 0 (i=1,....,5).
Для заполнения первой таблицы необходимо в каждом из уравнений (4) перенести все члены, кроме свободного, из правой части в левую, т. е. записать (9) в виде:
(19)
Аналогичную работу следует проделать и с равенством (10):
Теперь можно заполнить симплекс-таблицу (таблица 1):
Таблица 1: Симплекс-таблица
Базисныенеизвестные |
Свободныечлены |
||||||
|
1 |
0 |
0 |
|||||
|
0 |
1 |
0 |
|||||
|
0 |
0 |
1 |
|||||
|
f |
0 |
0 |
0 |
Заглавная строка таблицы и характер заполнения, не считая, стрелок, в комментариях не нуждаются. Расстановку стрелок поясним ниже.
В соответствии с ранее описанной методикой мы должны, прежде всего, выяснить, имеется ли в первоначальном выражении:
хотя бы один отрицательный коэффициент при х4 и х5. Поскольку при внесении в таблицу коэффициенты при х4 и х5 поменяли знаки, то мы должны, выяснить, имеются ли в последней строке таблицы (не считая свободного члена ) положительные числа. Если таковых нет, то базисное решение, отвечающее данному базису, т. е. является оптимальным, а - задача решена.
Предположим, что в последней строке имеется (не считая) положительное число 4. Отмечаем столбец, в котором оно находится, вертикальной стрелкой. Далее просматриваем остальные числа этого столбца. Если среди нет отрицательных чисел - это означает, что , и мы имеем случай II. Тогда ,и процесс снова прекращается.
Пусть, наконец, среди чисел отмеченного столбца, кроме последнего числа, имеются положительные числа. Это означает, что мы имеем случай III и, следовательно, должны сделать шаг. Например, как мы считали ранее, пусть -, (это означает ), а (т.е. ), в точном соответствии с предложением (17). В этом случае описанная ранее методика предписывает составить отношения:
и выбрать из них наименьшее.
Пусть, например, таковым является отношение, отвечающее строке таблицы с базисным неизвестным х1. Отмечаем эту строку горизонтальной стрелкой. Элемент таблицы, стоящий в отмеченном столбце и отмеченной строке, называется разрешающим элементом. В данном случае это .
С этого момента начинается перестройка таблицы, цель которой состоит в переходе к новому базису {х4,х2,х3}. Ее можно осуществить при помощи все того же метода Гаусса. А именно умножаем выделенную строку на такое число, чтобы на месте разрешающего элемента появилась единица, т. е. умножаем на . Это соответствует тому, что первое из уравнений (19) разрешается относительно нового базисного неизвестного х4. Полученную таким образом новую строку вписываем уже в новую таблицу снова в виде первой строки. Затем к каждой из остальных строк таблицы 1 прибавляем вновь полученную строку, умноженное на такое число, чтобы в клетке отмеченного столбца появился нуль - это соответствует исключению неизвестного х4 из остальных уравнений, а также из выражения для f. Преобразованные таким образом строки пишем в новую таблицу на место прежних строк. В результате получаем новую таблицу.
К новой таблице применяется та же процедура. В результате или находится оптимальное решение (случай I), или обнаруживается, что (случай II), или же производится следующий шаг (случай III) - получаем ещё одну новую таблицу. И так далее, пока процесс не остановится (случай I или случай III).
2.2 Первый алгоритм Гомори
Рассмотрим полностью целочисленную задачу линейного программирования, в которой n1 = n.
Пусть - оптимальный опорный план задачи на целочисленность. Если они все целые, то . Если хотя бы одна координата, допустим , будет нецелой, поступим следующим образом.
Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы выразим целевую функцию и все переменные через небазисные переменные :
(20)
Так как - нецелая величина, обозначим ближайшее целое число, не превосходящее , через (целая часть) и определим дробную часть числа
(21)
Очевидно, .
Теорема 1: Пусть - допустимое решение задачи . Тогда соотношение
(22)
определяют правильное отсечение.
Доказательство: Запишем выражение (21) в виде
Используя выражение (22), получим
Или
.
На основании предположения теоремы о допустимости решения задачи и - целые. Величины и целые по определению. Следовательно, тоже целое.
Докажем, что . Предположим, что . Это значит, что
По определению дробной части . По условию теоремы x - допустимое решение задачи , поэтому . Следовательно, , . Отсюда , или, что то же самое, . Итак, - нецелое, а это противоречит только что доказанному. Следовательно, предположение неверное.
Теорема доказана.
Следствие: Любое оптимальное решение задачи , не являющиеся допустимым решением задачи не удовлетворяет условию правильного отсечения (22).
Доказательство: Пусть - оптимальное решение задачи , -дробное. Покажем, что не удовлетворяет условию отсечения. Из оптимальности плана следует, что. Поэтому . Учитывая это, подставим в выражение (22):
что противоречит условию .
Важной проблемой метода отсечения является нарастание количества дополнительных ограничений по мере решения вспомогательных задач, оптимальные планы которых будут содержать нецелые координаты, т.е. возникает проблема размерности. Гомори предложил прием, ограничивающий размеры рассматриваемых расширенных симплексных таблиц числом , где n - количество переменных задач , k - число ее небазисных переменных. Этот прием основан на том, что дополнительные ограничения (правильные отсечения) интересуют нас лишь как способ отсечения нецелочисленного оптимального решения и перехода от задачи к задаче . Заметим, что переменная выводится из базиса сразу же после введения ограничения:
,
.
2.3 Второй алгоритм Гомори
Данный алгоритм предназначен для решения задач, в которых требование целочисленности наложено на некоторые переменные (в частности и на все). Рассмотрим его применение к частично целочисленным задачам линейного программирования, имея в виду, что вычислительная схема будет справедлива и для полностью целочисленных задач. Пусть требуется максимизировать функцию
(23)
при условиях
(24)
(25)
(26)
Метод решения задачи (23) - (26) основывается на той же идее, что и метод решения полностью целочисленных задач. Сформулируем второй алгоритм Гомори в виде следующей теоремы.
Теорема 2: Пусть - оптимальное решение задачи и - соответствующая симплексная таблица. Если - не целое, то неравенство
(27)
или, что то же самое,
(28)
(29)
где
(30)
(31)
определяет оптимальное отсечение.
Мы проверим лишь условие отсечения. Для этого докажем, что оптимальное решение задачи , не являющееся допустимым решением исходной задачи (23) - (26), не удовлетворяет условиям отсечения. Пусть в оптимальном решении величина нецелая, . Так как в оптимальном решении все небазисные переменные равны нулю:
()
Тогда формула (8) примет вид
Поскольку по условию теоремы . Условие отсечения выполнено.
Правило построения правильного отсечения: Пусть не удовлетворяет условию целочисленности (26) и - симплекс-таблица, соответствующая полученному оптимальному решению задачи . Выберем
и построим правильное отсечение по формулам (28) - (31).
2.4 Метод ветвей и границ
Метод ветвей и границ -- один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
Алгоритм решения:
Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и
Fmax = F(Xo)
Если же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X0) F(X) для всякого последующего плана X.
Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу . Определяя эти числа, находим симплексным методом решение двух задач линейного программирования:
(32)
Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:
1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.
Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II).
4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II).
Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.
Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы:
1. Находят решение задачи линейного программирования (1)-(3).
2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
3. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.
Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод.
целочисленный программирование задача коммивояжер ранец
3. Прикладные задачи целочисленного программирования
3.1 Задача о назначениях
Задача о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 1.
Формулировка задачи о назначениях: Пусть имеется n претендентов (каждому из которых соответствует индекс ) на n рабочих мест (каждому из которых соответствует индекс ), при этом известна стоимость затрат , связанных с назначением i - го претендента на j - ое рабочее место. Требуется распределить претендентов по рабочим местам таким образом, чтобы каждый претендент занимал одно рабочее место и каждое рабочее место было занято лишь одним претендентом, при этом, связанные с распределением затраты должны быть минимальными.
Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов:
1 этап:
1. Формализация проблемы в виде транспортной таблицы.
2. Приведение матрицы (транспортной таблицы):
а) в каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки;
б) повторить ту же процедуру для столбцов.
Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью. Оптимальное значение целевой функции в этом случае равно нулю.
2 этап:
1. Зачёркиваем все нулевые значения в приведённой матрице, таким образом, чтобы число вертикальных и горизонтальных линий (k), зачёркивающие элементы, было минимальным (сколько бы ни было нулевых элементов, зачёркивается вся строка или весь столбец).
2. Высчитываем число k:
Теорема 3: Максимальное число независимых нулей равно минимальному суммарному числу горизонтальных и вертикальных линий - k, которыми можно зачеркнуть все нулевые элементы приведённой матрицы.
3 этап:
1. Найти наименьший из элементов, через которые не проходит ни одна прямая, обозначим этот элемент б.
3. Вычесть его из всех элементов, через которые не проходят прямые.
4. Прибавить его ко всем элементам, лежащим на пересечении двух прямых.
5. Элементы, через которые проходит только одна прямая, оставить неизменными.
В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново, и продолжать до тех пор, пока k не станет равным n.
4 этап:
1. В первую очередь находим строки, в которых всего один нуль, и на место этого нуля в матрице назначений ставим 1.
2. Вычёркиваем строку и столбец, на пересечении которых стоит 1.
3. Далее по тому же принципу выбираем следующий нуль и проделываем тоже самое.
4. Т.к. в матрице назначений в каждой строке и в каждом столбце должна быть всего одна единица - один претендент на одном месте, то если получилось иначе (в строке или столбце две единицы) один из нулей был выбран не верно, необходимо вернуться к началу построения матрицы назначений.
5. Когда матрица назначений построена, мы суммируем элементы исходной матрицы С, соответствующие единичным элементам в матрице назначений. Это и будут минимальные затраты, связанные с распределением.
Рассмотрим пример решения задачи о назначениях:
Задача: Дана исходная матрица С порядка 5Ч5. Найти оптимальный план распределения 5 претендентов на 5 рабочих мест (один претендент должен занимать только одно рабочее место и каждое рабочее место должно быть занято только одним претендентом), причём связанные с этим распределением затраты должны быть минимальными.
1 этап: Приводим матрицу С (т.е. в каждой строке и каждом столбце данной матрицы должен быть хотя бы один нуль). Для этого в каждой строке выбираем минимальный элемент и вычитаем его из остальных. Затем повторяем процедуру для столбцов:
В итоге преобразований получаем приведённую матрицу, обозначим её С0:
2 этап: По теореме 3: обозначим минимальное суммарное число горизонтальных и вертикальных линий через k. В нашем случае оно будет равно k=2 (первая строка и первый столбец).
3 этап: По алгоритму, приведённому в пункте 1.4.1.:
1. Находим наименьший из элементов, через которые не проходит ни одна прямая, б.=1;
3. Вычитаем его из всех элементов, через которые не проходят прямые;
4. Прибавляем его ко всем элементам, лежащим на пересечении двух прямых;
5. Элементы, через которые проходит только одна прямая, оставляем неизменными.
В итоге получаем матрицу
В данном случае k=4<n. Следовательно, по алгоритму переходим опять к 1 пункту 3 этапа (если вдруг, что маловероятно, С1 окажется неприведённой, то возвращаемся к 1 пункту 1 этапа).
В результате получаем матрицу:
В данном случае k=5=n, следовательно, по алгоритму «Венгерского метода» переходим к 4 этапу.
4 этап: В результате действий, описанных в пункте 1.4.1., 4 этап: 1 - 4, получаем матрицу назначений
С помощью суммирования соответствующих элементов исходной матрицы С , делаем вывод:
Вывод
1. Матрица назначений показывает нам оптимальный план распределения.
2. Минимальные затраты на распределение 5 претендентов на 5 рабочих мест будут равны:
L=1+4+2+4+3=14
Задача решена.
3.2 Задача коммивояжера
Задача коммивояжера (коммивояжер - бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешевый, совокупный критерий и т.п.) и соответствующие матрицы расстояний, стоимости и т.п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз - в таком случае выбор осуществляется среди гамильтоновых циклов.
Существует масса разновидностей обобщённой постановки задачи. В частности геометрическая задача коммивояжёра (когда матрица расстояний отражает расстояния между точками на плоскости). Треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра.
Методы решения задачи о коммивояжере:
а) полный лексический перебор;
б) «жадные» алгоритмы:
- метод ближайшего соседа;
- метод включения ближайшего города;
- метод самого дешёвого включения;
в) метод минимального основного дерева.
На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а также алгоритм муравьиной колонии.
Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра - методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые «any-time» алгоритмы, то есть постепенно улучшающие некоторое текущее приближённое решение.
Математическая модель задачи о коммивояжёре:
(33)
при условиях неотрицательности и целочисленности:
Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.
Модель задачи примет вид
(34)
при ограничениях на вместимости отсеков:
при условии неотрицательности:
при условии целочисленности:
Когда для перевозки имеется один отсек и каждый вид продукции может быть взят или нет, то модель задачи принимает вид:
(35)
Решим задачу коммивояжёра с помощью метода ветвей и границ.
Рассмотрим на примере решение задачи коммивояжера:
Задача: Решить задачу коммивояжёра, где n=6.
Начальный рекорд R=?. Подобно задаче о назначениях для начала приведём исходную матрицу С.
Вычисляем S - сумму приводящих констант:
Далее находим Sij : величина Sij равна сумме минимального элемента строки (i) и минимального элемента столбца (j). Далее выбираем максимальное значение Sij . В нашем случае S14.
По правилу обхода дерева рассматриваем два варианта: и , причём из рассмотрения вычёркиваем первую строку и четвёртый столбец. Преобразовываем матрицу согласно выдвинутому утверждению
а)
Приводим матрицу С1
Опять вычисляем Sij и сумму приводящих констант:
б)
Также приводим данную матрицу и находим величины Sij, а также:
По правилу обхода дерева, идём по ветке с наименьшим значением параметра , т.е. и .
Для удобства пропустим несколько следующих итераций, т.к. алгоритм вычисления был рассмотрен выше. В результате получим:
По правилу обхода дерева идём по ветви с минимальным значением . Т.е. С7 будет нашей последней матрицей.
Теперь составляем оптимальное решение задачи коммивояжёра:
Единицы ставятся на те позиции, где в дереве обхода проходит главная ветвь. А последние единичные элементы ставятся в соответствии с матрицей С7 , в данном случае это элементы: и - выбираются с учётом оставшихся элементов в невычеркнутых строка и столбцах, и таким образом, чтобы не образовывался цикл (т.е. чтобы коммивояжер не заходил циклично в одни и те же города).
Вычислим оптимальный план:
Коммивояжер должен двигаться по маршруту:
1 - 4 - 3 - 5 - 6 - 2 - 1
L=16+25+5+5+5+7=63
Величина L вычисляется по тому же принципу, что и в задаче о назначениях.
Задача решена.
3.3 Задача о ранце
Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.
Модель задачи примет вид:
(34)
при ограничениях на вместимости отсеков:
при условии неотрицательности:
при условии целочисленности:
Когда для перевозки имеется один отсек и каждый вид продукции может быть взят или нет, то модель задачи принимает вид:
(35)
Заключение
В данной работе была рассмотрена сущность целочисленного программирования. Затронуты специальные методы решения целочисленных задач. Такие задачи возникают при моделировании разнообразных производственно-экономических, технических, военных и других ситуаций. В то же время ряд проблем самой математики может быть сформулирован как целочисленные экстремальные задачи.
Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. Эти задачи интересны и с математической точки зрения. С появлением ЭВМ, ростом их производительности повысился интерес к задачам такого типа и к математике в целом.
Список литературы
1. А.Схрейвер. Теория линейного и целочисленного программирования: в 2-х томах.; перевод с английского. 1991г. 360с.
2. Т.Ху. Целочисленное программирование и потоки в сетях.; перевод с английского. 1974г.
3. А.В.Кузнецов, В.А.Сакович, Н.И.Холод. Высшая математика: Математическое программирование. Ученик - 2-е издание. 2001г. 351с.
4. В.Г.Карманов. Математическое программирование: Учебное пособие - 5-е издание, стереотип-М:ФИЗМАТ, 2001г.-264с.
5. Е.Г.Белоусов. Введение в выпуклый анализ и целочисленное программирование. М.:Издательство МГУ, 1977г.
6. В.В. Федосеев, А.Н.Гармаш, Д.М.Дайитбегов.: Экономико-математические методы и прикладные модели: Учеб.пособие для вузов/ЮНИТИ, 1999г.-391с.
7. Н.Ш. Кремер, Б.А. Путко, И.М.Тришин, М.Н.Фридман; под ред. Проф.Н.Ш. Кремера.: Исследование операций в экономике; учеб. Пособие для вузов.
8. Ананий В. Левитин: Алгоритмы: введение в разработку и анализ -- М.: «Вильямс», 2006.
9. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ 2-е изд. -- М.: «Вильямс».
10. Парамонов Ф.И. Моделирование процессов производства. - М.: Машиностроение, 1984
11. Рейнгольд Э., Нивергелы Ю., Део Н. Комбинаторные алгоритмы v теория и практика. / Пер. с англ. Под ред. Алексеева. - М.: Мир,1980.
12. Зайченко Ю. П., «Исследование операций», Киев «Высшая школа» 1975г.
13. Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «В ысшая школа» 1993г.
14. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «В ысшая школа» 1980г.
15. Носова С.С. Экономическая теория. - Москва: «Владос», 2003.
Размещено на Allbest.ru
Подобные документы
Описание задачи линейного целочисленного программирования. Общий алгоритм решения задач с помощью метода границ и ветвей, его сущность и применение для задач календарного планирования. Пример использования метода при решении задачи трех станков.
курсовая работа [728,8 K], добавлен 11.05.2011Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
реферат [583,3 K], добавлен 15.06.2010Формы задачи линейного программирования, каноническая форма. Симплекс-метод: теоретические основы, прямой алгоритм; метод Гомори. Математическая и техническая постановка задачи, программная реализация: запуск, графический интерфейс и созданные функции.
курсовая работа [578,7 K], добавлен 04.02.2011Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014Основные методы решения задач линейного программирования. Графический метод, симплекс-метод. Двойственная задача, метод потенциалов. Моделирование и особенности решения транспортной задачи методом потенциалов с использованием возможностей Мicrosoft Excel.
контрольная работа [1,1 M], добавлен 14.03.2014Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.
контрольная работа [158,7 K], добавлен 15.10.2010Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа [268,0 K], добавлен 17.02.2010Универсальный метод решения канонической задачи линейного программирования. Общая схема симплекс-метода, его простейшая реализация на примере. Группировка слагаемых при одинаковых небазисных переменных. Определение координат нового базисного плана.
контрольная работа [49,1 K], добавлен 21.10.2013
