Квазилинейное программирование и обобщенная транспортная задача

Задача Линейного программирования может быть поставлена так: нужно минимизировать или максимизировать функцию являющуюся линейной формой определенной на многомерном выпуклом многограннике который задается системой линейных уравнений. Квазилинейное программирование отличается от линейного тем, что необходимо минимизировать вогнутую или максимизировать выпуклую функцию, а не линейную форму. Для обеих задач можно доказать, что экстремум достигается в крайних (угловых) точках выпуклого многогранника. Так как количество крайних точек в выпуклом многограннике конечно, то задача сводится к комбинаторной. Отличие заключается в том, что экстремум линейной формы является глобальным, а экстремум вогнутой или выпуклой функции —локальным. Обобщенная транспортная задача является частным случаем задачи квазилинейного программирования. Необходимо минимизировать транспортные расходы для перевозки товаров из пунктов производства (истоки) в пункты потребления (стоки). Задача о нахождении расстояния между функциональными распределениями на графах соседства (частными случаями графа соседства являются многомерные решетки) может быть сведена к обобщенной транспортной задаче. Для этого достаточно из начального функционального распределения вычесть конечное. В тех вершинах графа где разница положительная — определены истоки, а там где отрицательная — стоки. Количество производимой и потребляемой продукции равно разнице между функциональными распределениями по абсолютной величине. Мы покажем, что стоимость перевозки может зависеть от расстояния между истоками и стоками только в виде степенного закона. Причем, если выгодна перевозка сразу в конечный пункт назначения без промежуточных пунктов, тогда показатель степени должен лежать между нулем и единицей. Аналогичный степенной закон распространяется и на количество перевозимого товара.