Задачи целочисленного программирования реферат

Обновлено: 30.06.2024

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Решение задач целочисленного линейного программирования
в табличном процессоре Excel

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

Содержание лабораторной работы

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

Пусть – количество тракторов марки , – марки , которые планируется приобрести, – общие затраты на новую технику.

Математическая модель задачи представлена следующим образом:

Для решения ЗЛП в процессоре Excel необходимо:

Занесём данные задачи и формулы целевой функции и ограничений в ячейки:

Заполним математическую модель:

Получено следующее оптимальное решение:

Отчёт по результатам:

В ответе получились целые значения: , . Значение целевой функции находится в ячейке E4: .

Таким образом, оптимальным будет вариант, при котором приобретаются 4 трактора марки и 9 тракторов марки .

Затраты на новую технику составят 86 ден. ед.

Получено следующее оптимальное решение:

В результате получили решение: , . Значение целевой функции находится в ячейке E4: .

Как видно, ответ получился не целочисленным (значения и не целые числа).

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

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

Выбор, например, переменной , порождает две подзадачи, связанные с условием или или .

Так как , имеем две подзадачи 1.1 и 1.2 (обозначения вершин дерева ветвления):

Порождённые подзадачи содержат все допустимые целочисленные решения исходной задачи, т. е. исходное множество допустимых целочисленных решений остаётся неизменным в процессе ветвления.

В результате решения подзадачи 1.1 получили решение: , . Значение целевой функции находится в ячейке E4: .

В результате решения подзадачи 1.2 получили решение: , . Значение целевой функции находится в ячейке E4: .

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

Проведём ветвление вершины 1.1. Как видно, ответ получился не целочисленным (значения не целое число). Выбор переменной порождает две подзадачи: 2.1 и 2.2 с дополнительными ограничениями соответственно, т. е. или .

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

В результате решения подзадачи 2.2 получили решение: , . Значение целевой функции находится в ячейке E4: .

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

Итак, найдено оптимальное решение задачи: , .

К нему привела цепочка задач: .

Таким образом, оптимальным будет вариант, при котором приобретаются 4 трактора марки и 9 тракторов марки . Затраты на новую технику составят 86 ден. ед.

Изобразим схематически ход решения задачи.

Значение целевой функции: .

пустое множество допустимых решений.

, . Значение целевой функции: .

Каковы особенности задачи целочисленного линейного программирования?

Целочисленное программирование – раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности.

Какие методы решения задачи целочисленного линейного программирования Вы знаете?

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

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

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

Что является первым оптимальным решением, организующим процесс ветвления?

Сначала решается задача линейного программирования без учёта условий целочисленности. Если полученное оптимальное решение оказывается допустимым для целочисленной задачи, то его следует зафиксировать как наилучшее. Иначе задача разбивается на две подзадачи.

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

Математическая модель задачи целочисленного линейного программирования имеет вид:

Здесь Z – множество целых чисел. Если , то задачу называют полностью целочисленной, если , то частично целочисленной.

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

Рубрика	Экономико-математическое моделирование
Вид	курсовая работа
Язык	русский
Дата добавления	10.08.2013
Размер файла	1,8 M

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

КУРСОВАЯ РАБОТА

1. Теоретическая база. Методы решения

1.1 Графический метод решения задач

1.2 Метод Гомори

1.3 Метод ветвей и границ

1.4 Дискретное программирование

1.4.1 Задача о назначениях

1.4.2 Задача коммивояжёра

1.4.3 Задача о рюкзаке

1.5 Динамическое программирование

1.5.1 Задача о распределении ресурсов

1.5.2 Выбор транспортных маршрутов

2. Решения задач целочисленного программирования

2.1 Метод Гомори

2.2 Метод ветвей и границ

2.3 Дискретное программирование

2.3.1 Задача о назначениях

2.3.2 Задача коммивояжёра

2.4 Динамическое программирование

2.4.1 Задача о распределении ресурсов

2.4.2 Выбор транспортных маршрутов

3. Теоретические выводы

3.1 Графический метод

3.2 Метод Гомори

3.3 Метод ветвей и границ

3.4 Дискретное программирование

3.4.1 Задача о назначениях

3.4.2 Задача коммивояжёра

3.4.3 Задача о рюкзаке

3.5 Динамическое программирование

Целочисленное программирование - раздел математического программирования, занимающийся решением задач в которых все или некоторые переменные принимают целочисленные значения.

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

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

Основными задачами данной курсовой работы является:

