- •ОГЛАВЛЕНИЕ
- •ВВЕДЕНИЕ
- •1. ВВЕДЕНИЕ В ЗАДАЧИ ОПТИМИЗАЦИИ
- •1.1. Функции одной переменной
- •1.2. Функции многих переменных
- •ЗАДАЧИ
- •2. КЛАССИЧЕСКАЯ ЗАДАЧА МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
- •2.1. Задачи оптимизации при отсутствии ограничений
- •2.2. Метод множителей Лагранжа
- •ЗАДАЧИ
- •3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
- •3.1. Постановка задачи
- •3.3. Методы решения задач нелинейного программирования
- •3.4. Градиентные методы оптимизации
- •3.5. Квадратичные методы оптимизации
- •3.6. Учет ограничений в градиентных методах оптимизации
- •3.7. Последовательный симплексный метод
- •3.10. Методы случайного поиска
- •3.11. Глобальный поиск
- •3.12. Многокритериальные задачи
- •ЗАДАЧИ
- •4. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
- •4.1. Постановка задачи
- •4.2. Двойственные задачи ЛП
- •4.3. Методы решения задач линейного программирования
- •ЗАДАЧИ
- •5. СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- •5.1. Транспортные задачи
- •5.2. Задачи целочисленного программирования
- •5.3. Задача выбора вариантов
- •5.4. Дискретное программирование
- •5.5. Задача коммивояжера
- •ЗАДАЧИ
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Given
|
|
n |
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
k |
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
x0 j |
|
|
b0 |
|
|
|
x1 j |
|
b1 |
|
xi 0 |
|
|
d0 |
xi 1 |
|
d1 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
j 0 |
|
|
|
|
|
|
|
|
j 0 |
|
|
|
|
|
|
i 0 |
|
|
|
|
|
i 0 |
|
|
|
|
|
|||
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xi 2 |
|
|
|
d2 |
|
|
|
x 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
i 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x0 MinimizeQ1( x) |
|
|
|
40 |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
Q1(x0) 335 |
|
|
|
x0 |
25 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
0 |
|
30 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
%В системе Matlab |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
A1=[1 |
1 |
1 |
0 |
0 |
|
0;0 |
0 |
0 |
1 |
1 |
1;1 |
0 |
0 |
1 |
0 |
0;0 |
1 |
0 |
0 |
1 |
0;0 |
0 |
1 |
0 |
0 |
1]; |
||||||
b1=[70;30;40;55;5]; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c=[2;6;3;5;3;1];xmin=zeros(6,1);
[x,Q]=linprog(c,[],[],A1,b1,xmin)
ris51
Optimization terminated.
x=
40.0000
25.0000
5.0000
0.0000
30.0000
0.0000
Q = 335.0000
Рис. 5.1. Окончание
5.2.Задачи целочисленного программирования
Во многих задачах линейного программирования переменные являются неделимыми на части величинами. Так, предприятие не может выпустить 7.5 самолета, 4.8 турбины и т.п. В этом случае задача целочисленного программирования записывается в виде
n |
|
|
|
Q(x) c |
x j extr, |
(5.11) |
|
j |
j |
x X |
|
|
|
||
|
|
|
115
n |
|
|
bi ,i , m |
|
aij x j |
|
|||
j |
|
|
|
|
|
j |
x j d j , j , n |
|
|
X d |
|
|||
x |
j |
целые для j , n |
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если n n , то задачу называют полностью целочисленной, иначе - |
||||
частично целочисленной. Здесь d j , d j |
- нижняя и верхняя граница перемен- |
ной x j .
Геометрически допустимое множество задачи целочисленного программирования может быть представлено выпуклым многогранником OABCD (рис. 5.2). Решение задачи может быть в любой вершине данного многогранника, либо на любой его грани.
А |
x |
|
|
|
|
4 |
|
|
|
В |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
2 |
|
|
|
|
C |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
D x |
0 |
1 |
2 |
3 |
4 |
5 |
Рис. 5.2. Графическое представление задачи целочисленного программирования
Очевидно, можно попытаться решить задачу, не считаясь с условием целочисленности, как непрерывную задачу. Если решение целочисленно, например, вершины D, O, то это и будет решением задачи.
Можно найденное для непрерывного случая решение (вершины А, В, С) округлить до ближайшего целого, удовлетворяющего ограничениям. Однако при этом может получиться решение, далекое от оптимального.
Для получения точного результата можно воспользоваться методом ветвей и границ. Суть метода в следующем [4].
Задача целочисленного программирования решается без учета целочисленности. Далее рассматривают одну из переменных x*j , на которую на-
116
ложено ограничение целочисленности, но которая в результате решения получила дробное значение. На основе полученного решения составляют дополнительные ограничения:
x j x j и x j x j ,
где x j - целая часть нецелочисленного значения переменной x j в опти-
мальном решении, и затем решаются еще две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных.
Полученное решение новых задач проверяют на целочисленность переменных. Если решение не удовлетворяет требованию целочисленности, на основе каждой из задач составляют, аналогично предыдущим, две новые и т.д.
Если одно из решений удовлетворяет требованию целочисленности, значение целевой функции принимается за граничное Qгр . При этом рас-
смотрение других задач продолжается до тех пор, пока не будет получено:
на одной из ветвей недопустимое решение;
на одной из ветвей целочисленное решение. Тогда значение целевой функции сравнивается с Qгр (верхним – при max, нижним – при min); если
полученное значение хуже, оно отбрасывается; если лучше, то принимается за граничное;
на одной из ветвей нецелочисленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается.
На первом цикле расчета
для задачи максимизации,
Qгр для задачи минимизаци и.
Таким образом, для получения целочисленного решения методом ветвей и границ приходится решать большое число задач линейного программирования, причем в каждом очередном ветвлении число ограничений увеличивается на 1. Поэтому время решения задачи целочисленного программирования по сравнению с непрерывной значительно увеличивается.
Пример 5.1.
Q(x) x x max,
x X
x x , |
||
|
|
|
X x x , |
||
x , x |
|
целые. |
|
|
117
Решение. В результате решения задачи симплекс-методом ЛП найдем
оптимальное решение: x , |
x . , |
Q . , где верхний индекс пере- |
|
|
|
менных — номер задачи. |
|
|
В полученном решении |
x . |
— нецелочисленное. Поэтому для |
дальнейшего решения составляем две новые задачи с различными граничными условиями.
Задача 2.
Q(x) x x max,
x X
x x , |
|||
|
|
|
|
X x x , |
|||
x , |
x |
|
. |
|
|
|
Задача 3.
Q(x) x x max,
x X
x x , |
||
|
, |
|
X x x |
||
x , x |
|
. |
|
|
Результаты решения симплекс-методом ЛП задачи 2: x . ; x ;
Q . ; задачи 3: x . ; x ; L . .
В задаче 1 переменная x — целочисленная, а в последующих задачах, при целочисленности x , x перестала быть целочисленной. Затем следует накладывать ограничения целочисленности на x и т.д. (рис. 5.2).
Результаты решения непрерывной и целочисленной задач сводятся в таблицу 5.2. В качестве оптимального принимается решение задачи 5, которое дает наибольшее значение целевой функции для целочисленных решений.
|
|
|
|
|
|
|
|
Таблица 5.2 |
|
|
|
|
Выбор лучшего решения |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
N задачи |
x |
x |
Q |
N задачи |
|
x |
x |
|
Q |
1 |
1 |
7,5 |
29,5 |
5 |
|
2 |
5 |
|
29 |
4 |
1 |
7 |
28 |
6 |
|
0 |
9 |
|
27 |
118