Решение задачи линейного программирования
Листинг 6.6. Решение задачи линейного программирования
Модель типичной транспортной задачи следующая. Пусть имеется N предприятий-производителей, выпустивших продукцию в количестве b0, ... ,bN-1 тонн. Эту продукцию требуется доставить м потребителям в количестве а0, ... „аM-1 тонн каждому. Численное определение векторов а и b находится в первой строке листинга. Сумма всех заказов потребителей ai равна сумме произведенной продукции, т. е. всех bi (проверка равенства во второй строке). Если известна стоимость перевозки тонны продукции от i-го производителя к j-му потребителю Ci,j, то решение задачи задает оптимальное распределение соответствующего товаропотока xi,j с точки зрения минимизации суммы транспортных расходов. Матрица с и минимизируемая функция f (х) матричного аргумента х находятся в середине листинга 6.6.
Условия, выражающие неотрицательность товаропотока, и равенства, задающие сумму произведенной каждым предприятием продукции и сумму заказов каждого потребителя, находятся после ключевого слова Given. Решение, присвоенное матричной переменной sol, выведено в последней строке листинга вместе с соответствующей суммой затрат. В строке, предшествующей ключевому слову Given, определяются нулевые начальные значения для х простым созданием нулевого элемента матрицы xN-1,M-1.
Примечание 1
Примечание 1
Если взять другие начальные значения для х, решение, скорее всего, будет другим! Возможно, вы сумеете отыскать другой локальный минимум, который еще больше минимизирует транспортные затраты. Это еще раз доказывает, что задачи на глобальный минимум, к классу которых относится линейное программирование, требуют аккуратного отношения в смысле выбора начальных значений. Часто ничего другого не остается, кроме сканирования всей области начальных значений, чтобы из множества локальных минимумов выбрать наиболее глубокий.
Примечание 2
Примечание 2
Не забывайте о том, что в вычислительном блоке в качестве неизвестных следует использовать все компоненты вектора х, как это сделано в предпоследней строке листинга 6.6 (с/и. разд. 5.1.1). Иными словами, нельзя задавать некоторые из компонент х в виде параметров.
Примечание 3
Примечание 3
Еще раз напомним, что в новых версиях Mathcad (начиная с 11-й) появилась возможность программного управления глобальной минимизацией. Для этого служит параметр численного алгоритма Multistart (Сканирование), который следует установить в положение Yes (Да) для поиска глобального экстремума (см. разд. 5.3.2). Любопытно, что если при решении нашей задачи поменять только эту опцию функции Minimize, то численный метод даст сбой, и вместо решения появится сообщение об ошибке. Однако если вспомнить, что наша транспортная задача — линейная, и выставить в контекстном меню, вызываемом на имени функции Minimize, флажок Linear (Линейный), задающий линейный вариант алгоритма, то глобальное решение будет найдено.
