Целочисленное программирование

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

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

на тему: «Целочисленное программирование»

Содержание

Введение

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}=a, {-a}={-A+a^*}, где А - целая часть отрицательное число, а^*-положительная дробь.

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

где x_n+1 - нововведённая переменная,

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 городов. По существу, это задача является задачей о назначениях с дополнительными ограничениями, которые гарантируют исключение из оптимального решения неполных замкнутых маршрутов (в задаче коммивояжёра замкнутый маршрут, проходящий через каждый пункт только один раз, называется циклом цикл, проходящий через все пункты, называется полным, в противном случае - частичным или подциклом).

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

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

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

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

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

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

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

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

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

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

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):

где F_n(x_n)=0.

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

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

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

Задача:

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

Сменные ресурсы: 51 ед. производственного оборудования, 48 ед. сырья, 67 ед. электроэнергии, их расход на одно изделие дано в «таблице 2.2.1».

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

Таблица 2.2.1

Ресурсы	Изделие х1	Изделие х2	Изделие х3
Оборудование	3	2	0
Сырьё	1	4	0
Электроэнергия	3	3	1

Определить, сколько изделий каждого вида надо производить, чтобы получить максимальную прибыль от выпускаемых сверх плана изделий[3].

Формализуем данные и получаем целевую функцию, приведённую в формуле (2.2.1):

(2.2.1)

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

То получаем следующую целевую функцию, показанную в формуле (2.2.2):

При системе ограничений (2.2.3):

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

X₁=(0,0,0,51,48,67)

F₁=-770;

X₂=(0,12,0,27,0, 31)

F₂=-170;

X₃=(10,8; 9,3; 0; 0; 0; 6,7)

F₃=127,

X₃=(10,8; 9,3; 6,7; 0; 0; 0)

F₃=194.

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

Полученное решение нас не удовлетворяет, так как переменные не целочисленные.

Для получения целочисленного решения выражаем переменные х₁, х₂, х₃ через не основные переменные и получаем систему уравнений (2.2.4):

Так как получились все 3 переменные дробными, можно накладывать ограничения на любую переменную. Накладываем на х₁ ограничение при соблюдении всех правил построения.

Таким образом

B_i {10,8}={10+0,8}=0,8;

{0,4}=0,4;

{-0,2}={-1+0,8}=0,8.

Получаем новое ограничение предложенное в уравнение (2.2.5).

Меняем знак на противоположный и добавляем новую переменную - уравнение (2.2.6).

Вводим полученное ограничение в систему ограничений последнего этапа симплекс-метода (2.2.8)

Получаем вектор X=(10,8; 9,3; 6,7; 0; 0; 0; -0,8) - который является не допустимым решением. Вводим в базис либо х₄ либо х₅, для этого выражаем их через не основные переменные и получаем уравнения (2.2.9)

Выбираем х₅, так как оно даёт при подстановке целые числа на первом этапе, и получаем систему уравнений (2.2.10).

Ответ: X^*=(11,9,7,0,1,0,0), так как нужно выявить сверхплановое производство получаем ответ X^*'=(2,2,1) при значении целевой функции равной F=190.

Для полного анализа наложим ограничения на x₂ и x₃.

Наложим ограничения на x₂ и получим:

Х^*=(11,9,7, 0,1,0,0); F=190

Наложим ограничения на x₃ и получим:

Х^*=(8,9,13, 7,0,0,0); F=130

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

Берём ту же задача что и в методе Гомори, с теми же исходными данными, то есть уравнения (2.2.2), (2.2.3). Данная задача разделяется поэтапно на задачу 1, 2, 3, 4, 5.

Задача №1.

Решаем симплекс-методом и получаем оптимальное решение.

X^*=(10,8; 9,3; 6,7; 0; 0; 0)

F^*=194.

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

Накладываем согласно правилу два ограничения на x₁ предложенные в уравнениях (2.3.1), (2.3.2).

Решаем симплекс-методом со всеми исходными данными и новым ограничением (2.3.1) новую задачу.

