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

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

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

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

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

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

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

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

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

При ограничениях

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

- Жадный алгоритм;

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

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

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

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

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

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

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

- один раз;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при ограничениях

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

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

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

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

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

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

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

где Fn(xn)=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):

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

X1=(0,0,0,51,48,67)

F1=-770;

X2=(0,12,0,27,0, 31)

F2=-170;

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

F3=127,

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

F3=194.

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

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

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

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

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

Bi {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) - который является не допустимым решением. Вводим в базис либо х4 либо х5, для этого выражаем их через не основные переменные и получаем уравнения (2.2.9)

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

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

Для полного анализа наложим ограничения на x2 и x3.

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

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

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

Х*=(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.

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

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

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

Задача №2.

х2 - увеличиваем, х1,3=0

 

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

X2=(0,12,0,27,0,31,10); F2=-170

Основные переменные - х2, х4, х6, х7, н\о - х1, х3, х5

F(х1, х3, х5)=-170+27,5x1+10x3-12,5x5

x1 - увеличиваем, х3,5=0

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

X3=(10; 9,5; 0; 2; 0; 8,5; 0); F3=105

Основные переменные - х1, х2, х4, х6, н\о - х3, х5, х7

F(х3, х5, х7)=105+10x3-27,5x7-12,5x5

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

X4=(10; 9,5; 8,5; 2; 0; 0; 0); F4=190

Основные переменные - х1, х2, х3, х4, н\о - х5, х6, х7

F(х5, х6, х7)=190-5x5-10x6-5x7

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

Задача №3.

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

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

х2 - увеличиваем, х3,7=0

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

X2=(11,9,0,0,1,7,0); F2=80

Основные переменные - х1, х2, х5, х6, н\о - х3, х4, х7

F(х3, х4, х7)=80+10x3-25x4-35x7

x3 - увеличиваем, х5,7=0

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

X3=(11; 9; 7; 0; 1; 0; 0); F3=190

Основные переменные - х1, х2, х3, х5, н\о - х4, х6, х7

F(х4, х6, х7)=190-10x4-10x6-20x7

Fграничное=190.

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

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

Задача №4.

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

х2 - увеличиваем, х1,3=0

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

X2=(0,9,0,33,12,40,10,0); F2=-320

Основные переменные - х2, х4, х5, х6, х7, н\о - х1, х3, х8

F(х1, х3, х8)=-320+40x1-50x8+10x3

x1 - увеличиваем, х3,8=0

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

X3=(10; 9; 0; 3; 2; 10; 0); F3=80

Основные переменные - х1, х2, х4, х5, х6, н\о - х3, х7, х8

F(х3, х7, х8)=80 +10x3-40x7-50x8

x3 - увеличиваем, х3,8=0

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

X4=(10; 9; 10; 21; 2; 0; 0; 0); F4=190

Основные переменные - х1, х2, х4, х4, х6, н\о - х3, х7, х8

F(х3, х7, х8)=190-10x6-10x7-20x8

F4=Fграничное.

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

Задача №5.

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

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

Основные переменные - х2, х4, х5, х6, х7, н\о - х1, х3, х8

x1 - увеличиваем, х3,8=0

 

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

X2=(8,10,0,7,0,13,2,0); F2=50

Основные переменные - х1, х2, х4, х6, х7, н\о - х3, х5, х8

F(х3, х5, х8)=50+10x3-40x5-110x8

x3 - увеличиваем, х5,8=0

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

X3=(10; 10; 7; 1; 0; 10; 0); F3=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

Х верхнее граничное= С12+С23+С34+ С45+С51=10+5+7+4+3=29

Xt1=x31+ x42+ x13+ x54+ x25= (x13+ x31)+( x25+ x54+ x 42)

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

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

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

x13=?

Х2=17 Xt2= x31+ x52+ x43+ x14+ x25=( x14+ x43+ x31)+( x25+ x52)

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

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

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

x13=?; x25=?

Х3=21 Xt3= x31+ x52+ x23+ x14+ x45=x14+ x45+ x52+x23+ x31

Полученное решение Х3< Х верхнее граничное=> Х верхнее граничное:=Х3

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

x13=?; x52=?

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

Х4=19 Xt4= x31+ x42+ x53+ x14+ x25=x14+ x42+ x25+x53+ x31.

Полученное решение Х4< Х верхнее граничное=> Х верхнее граничное:=Х4

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

x31=?

Х5=16 Xt5= x51+ x42+ x13+ x34+ x25= x13+ x34+ x42+ x25+ x51

Полученное решение Х5< Х верхнее граничное=> Х верхнее граничное:=Х5

Ответ: Х*=Х5=16; Xt5= x13+ x34+ x42+ x25+ x51

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

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

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

Х6=17 Xt6= x52+ x45+ x13+ x31+ x24= (x13+ x31)+( x24+ x45+ x52)

Х7=16 Xt7= x51+ x42+ x13+ x34+ x25= x13+ x34+ x42+ x25+ x51

Х8=17 Xt8= x52+ x45+ x13+ x31+ x24= (x13+ x31)+( x24+ x45+ x52)

Х9=22 Xt9= x52+ x43+ x15+ x31+ x24= x15+ x52+ x24+ x43+ x31

Х10=21 Xt10= x53+ x42+ x14+ x31+ x25= x14+ x42+ x25+ x53+ x31

Х11=23 Xt11= x51+ x43+ x14+ x32+ x25= x14+ x43+ x32+ x25+ x51

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