1. Анализ и получение оптимальных решений;

2. Выявление проблем, связанных с получением оптимального решения;

3. Проработка всех направлений целочисленного программирования.

Используемые методы для анализа:

- метод ветвей и границ;

- методы динамического программирования;

1. Теоретическая база. Методы решения

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

Разделим задачи целочисленного программирования на классы:

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

- Другим важным классом таких задач являются экстремальные комбинаторные задачи, переменные которых носят логический характер (х=0 или х=1). Такие переменные называются булевыми. К таким задачам относятся, например, задача выбора некоторого подмножества, обладающего какими-либо экстремальными свойствами.

- Задачи, не требующие явного условия целочисленности, но сводящиеся к задачам целочисленного или частично целочисленного программирования.

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

1. Построение математической модели;

2. Решение математической модели выбранным методом;

3. Анализ полученных данных и принятие решения.

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

- Формализация целевой функции приведена в формуле (1.1)

- Наложение ограничений показано в формулах (1.2).

В зависимости от условий конкретной задачи могут быть введены дополнительные ограничения на отдельные переменные, которые могут быть выражены, например, формулой (1.3)

где d_j, D_j - свободные коэффициенты.

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

- графический метод решения задач;

- метод ветвей и границ;

- и другие методы в зависимости от класса решаемых задач.

Рассмотрим методы решения задач целочисленного программирования:

1.1 Графический метод решения задач

Пусть заданы некоторые данные, которые сводятся к следующей математической модели.

Целевая функция и ограничения приведены в формулах 1.1.1 и 1.1.2.

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

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

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

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

1.2 Метод Гомори

Данный метод основан на симплексном методе.

Исходные данные приведены в формулах (1.2.1) и (1.2.2).

На первом этапе данная задача решается симплекс-методом, если полученное решение не целочисленное, то вводим дополнительное ограничение, которые должны быть:

- отсекать найденный оптимальный не целочисленный план;

- не должно отсекать ни одного целочисленного плана.

Дополнительное ограничение обладающие этими свойствами называются правильным отсечением[2].

Ограничение накладывается на нецелочисленную переменную или на ту переменную, которая имеет большее дробное значение. Ограничение накладывается на не целочисленную переменную через не основные переменные. Ограничение составляется используя следующее правило: дробная часть свободного члена берётся с тем же знаком, который он имеет и в уравнении, а дробные части неосновных переменных - с противоположным знаком и выделяется положительная дробь. Например, =a, =, где А - целая часть отрицательное число, а * -положительная дробь.

Получаем новое ограничение, вводим новую основную переменную, приведённое в формуле (1.2.3).

где x_n₊₁ - нововведённая переменная,

x_j _- переменные не входящие в базис.

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

Полученное базисное решение всегда не допустимое, соответствующее правильному отсечению.

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

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

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

Если в процессе решения появится выражение с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и данная задача не имеет целочисленного оптимального решения[2].

1.3 Метод ветвей и границ

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

Рассмотрим построение математической модели и не посредственно этапы решения задач данным методом.

Исходные данные полностью соответствуют данным метода Гомори формулы (1.2.1) и (1.2.2).

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

где [x_j * ] - целая часть нецелочисленного значения переменной x_j * в оптимальном решении без учёта целочисленности.

Затем решаются ещё две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных (1.3.1).

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

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

- На одной из ветвей недопустимое решение;

- На одной из ветвей целочисленное решение. Тогда значение целевой функции сравнивается с граничное (верхним при max, нижним при min); если полученное значение хуже, оно отбрасывается, если лучше, то принимается за граничное;

- На одной из ветвей нецелочисленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается[4].

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

1.4 Дискретное программирование

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

Основными задачами демонстрирующими сущность дискретного программирования являются:

- задача о назначениях;

1.4.1 Задача о назначениях

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

Спецификой данной задачи является одинаковое количество представляемого ресурса и источников его использования.

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

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

Каждый сотрудник имеет определённые требование выраженные по шкале от 1 до 10 обозначим их за C_ij в связи, с которыми заполняется матрица n?n относительно рабочего места требований сотрудника.

В данной задаче используются булева переменная для назначения i - работника на j - место показанная в формуле (1.4.1.1)

где i=1,2. n - множество работников

j =1,2. n - множество рабочих мест.

Таким образом, составляется матрица n?n и решается выбранным методом.

1.4.2 Задача коммивояжёра

В задаче коммивояжёра с n городами можно определить такие переменный приведённые в формуле (1.4.2.1).