Задача №2.

х₂ - увеличиваем, х_1,3=0

х₂ - себя исчерпало и переход в основные переменные

X₂=(0,12,0,27,0,31,10); F₂=-170

Основные переменные - х₂, х₄, х₆, х₇, н\о - х₁, х₃, х₅

F(х₁, х₃, х₅)=-170+27,5x₁+10x₃-12,5x₅

x₁ - увеличиваем, х_3,5=0

x₁ - себя исчерпало и переход в основные переменные

X₃=(10; 9,5; 0; 2; 0; 8,5; 0); F₃=105

Основные переменные - х₁, х₂, х₄, х₆, н\о - х₃, х₅, х₇

F(х₃, х₅, х₇)=105+10x₃-27,5x₇-12,5x₅

x₃ - себя исчерпало и переход в основные переменные

X₄=(10; 9,5; 8,5; 2; 0; 0; 0); F₄=190

Основные переменные - х₁, х₂, х₃, х₄, н\о - х₅, х₆, х₇

F(х₅, х₆, х₇)=190-5x₅-10x₆-5x₇

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

Задача №3.

Решим симплекс методом задачу с условием (2.3.2).



Не допустимое решение, вводим вместо х₇ в базис х₁.

х₂ - увеличиваем, х_3,7=0

х₂ - себя исчерпало и переход в основные переменные

X₂=(11,9,0,0,1,7,0); F₂=80

Основные переменные - х₁, х₂, х₅, х₆, н\о - х₃, х₄, х₇

F(х₃, х₄, х₇)=80+10x₃-25x₄-35x₇

x₃ - увеличиваем, х_5,7=0

x₃ - себя исчерпало и переход в основные переменные

X₃=(11; 9; 7; 0; 1; 0; 0); F₃=190

Основные переменные - х₁, х₂, х₃, х₅, н\о - х₄, х₆, х₇

F(х₄, х₆, х₇)=190-10x₄-10x₆-20x₇

F_{граничное}=190.

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

В задаче №2 мы получили ответ частично целочисленный, поэтому накладываем ограничения на х₂, которые предложены в формулах (2.3.3) и (2.3.4).

Задача №4.

Решаем симплекс-методом со всеми исходными данными, ограничением (2.3.1) и новым ограничением (2.3.3) новую задачу.

х₂ - увеличиваем, х_1,3=0



x₂ - себя исчерпало и переход в основные переменные

X₂=(0,9,0,33,12,40,10,0); F₂=-320

Основные переменные - х₂, х₄, х₅, х₆, х₇, н\о - х₁, х₃, х₈

F(х₁, х₃, х₈)=-320+40x₁-50x₈+10x₃

x₁ - увеличиваем, х_3,8=0

x₁ - себя исчерпало и переход в основные переменные

X₃=(10; 9; 0; 3; 2; 10; 0); F₃=80

Основные переменные - х₁, х₂, х₄, х₅, х₆, н\о - х₃, х₇, х₈

F(х₃, х₇, х₈)=80 +10x₃-40x₇-50x₈

x₃ - увеличиваем, х_3,8=0

x₃ - себя исчерпало и переход в основные переменные

X₄=(10; 9; 10; 21; 2; 0; 0; 0); F₄=190

Основные переменные - х₁, х₂, х₄, х₄, х₆, н\о - х₃, х₇, х₈

F(х₃, х₇, х₈)=190-10x₆-10x₇-20x₈

F₄=F_{граничное}.

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

Задача №5.

Решаем симплекс-методом со всеми исходными данными, ограничением (2.3.1) и новым ограничением (2.3.4) новую задачу.

Не допустимое решение, вводим вместо х₈ в базис х₂.

Основные переменные - х₂, х₄, х₅, х₆, х₇, н\о - х₁, х₃, х₈

x₁ - увеличиваем, х_3,8=0

x₁ - себя исчерпало и переход в основные переменные

X₂=(8,10,0,7,0,13,2,0); F₂=50

Основные переменные - х₁, х₂, х₄, х₆, х₇, н\о - х₃, х₅, х₈

F(х₃, х₅, х₈)=50+10x₃-40x₅-110x₈

x₃ - увеличиваем, х_5,8=0

x₃ - себя исчерпало и переход в основные переменные

X₃=(10; 10; 7; 1; 0; 10; 0); F₃=200

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

Ответ: X^*1=(11,9,7) F^*=190 - решение задачи № 3, X^*1'=(2,2,1);

X^*2=(10,9,10) F^*=190 - решение задачи № 4, X^*2'=(2,2,1).

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

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

Задачи данного типа рассмотрены в рамках дисциплины «методы оптимизации». Решение данных задач осуществляется венгерским методом, так как он имеет преимущество переде другими методами в виде простоты и меньшего затраченного времени.

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

Дана матрица расстояния между i и j городами.

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

Рассмотрим задачу №1

Min(6,2,3,1,4,1)=1

X_{нижняя граница} =4+1+3+5+2=15

Х _{верхнее граничное}= С₁₂+С₂₃+С₃₄+ С₄₅+С₅₁=10+5+7+4+3=29

X_t1=x₃₁+ x₄₂+ x₁₃+ x₅₄+ x₂₅= (x₁₃+ x₃₁)+( x₂₅+ x₅₄+ x ₄₂)

То есть получили частные циклы (1-3-1) и (2-5-4-2). Так как частный цикл (1-3-1) меньше рассмотрим его.

Разделим исходную задачу на 2 подзадачи, принудительно присвоив значения переменных в первой задаче x₁₃=?, а во второй x₃₁=?.

Рассмотрим задачу №2.

x₁₃=?



Х₂=17 X_t2= x₃₁+ x₅₂+ x₄₃+ x₁₄+ x₂₅=( x₁₄+ x₄₃+ x₃₁)+( x₂₅+ x₅₂)

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

Разделим исходную задачу на 2 подзадачи, принудительно присвоив значения переменных в первой задаче x₂₅=?, а во второй x₅₂=?.

Рассмотрим задачу №3.

x₁₃=?; x₂₅=?

Х₃=21 X_t3= x₃₁+ x₅₂+ x₂₃+ x₁₄+ x₄₅=x₁₄+ x₄₅+ x₅₂+x₂₃+ x₃₁

Полученное решение Х₃< Х _{верхнее граничное}=> Х _{верхнее граничное}:=Х₃

Рассмотрим задачу №4.

x₁₃=?; x₅₂=?



Min(5,3,4,1,2)=1

Х₄=19 X_t4= x₃₁+ x₄₂+ x₅₃+ x₁₄+ x₂₅=x₁₄+ x₄₂+ x₂₅+x₅₃+ x₃₁.

Полученное решение Х₄< Х _{верхнее граничное}=> Х _{верхнее граничное}:=Х₄

Рассмотрим задачу №5.

x₃₁=?

Х₅=16 X_t5= x₅₁+ x₄₂+ x₁₃+ x₃₄+ x₂₅= x₁₃+ x₃₄+ x₄₂+ x₂₅+ x₅₁

Полученное решение Х₅< Х _{верхнее граничное}=> Х _{верхнее граничное}:=Х₅

Ответ: Х^*=Х₅=16; X_t5= x₁₃+ x₃₄+ x₄₂+ x₂₅+ x₅₁

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

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

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

Х₆=17 X_t6= x₅₂+ x₄₅+ x₁₃+ x₃₁+ x₂₄= (x₁₃+ x₃₁)+( x₂₄+ x₄₅+ x₅₂)

Х₇=16 X_t7= x₅₁+ x₄₂+ x₁₃+ x₃₄+ x₂₅= x₁₃+ x₃₄+ x₄₂+ x₂₅+ x₅₁

Х₈=17 X_t8= x₅₂+ x₄₅+ x₁₃+ x₃₁+ x₂₄= (x₁₃+ x₃₁)+( x₂₄+ x₄₅+ x₅₂)

