Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.
В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:
· задачи линейного программирования, если f(X) и W линейны;
· задачи целочисленного программирования, если ставится условие целочисленности переменных Х1, Х2,…, Хn;
· задачи нелинейного программирования, если форма f(X) носит нелинейный характер.
Задачи линейного программирования.
Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
f(X) = å СjXj ® max(min);
å aij xj = bi, iÎI, IÍM = {1, 2,…m};
å aij xj £ bi, iÎM;
Xj³0, jÎJ, JÍN = {1, 2,…n}.
При этом система линейных уравнений и неравенств, определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией или критерием оптимальности.
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот.
Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
4) если некоторая переменная Хk не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными::
Xk = X`k – Xl, где l – свободный индекс, X`k ³ 0, Xk ³ 0.
3.2. Постановка задачи линейного программирования
Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), но n потребителям этих ресурсов.
На автомобильном транспорте часто встречаются следующие задачи, относящиеся к транспортным:
· прикрепление потребителей ресурса к производителям;
· привязка пунктов отправления к пунктам назначения;
· взаимная привязка грузопотоков прямого и обратного направлений;
· отдельные задачи оптимальной загрузки промышленного оборудования;
· оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями.
Транспортным задачам присущи следующие особенности:
· распределению подлежат однородные ресурсы;
· условия задачи описываются только уравнениями;
· все переменные выражаются в одинаковых единицах измерения;
· во всех уравнениях коэффициенты при неизвестных равны единице;
· каждая неизвестная встречается только в двух уравнениях системы ограничений.
Транспортные задачи могут решаться симплекс-методом.
3.3. Решение транспортной задачи
| Мощности постав- щиков 140 | Мощности потребителей | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7/15 | 14 | 8/5 | 7/10 | 0 |
| 40 | 12 | 8 | 10 | 8/40 | 15 | 0 |
| 25 | 6/18 | 10 | 10 | 12 | 14/7 | -7 |
| 45 | 16 | 10 | 8/32 | 12 | 16/13 | -9 |
| Vj | -1 | 7 | -1 | 8 | 7 | |
Начальное распределение выберем по методу наименьших стоимостей. Порядок заполнения клеток: (3,1), (1,2), (4,3). (2,4), (1,5), (1,4), (3,5), (4,5)
Суммарные затраты:
f(x) = 6´18+7´15+8´32+8´5+8´40+7´10+14´7+16´13=1107
Рассмотрим процесс нахождения потенциалов для данного распределения.
Положим, Ui=0 Þ V2=U1+C12=7; V5=U1+C15=7=U3+14=U4+16 Þ U3= -7, U4= -9; V3=U4+C43= -1; V4=U2+8=U1+8 Þ U2=U1=0; V4=8.
Найдем оценки: dij=(Ui+cij)-Vj:
11 0 15 0 0
(dij) = 13 1 11 0 8
0 -4 4 -3 0
8 -6 0 -5 0
Данный план не является оптимальным, т.к. есть отрицательные оценки.
Построим контур перераспределения для клетки (4,2). Наименьшая поставка в вершине контура со знаком “-” равна 13, поэтому проведем перераспределение поставок, уменьшив поставки в клетках со знаком “-” на 13 и увеличив поставки в клетках со знаком “+” на 13. результаты поставлены в таблице 2.
| Мощности постав- щиков 140 | Мощности потребителей | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7/2 | 14 | 8/5 | 7/23 | 0 |
| 40 | 12 | 8 | 10 | 8/40 | 15 | 0 |
| 25 | 6/18 | 10 | 10 | 12 | 14/7 | -7 |
| 45 | 16 | 10/13 | 8/32 | 12 | 16 | -3 |
| Vj | -1 | 7 | 5 | 8 | 7 | |
Суммарные затраты:
f(x) = 6´18+7´2+10´13+8´32+8´5+8´40+7-23+14-7=1127
Положим U1=0
V2 = U1+C12=7=U4+10 Þ U4 = -3
V3 = U4+8=5; V4=U1+8=8=U2+8 Þ U2=0
V5 = U1+7= 7 = U3+14 Þ U3= -7
V1 = U3+6= -1
dij = (Ui+Cij)-Vj
9 0 9 0 0
(dij) = 11 1 5 0 8
0 -3 -2 -3 0
14 0 0 1 6
Наличие отрицательных оценок свидетельствует о том, что план не является оптимальным. Построим контур перераспределения для клетки (3,2). Наименьшая поставка в вершине контура со знаком “-” равна 2. Произведем перераспределение поставок. Результаты представим в таблице 3.
| Мощности постав- щиков 140 | Мощности потребителей | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7 | 14 | 8/5 | 7/25 | 0 |
| 40 | 12 | 8 | 10 | 8/40 | 15 | 0 |
| 25 | 6/18 | 10/2 | 10 | 12 | 14/5 | -7 |
| 45 | 16 | 10/13 | 8/32 | 12 | 16 | -7 |
| Vj | -1 | 7 | 5 | 8 | 7 | |
Суммарные затраты:
f(x) = 6´18+10´2+10´13+8´32+8´5+8´40+7´25+14´7=1119
Положим, U1=0 Þ V4=8, V5=7; V4=U2+8 Þ U2=0
V5 = U3+14 Þ U3= 7-14= -7; V1= -7+6= -1; V2= -7+10= +3
V2=U4+10 Þ U4=3-10= -7; v3= -7+8=1
9 4 13 0 0
(dij) = 13 5 9 0 8
2 0 2 -3 0
10 0 0 -3 2
Наличие отрицательных оценок свидетельствует о том, что план не является оптимальным. Построим контур перераспределения для клетки (3,4).
Наименьшая поставка в клетке со знаком “-” равна 5. Произведем перераспределение поставок результаты представим в таблице 4.
| Мощности постав- щиков 140 | Мощности потребителей | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7 | 14 | 8 | 7/30 | 0 |
| 40 | 12 | 8 | 10 | 8/40 | 15 | 0 |
| 25 | 6/18 | 10/2 | 10 | 12/5 | 14 | -4 |
| 45 | 16 | 10/13 | 8/32 | 12 | 16 | -4 |
| Vj | 2 | +6 | 4 | 8 | 7 | |
Суммарные затраты: