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

5.Лекция. Целочисленное программирование.

5. 1 Постановка задачи целочисленного программирования.

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

Задача целочисленного программирования формулируется следующим образом: 

Найти такое решение план Х=(х₁, х₂,…, х_n), при котором линейная функция  принимает максимальное или минимальное значение при ограничениях

  

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

Понятия о методе ветвей и границ.

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

Рекомендуемые материалы

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

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

5.2 Графический метод решения задач целочисленного программирования.

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

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

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

1.Оно должно быть линейным;

2.Должно отсекать найденный оптимальный не целочисленный план;

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

Алгоритм графического решения задачи целочисленного программирования.

1.Построить систему координат x₁0х₂ и выбрать масштаб.

2.Найти область допустимых решений (ОДР) системы ограничений задачи.

3.Построить целевую функцию, являющуюся линией уровня и на ней указать направление нормали.

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

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

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

6.Выделить у этих координат область с целочисленными значениями.

7.Определить новые координаты и построить граф.

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

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

  Условие задачи.

Решить методом ветвей и границ задачу, имеющую следующую математическую модель.

Решение:

1.Находим координаты точек каждого линейного уравнения системы ограничений и строим прямые

     1 прямая: 3х₁+2х₂=1

-если х₁=1, то 2х₂=12, х₂=6

-если х₂= 0, то 3х₁=12, х₁=4

      2 прямая: 2х₁+5х₂=20

-если х₁=0, то 5х₂=20, х₂=4;

-если х₂=0, то 2х₁=20, х₁=10

2.Находим ОДР.

Так как х₁, х₂ ≥ 0, то область будет ограничен прямыми ОХ₁ и ОХ₂ и построенными прямыми (см. рис.1).

3.Находим координаты точек целевой функции и строим прямую целевой функции:

7х1+4х2=0

- первая точка х₁=0; х₂=0

- вторая точка х₁=4, х₂=(-7).

4.Перемещаем прямую целевой функции по направлению через ОДР до тех пор, пока она не станет касательной к ней, и находим точку А₀.

5.Находим координаты точек А₀  и значение целевой функции в ней:

Х1=1,8; х2=3,27;

Z=7×1,8+4×3,27=12,6+13,08=25,68

Получен не целочисленный оптимальный план

6.выделим область относительно точки А₀ беря целые значения                1 ≤ х₁ ≤ 2; 3 ≤ х₂ ≤ 4.

Получим координаты точек по границе этой области:

А₁ (1;3,6) А₂ (2;3); А₃ (0;4); А₄ (1;3); А₅ (0;3); А₆ (1;0); А₇ (2;0).

7.Строим граф (рис.2)

8.Для точек с целыми значениями их координат (искомые значения х₁ и х₂)находим значения целевой функции:

Для точки А₂ (2;3) Z₂= 7×2+4×3=26

Для точки А₃ (0;4) Z₃= 7×0+4×4=16

Для точки А₄ (1;3) Z₄= 7×1+4×3=19

Для точки А₅ (0;3) Z₅= 7×0+4×3=12

Для точки А₆ (1;0) Z₆= 7×1+4×0=7

Для точки А₇ (2;0) Z₇= 7×2+4×0=14

Так как максимальное значение целевой функции находится для точки А2 (2;3), то она и будет оптимальным целочисленным решением задачи.

Ответ: Z=26; х₁=2; х₂=3.

                          5.4.      Задача коммивояжера.

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

 Задана матрица расстояний между городами c_ij.

Сформулированная задача - задача целочисленная. Пусть х_ij = 1 , если путешественник переезжает из i -ого города в j-ый и х_ij = 0, если это не так.

Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.

Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u₁ = 0, u_n+1 = n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x_ij и переменные u_i. ( u_i целые неотрицательные числа).

2. Математическая модель

5.5. Пример решения задачи.

Условия задачи:

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

  Матрица расстояний c_ij между городами задана таблицей:

Решение задачи.

          Составляем математическую модель задачи.

Z_min=19х₁₂+25х₁₃₊11х₁₃₊37х₂₁+26х₂₃+58х₂₄+10х₃₁+50х₃₂+39х₃₄+38х₄₁+39х₄₂+24х₄₃

                   х₁₂+х₁₃+х₁₄=1                                  х₂₁+х₃₁+х₄₁=1

                   х₂₁+х₂₃+х₂₄=1                            х₁₂+х₃₂+х₄₂=1

             х₄₁+х₄₂+х₃₄=1                                  х₁₃+х₂₃+х₄₃=1

             х₂₁+х₂₃+х₂₄=1                            х₁₄+х₄₂+х₃₄=1        

                                   U₁ - U₂ + 4х₁₂   <  3                          

                                    U₁ –U₃ + 4х₁₃   <   3

                                    U₁ – U₄+ 4х₁₄  <  3

                                    U₂ – U₃ + 4х₂₃  <  3                                   

                                    U₂ –U₄ + 4х₂₄   <   3

                                    U₃ – U₂+ 4х₃₂  <  3

                                    U₃ – U₄ + 4х₃₄  <  3

                                    U₄ – U₂ + 4х₄₂   <  3                          

                                    U₄ –U₃ + 4х₄₃   <   3

                                    U₄ – U₁+ 4х₄₁  <  3

                                    U₃ – U₁ + 4х₃₁  <  3                                   

                                    U₂ –U₁ + 4х₂₁   <   3

                                              

                                                 0,

                                    Х_ij=        -  ЦЕЛЫЕ ,

                                                 1                                                                                                                             

где:

Z_min  - минимальный маршрут посещения городов;

c_ij    -  расстояние между городами  ij ;

U_i    - номер посещения i – го города.

Строим граф посещения городов с учетом возможных маршрутов движения коммивояжера.

    Граф посещения городов:

                    

                    19 

                          25                11                                                              

        58                                      50       39                                        24           39

26

39           24                           58                 39                                   50              26    

                               

38     10                              38                37                                    37                10

122     111                         171                140                               122                  86   

где:

--- расстояние между городами;

--- расстояние, пройденное по маршруту;

"34. Характеристика солончаков, солонцов и солодей." - тут тоже много полезного для Вас.

--- расстояние, пройденное по минимальному маршруту.

Номер города 

Ответ:

Минимальный маршрут:  1 --- 4  --- 2 --- 3 --- 1 .

Минимальное расстояние – 86 ед.