Х₉=22 X_t9= x₅₂+ x₄₃+ x₁₅+ x₃₁+ x₂₄= x₁₅+ x₅₂+ x₂₄+ x₄₃+ x₃₁

Х₁₀=21 X_t10= x₅₃+ x₄₂+ x₁₄+ x₃₁+ x₂₅= x₁₄+ x₄₂+ x₂₅+ x₅₃+ x₃₁

Х₁₁=23 X_t11= x₅₁+ x₄₃+ x₁₄+ x₃₂+ x₂₅= x₁₄+ x₄₃+ x₃₂+ x₂₅+ x₅₁

Так как нижняя граница Х₅= Х₇=16= Х _{верхнее граничное} все другие планы является не оптимальными и дальнейшее их рассмотрение приведёт лишь к увеличению значения целевой функции.

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

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

Данная задача была разобрана в рамках дисциплины «методы оптимизаций».

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

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

Исходные данные приведены на «рисунке 1.5.2.1».



Рисунок 1.5.2.1

Разделим данную схему на этапы, показанную на «рисунке 1.5.2.2».

Рисунок 1.5.2.2

Рассмотрим, начиная с конечного пункта все расстояния до пункта отправления в «таблицах 1.5.2.1, 1.5.2.2, 1.5.2.1», основывая вычисления F_i(x_i) на формуле (1.5.2.1).

Таблица 1.5.2.1

x2	d(x2,x3)	Оптимальное решение
	x3=7	F2(x2)	x3*
5	6	6	7
6	4	4	7

Таблица 1.5.2.2

x1	d(x1,x2)	Оптимальное решение
	x2=5	x2=6	F1(x1)	x2*
2	4+6	-	10	5
4	7+6	3+4	7	6
3	-	6+4	10	6

Таблица 1.5.2.3

x0	d(x0,x1)	Оптимальное решение
	x1=2	x1=4	x1=3	F0(x0)	x1*
1	3+7	2+7	3+7	9	4

Полученное оптимальный маршрут с минимальными затратами показан на «рисунке 1.5.2.3»

Рисунок 1.5.2.3

Таким образом, маршрут будет выглядеть следующим образом 1>4>6>7.

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

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

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

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

Метод впервые был предложен в 1957-1958 годах Р. Гомори.

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

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

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

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

Метод ветвей и границ был предложен Лендом и Дойгом в 1960 году.

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

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

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

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

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

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

Задачи данного типа были разобраны в рамках дисциплины «методы оптимизаций».

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

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

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

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

Таким образом, в зависимости от прерогатив путника, могут быть выбраны альтернативные маршруты.

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

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

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

Задачи данного типа относятся к детерминированным моделям с рекуррентным алгоритмом прямой и обратной прогонки.

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

Заключение

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

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

- специфика задачи влечёт за собой выбор метода решения данной задачи;

- полученное оптимальное решение может быть не единственным;

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

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

- сложность формализации;

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

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

Основными методами целочисленного программирования являются:

- метод Гомори;

- метод ветвей и границ, который взаимно дополняют друг друга.

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

1. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Целочисленное программирование: Учебник/ Под ред. Н. П. Бусленко. - М.: Мир, 1977. - 424 с.

2. Кремер Н.Ш., Путко Б.А. и др. Исследование операций в экономике: Учебное пособие для вузов/ Под ред. Н.Ш. Кремер. - М.: Юнити, 2003. - 407 с.

3. Красс М.С., Чупрынов Б.П. Основы математики и её приложение в экономическом образовании: Учебник/ - М.: Дело, 2000 - 688 с.

4. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента: Учебное пособие/ 3-е изд., стер. - СПб.: Лань, 2007 - 528 с.

5. Таха, Хемди А. Введение в исследование операций: Учебник/ Пер. с англ. - 7-е издание - М.: Вильямс, 2005. - 912 с.

6. Косоруков О.А., Мищенко А.В. Исследование операций: Учебник/ Под ред. Н.П. Тихомирова. - М.: Экзамен, 2003. - 448 с.

Приложение

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