Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
Второй пример линейной оптимизации дает так называемая транспортная задача. Пусть в /-м пункте, 1</^т, отправления
336 ’ -
V,
имеется dt количество груза, в у-м пункте, Ку<л, назначения требуется bj количество этого груза. Пусть cuj—стоимость перевозки единицы груза из z-го в у-й пункт. Предположим, что
т п
Е 4= Е bj,
i= 1 j= 1
т. е. весь груз должен быть вывезен на пункты назначения.
Транспортная задача состоит в поиске x=xitj, 1^у<л,
доставляющего
т, п
штФ(х)= ? ciJxi,j i,j= i
(минимизация транспортных расходов) при естественных условиях
п
Е
7=1
т
i= 1
xi,j ^о.
Размерность неизвестного вектора х в транспортной задаче равна тп. Нетрудно заметить, что получается каноническая форма задачи линейной оптимизации.
8.5.3. Геометрическая интерпретация. Рассмотрим каноническую задачу линейной оптимизации на плоскости: найти
пппФ(х) = (с1х1 +с2х2)
при ограничениях
~^~а\,2Х2 =^1 >
**2,1 *1 ~^~а2,2Х2 =^2?
Хх ^0, Х2^0.
Заметим, что линейная функция Ф(х) = с1х1+с2х2 на плоскости задает семейство прямых (рис. 8.10) уравнением
Неравенства хх ^0, х2^0 выделяют I квадрант плоскости (х1? х2) (рис. 8.10).
Рис. 8.10
337
Ограничения;) в форме равенств могут быть следующего вида:
1) отсутствуют;
2) одно ограничение;
3) два ограничения.
Предположенйе о линейной независимости строк матрицы А эквивалентно в случае двух ограничений существованию единственного, решения системы уравнений
Ах = Ь.
Обозначим решение х = (х19 х2). Если выполняются неравенства
хх^0, х2>0,
то это и есть решение задачи линейной оптимизации, а оптимальное значение равно
Ф (х) = с1х1 + с2х2.
Если выполняются неравенства
хх <0 или х2<0,
то задача неразрешима (рис. 8.11). Заметим, что два линейно независимых ограничения типа равенства (в многомерном случае т=п) приводят к тому, что исходная задача оказывается неоптимизационной. Ограничения однозначно определяют единственное решение х, а целевая функция Ф(л:) принимает «навязанное» ей значение Ф(х).
В рлучае одного ограничения типа равенства, описывающего множество точек на прямой
аххх -\-с12х2 =Ь,
возможны следующие варианты пересечения этой прямой с осями координат I квадранта (рис. 8.12):
1) прямая отсекает два отрезка;
2) прямая отсекает один отрезок;
3) прямая не пересекается с осями.
Если прямая не пересекается с осями координат I квадранта, то задача неразрешима.
Если прямая отсекает один отрезок, то возможны три варианта. Проекция вектора градиента целевой функции gradФ(л:)=(c1, с2):
338 \
777777777^
Рис. 8.12
1) направлена внутрь квадранта;
2) направлена вне квадранта;
3) равна нулю.
Так как вектор градиента направлен в сторону возрастания Ф(х), то нетрудно понять, что в случае 2) целевая функция Ф(х) не ограничена снизу; вдоль прямой а1х1+а2х2=Ь значения Ф(л:) убывают и Ф(л;)->— оо (рис. 8.13). В случае 3) вектор (с1? с2) коллинеарен вектору (а19 а2). Следовательно, для того чтобы выполнялось ограничение, необходимо совпадение прямых Ф(х)=/? и а1х1 + а2х2 = Ь. Отсюда получаем: оптимальными являются все точки пересечения прямой ограничения с прямой Ф(х)=/?, лежащие внутри I квадранта (рис. 8.13). В случае 1), поскольку вектор gradФ(д:) направлен в сторону врзрастания Ф(х), целевая функция Ф(д:) достигает минимального значения, когда прямая Ф(х)=р проходит через точку х пересечения прямой ограничений с осью координат I квадранта (рис. 8.13). Следовательно, оптимальной является единственная точка х.
Если прямая а1х1+а2х2 = Ь отсекает два отрезка на осях координат I квадранта, то в зависимости от направления проекции градиента на эту прямую возможны (рис. 8.14) три варианта:
1) Проекция направлена в сторону точки пересечения с осью Ох2 \ тогда оптимальная точка — точка пересечения с осью Охг. 2) Проекция направлена в сторону точки пересечения с осью Охг; тогда оптимальная точка—это точка пересечения с осью Ох2. 3) Проекция равна нулю; следовательно, прямая Ф(х)=/? должна совпадать
X
Рис. 8.13
339
с прямой ограничения, отсюда оптимальными являются все точки прямой ограничений, лежащие внутри I квадранта (рис. 8.14).
Наконец, если ограничения в форме равенств отсутствуют, то возможны (рис. 8.15) следующие оптимальные решения в зависимости от направления вектора %т<1Ф(х):
1) единственная оптимальная точка хх=0, х2 = 0;
2), 3) бесконечное множество оптимальных точек (оси координат);
4) целевая функция в I квадранте не ограничена снизу.
Результатом геометрических рассмотрений задачи линейной
оптимизации на плоскости являются следующие выводы, которые справедливы и в многомерной задаче.
Линейная целевая функция Ф(д:) может достигать единственного минимума в точке х только на границе области х{^0 (рис. 8.13, 7); функция не достигает минимума (рис. 8.13, 2; 8.15,4), а значит, задача линейной оптимизации неразрешима. Наконец, возможна ситуация наличия бесконечного множества решений (рис. 8.13, 3; 8.14, 3; 8.15, 2, 3).
Мы не будем рассматривать неразрешимые задачи, поскольку в этом случае следует обратиться к технической постановке проблемы, а также задачи с бесконечным множеством решений, так как они неустойчивы. Возмущение коэффициентов сх целевой функции Ф(д:) приводит такую задачу либо к единственной точке минимума, либо к неразрешимой задаче.
