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

1. Построить систему координат x12 и выбрать масштаб.

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

1 прямая: 1+2х2=1

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

если х2= 0, то 1=12, х1=4

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

если х1=0, то 2=20, х2=4;

если х2=0, то 1=20, х1=10

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

 

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

 

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

7х1+4х2=0

- первая точка х1=0; х2=0

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

 

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

 

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

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

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

 

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

 

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

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

А1 (1;3,6) А2 (2;3); А3 (0;4); А4 (1;3); А5 (0;3); А6 (1;0); А7 (2;0).

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

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

 

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

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

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

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

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

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

 

 

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

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

 

 

 

 

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

 

 

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

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

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

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

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

 

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

 

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

 

 

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

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

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

 

Номер города
 
 
 
 

 

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

 

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

 

Zmin=19х12+25х13+11х13+37х21+26х23+58х24+10х31+50х32+39х34+38х41+39х42+24х43

 

х121314=1 х213141=1

х212324=1 х123242=1

х414234=1 х132343=1

х212324=1 х144234=1

 

U1 - U2 + 4х12 < 3

U1 –U3 + 4х13 < 3

U1 – U4+ 4х14 < 3

U2 – U3 + 4х23 < 3

U2 –U4 + 4х24 < 3

U3 – U2+ 4х32 < 3

U3 – U4 + 4х34 < 3

U4 – U2 + 4х42 < 3

U4 –U3 + 4х43 < 3

U4 – U1+ 4х41 < 3

U3 – U1 + 4х31 < 3

U2 –U1 + 4х21 < 3

 

0,

 

Хij= - ЦЕЛЫЕ ,

 

где:

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

 

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

 

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

 

 

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

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

 

 
2
4
  4
 
 
 
 
  4
  3
 
 
 
 
 
 
 

 

 

25 11

 

58 50 39 24 39

 

39 24 58 39 50 26

 

38 10 38 37 37 10

 

 

122 111 171 140 122 86

 

 

где:

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

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

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

Номер города

 

Ответ:

 

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

 

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

Контрольные вопросы.

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

2. Математическая модель задачи целочисленного программирования, ее особенности.

3. Метод ветвей и границ и его применение.

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

5. Как построить граф целочисленной области возможных решений задачи?

6. Как определить целочисленный план и экстремальное значение целевой функции?

7. Сформулируйте задачу о коммивояжере.

8. Какие экономико-математические модели могут быть сведены к задаче о коммивояжере ?

9. Как построить математическую модель задачи о коммивояжере ?

10. Как называются переменные в математической модели задачи о коммивояжере ?

 

 

6.Лекция. Динамическое программирование.

 

Постановка задачи.

 

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

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

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

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

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

 

Решение на каждом шаге называется «шаговым управлением».

 

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

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

 

Требуется найти такое управление (х), при котором выигрыш обращался бы в максимум:

F(x)=

Где F – выигрыш за операцию;

Fi(xi) – выигрыш на i-м шаге;

х – управление операцией в целом;

хi – управление на i-м шаге (i=1,2,…,m). В общем случае шаговые управления 1, х2, … хm) могут стать числами, векторами, функциями.

 

То управление (х*), при котором достигается максимум, называется оптимальным управлением. Оптимальность управления состоит из совокупности оптимальных шаговых управлений х* = х*1, х*2, … х*m

F* = max {F*(х*)} – максимальный выигрыш, который достигается при оптимальном управлении х*.

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