korobov

232

Программа, кроме того, позволяет для каждой итерации вычислять симплексный мультипликатор.

Таким образом, подвергнув задачу нелинейного программирования линеаризации и заложив в программу исходные данные вспомогательной задачи линейного программирования, мы через конечное число итераций получим оптимальное решение.

Программа, листинг которой представлен в нашем издании [2] содержит исходные данные для решения примера, изложенного выше.

Рассмотрим теперь вопросы, которые необходимо учитывать при работе с персональным компьютером в данном случае.

Представленная программа выполнена на языке программирования Бейсик, ориентированном на применении персональных компьютеров IBM и совместимых с ними. Для ввода и выполнения программ и отдельных команд Бейсика необходимо передать управление персональной ЭВМ интерпретатору. Для запуска интерпретатора Бейсика необходима операционная система MS - DOS. Поэтому, прежде всего, следует произвести загрузку этой системы.

Интерпретатор дискового Бейсика находится в файле BASICA.COM, а расширенного - в файле BASIC.COM. Для запуска любого из этих интерпретаторов требуется набрать имя соответствующего файла без расширения СОМ и нажать клавишу "Enter".

Сообщение "Ok", появляющееся на экране дисплея в конце идентификационного сообщения, означает, что интерпретатор готов обрабатывать команды Бейсика.

Программу, помещенную в дисковый файл, можно извлечь и разместить в основной памяти с помощью оператора LOAD, набрав название команды и нажав клавишу "Enter".

LOAD "b : LP"

Команда LIST позволяет вывести на экран программу, находящуюся в памяти машины. В команде LIST можно указать диапазон номеров строк, которые нужно вывести. В нашем случае имеет смысл выводить на экран для редактирования только последние строки программы, в которых представлены исходные данные для конкретной задачи. Поэтому команду LIST следует задавать таким образом

LIST 5000 - или

LIST - - -

После появления на экране строк программы необходимо разместить данные задачи в строках программы, отмеченных оператором ДАТА, который создает список постоянных значений.

В начало массива вводится тип задачи "1" при решении задачи на минимум целевой функции и "-1" при решении задачи на максимум. В следующую строку следует ввести через запятую количество переменных, количество неравенств со знаком "больше или равно", количество неравенств со знаком "меньше или равно". В оставшиеся строки через запятую вводятся коэффициенты при переменных в ограничительных условиях, свободные члены ограничений, коэффициенты целевой функции. После ввода данных в каждую строку программы необходимо нажимать клавишу "Enter", указывая тем самым, что строка закончена.

Если требуется записать программу с новыми исходными данными в дисковый файл, то следует воспользоваться командой SAVE. С ее помощью осуществляется пересылка Бейсик-программ из основной памяти в дисковый файл.

SAVE "b : lp"

Для большинства видов производства целевая функция (6.52) монотонно возрастает и вогнута. В этом случае произведение ϕi(xi)xi берется со знаком минус. Для некоторых же видов производства, например при эксплуатации месторождений полезных ископаемых и т. п., функция (6.52) также монотонно возрастает и выпукла; здесь ϕi(xi)xi берется со знаком плюс. В последнем случае функция имеет единственный минимум, который, однако, не будет являться одним из опорных планов. Оптимальный план может быть любой граничной точкой выпуклого многогранника, определяемого системой ограничений (6.53). В первом случае, когда целевая функция (6.52) вогнута оптимальный план обязательно является одним из опорных планов. Но в этом случае задача имеет множество локальных минимумов, каждый из которых также достигается в некоторой вершине выпуклого многогранника, представляющей некоторый опорный план.

В случае вогнутости целевой функции задача в принципе может быть решена при помощи перебора всех опорных планов с вычислением целевой функции для каждого опорного плана. Однако при достаточно большом числе неизвестных xij такой перебор практически неосуществим ввиду колоссально большого количества вычислений.

Существуют методы решения транспортных задач с выпуклой целевой функцией или с вогнутой при ϕi(xi) = ki, равной постоянной величине. Однако алгоритмы этих

1 Этот способ, предложенный В.В. Шерстобитовым, был доложен на Всесоюзной межвузовской научно-технической конференции, проходившей в июне 1968 года в Московском лесотехническом институте. Нами впервые был опубликован в 1974 г. [9].

методов очень сложные и требуют вычислений большого объема. Поэтому мы рассмотрим лишь весьма простой приближенный способ решения транспортной задачи при любых дифференцируемых однотипных функциях ϕi(xi), при которых целевая функция (6.52) является выпуклой или вогнутой1. Рассмотрим сначала случай вогнутости целевой функции, соответствующий уменьшению производственных затрат на единицу продукции при увеличении ее объема. Этот случай наиболее соответствует действительности.