Имея значения C_ij - расстояние от города i до города j (считается, что C_ij=? при i=j), задачу коммивояжёра можно формализовать следующим образом, показанную в формуле (1.4.2.2)

При ограничениях, показанных в формулах (1.4.2.3)

Решения должно быть полным циклом[5].

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

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

Применение метода ветвей и границ для решения задачи коммивояжера.

Решения задачи данным методом, можно представить следующим алгоритмом:

1. На первом этапе решается задача о назначениях. Полученное решение принимается за нижнюю границу нахождения решения задачи коммивояжёра. За верхнюю границу можно принять сумму элементов С₁₂+С₂₃+С₃₄+..+С_n₁.

Если на первом этапе получен цикл, то его принимают за оптимальное решение задачи коммивояжёра.

2. Иначе чтобы исключить частные циклы в полученном решении принудительно приравниваются x_ij, задающие этот цикл, к бесконечности (например, если цикл состоит из 2 переменных, то приравнивается лишь одна переменная к бесконечности).

Выбирая для удаления короткий цикл, получаем на дереве подзадач две ветви. Новые задачи о назначениях строятся путём удаления из последней задачи переменной ветвеления, что уменьшает размер подзадач[5].

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

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

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

1.4.3 Задача о рюкзаке

В общем виде этот тип задач может быть описан следующим образом.

Имеется n позиций, каждую из которых можно либо выбрать (x_i=1), либо нет (x_i=0). Выбор i-позиции требует затрат ресурса в количестве a_i. Общее количество имеющегося в распоряжении ресурса равно b. Эффект отбора i-й позиции есть c_i. Следует осуществить выбор среди позиций, допустимый в смысле затрат ресурсов, и имеющий максимальный суммарный эффект[6].

Математическая модель представляет собой следующие исходные данные, представленные в формулах (1.4.3.1) и (1.4.3.2):

Решением данной задачи максимальный суммарный эффект. Который может быть найден с помощью следующих методов и алгоритмов:

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

- Алгоритм полного перебора.

Жадный алгоритм представляет из себя следующий алгоритм:

- Выбрать максимально эффективный предмет, то есть значение ci

- Упорядочить предметы по эффективности (от большего к меньшему), и наполнять рюкзак по мере его наполнения.

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

Так же данная задача может быть разделена в зависимости от того сколько раз может использоваться предмет:

- неограниченное количество раз.

Рассмотрим алгоритмы динамического программирования.

1.5 Динамическое программирование

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

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

К задачам динамического планирования относятся:

- задача распределения ресурсов;

- разработка правил управления запасами;

- выбор транспортных маршрутов;

- разработка принципов календарного планирования производства.

Рассмотрим некоторые задачи и методы их решения.

1.5.1 Задача о распределении ресурсов

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

Тогда введём обозначение:

х_i - количество ресурса, выделенных i - предприятию,

g_i(x_i) - функция полезности, в данном случае это величина дохода от использования ресурса х_i,

f_k - наибольший доход, который можно получить при использовании ресурсов x от первых k различных предприятий.

Сформулированную задачу можно записать в математической форме, которая представлена в формулах (1.5.1.1) и (1.5.1.2):

Для решения данной задачи необходимо получить рекуррентное соотношение, связывающее f_n(x) и f_n_-1(x).

Обозначим x_k, количество ресурса, используемого k-м способом (0?x_n?х), тогда для (k-1) способов остаётся величина ресурсов, равная (x-x_n). Наибольший доход, который получается при использовании ресурса (x-x_n) от первых (n-1) способов, составит f_n_-1(x-x_n).

Для максимизации суммарного дохода от n-ого и первых (n-1) способов необходимо выбрать x_k таким образом, чтобы выполнялись следующие соотношения:

То есть, рассматривая n-шаговый процесс, приходим к основному функциональному уравнению Беллмана, устанавливающему связь между F_k и F_k_-1.

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

1.5.2 Выбор транспортных маршрутов

Рассмотрим алгоритм обратной прогонки, который может быть формализован в следующем виде в формуле (1.5.2.1):

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

2. Решения задач целочисленного программирования

2.1 Метод Гомори

Фирма выпускает три вида изделий x1, x2, x3, причём плановый выпуск составляет 9 шт. изделий х1, 7 шт. изделий х2, 6 шт. изделий х3.

Прибыль от реализации изделий х1 - 40 условных единиц, х2 - 50 условных единиц, х3 - 10 условных единиц.

Читайте также: