Алгебраические уравнения > Линейное программирование   

Линейное программирование

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

Модель типичной транспортной задачи следующая. Пусть имеется N предприятий-производителей, выпустивших продукцию в количестве b₀,…,b_N-1 тонн. Эту продукцию требуется доставить M потребителям в количестве a₀,…,a_M-1 тонн каждому.  Сумма всех заказов потребителей a_i равна сумме произведенной продукции, т. е. всех b_i . Если известна стоимость перевозки тонны продукции от i-го производителя к j-му потребителю с_ij, то решение задачи задает оптимальное распределение соответствующего товаропотока x_ij с точки зрения минимизации суммы транспортных расходов. Матрица C и минимизируемая функция затрат f(x) 

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

Внимание!
Если Вы возьмете другие начальные значения для x, решение, скорее всего, будет другим! Возможно, что Вы сумеете отыскать другой локальный минимум, который еще больше минимизирует транспортные затраты. Это еще раз доказывает, что задачи на глобальный минимум, к классу которых относится линейное программирование, требуют аккуратного отношения в смысле выбора начальных значений. Часто ничего другого не остается, кроме сканирования всей области начальных значений, чтобы из множества локальных минимумов выбрать наиболее глубокий.