Для вогнутой функции, заданной на выпуклом множестве, имеет место неравенство

из которого видно, что любой локальный минимум функции f(X) в точке X0 одновременно является локальным минимумом линейной функции f(X0)X в той же точке X0. Значит, и точки абсолютного минимума для этих функций также совпадают. Таким образом, задача абсолютной минимизации функции (6.52) при условиях (6.53) оказывается эквивалентной задаче абсолютной минимизации линейной функции.

235

Однако постоянные коэффициенты cij = ∂f (x0 ) нам неизвестны, поскольку

неизвестна точка Х0, в которой достигается абсолютный минимум функции (6.55). Поэтому для нахождения точки X0 задача решается последовательными сближениями. На первом этапе полагаем ϕi(xi)=0 и решаем линейную транспортную задачу минимизации целевой функции

при ограничениях (6.53). Обозначим оптимальный план этой задачи через X 0(1) . На втором

и таким образом получаем оптимальный план X0(2) . Таким же образом перейдем от X0(2) к третьему оптимальному плану X0(3) .

Этот процесс очень быстро сходится к некоторому опорному плану X 0 , который

и принимается за решение задачи.

Проверка эффективности способа на ряде примеров показывает, что указанные сближения приводят к точному абсолютному минимуму целевой функции (6.52), в случае если матрица размеров mxn

имеет существенно различные по величине элементы. Если элементы матрицы А постоянны (особенно по строкам) или относительно мало различаются, то указанный процесс может сходиться к локальному минимуму, отличному от абсолютного. Однако в этом случае целевая функция изменяется относительно мало и полученный локальный минимум, не совпадающий с абсолютным минимумом, может приниматься за хороший приближенный результат.

Применение указанного процесса сближения для выпуклой функции, как правило, не сходится к одному опорному плану. Здесь обычно получается цикл повторяющихся опорных планов и за приближенное решение задачи принимается тот опорный план в цикле, который дает наименьшее значение целевой функции (6.52). Если процесс сближений сойдется к одному опорному плану, то это будет означать, что абсолютный минимум находится в одной из вершин выпуклого многогранника и мы получаем (в силу единственности решения для выпуклой функции) точное решение задачи. Для ускорения сходимости к циклу опорных планов следует на первом этапе минимизировать линейную форму

236

где

Рассмотрим решение задачи на конкретном числовом примере. Требуется решить задачу о размещении производства при уменьшении затрат на выпуск единицы продукции при исходных данных, представленных в табл.6.5.

В этом примере функция ϕi(xi) принимается постоянной. Целевая функция задачи является вогнутой, как сумма вогнутых функций.

На первом этапе решаем транспортную задачу открытого типа с объемом

cij=ci(0)+tij. Результат решения приведен в следующей табл. (6.6).

237

Переходим ко второму этапу вычислений.

Вычисляем частные производные [составляющие вектора f(X0)] целевой функции

где

j=1

Частные производные от этой функции имеют следующий вид:

квадратиках в левых верхних углах клеток.

238

При проверке оптимальности опорного плана потенциалы поставщиков с действительными поставками фиктивному потребителю принимаются равными нулю.

На втором этапе заканчивается решение задачи, так как получено распределение, совпадающее с распределением на первом этапе. Опорный план x21=10, x23=10, x41=40, x53=40, x62=40, x63=10, остальные xij=0, является оптимальным, при этом получаются наименьшие суммарные затраты на производство и транспортировку продукции, которые можно подсчитать подстановкой полученного решения в выражение целевой функции (6.61), что предоставляется сделать читателю.

В табл. 6.7 видно, что строить предприятие в пунктах А1 и А3 нецелесообразно, так как в этих пунктах объемы производства хi казались равными нулю. Предприятия в пунктах А4, А5, А6 должны работать на полную мощность, а в пункте А2 на 2/3 полной мощности.

Далее рассмотрим эту же задачу, т.е. с теми же исходными данными, но с выпуклой целевой функцией:

В этом случае производственные затраты на единицу продукции возрастают с увеличением объема производства.

На первом этапе решаем транспортную задачу со стоимостями поставок

В табл.6.9 приведен результат решения транспортной задачи со стоимостями поставок лесопродукции, заданными табл.6.8.

Табл. 6.9

По данному распределению рассчитаем стоимости поставок (фиктивные)

и с этими стоимостями поставок решим задачу на втором этапе. Результат решения на втором этапе приведен в табл. 6.10.

Получилось распределение отличное от распределения на первом этапе.

Снова рассчитываем фиктивные стоимости поставок по формулам (6.65) при

3

данных xi = ∑xij и хij в последней таблице и решаем транспортную задачу. Результат ее

j=1

решения приведен в табл.6.11.

Табл. 6.10

240

Табл. 6.11

Табл. 6.12