Метод потенциалов — один из наиболее распространенных методов решения транспортной задачи. В США этот метод называют модифицированным распределительным методом, или сокращенно МОДИ. Некоторое различие между этими методами заключается в том, что вместо разности потенциалов, с которыми оперируют в методе потенциалов, принимают в методе МОДИ их сумму.Экономический смысл потенциалов сводится к следующему. Если план перевозок оптимален, то можно присвоить грузам в пунктах отправления Л,- и в пунктах назначения Ej соответственно потенциалы иь и vh при которых перевозка из любого пункта отправления в любой пункт назначения не могла бы дать «прибыль» (учитывая, что оценка груза в любом пункте потребления не должна превышать оценки его в любом пункте производства с учетом расходов по перевозке в пункт потребления) и чтобы в то же время перевозки, внесенные в план, являлись безубыточными (оценка груза в пункте производства плюс издержки по его перевозке должны в точности покрываться оценкой груза в пункте потребления).Составление нового варианта плана начинают с определения той переменной, которой соответствует наибольшее значение d,-.,. В нашем случае это клетка (4.1). За счет за-гружепия этой клетки можно снизить себестоимость перевозок.
С этой целью для клетки, по которой можно получить максимальное снижение себестоимости и которая называется перспективной клеткой, строится контур.
Контур, или цепь, представляет собой замкнутый многоугольник, все углы которого прямые и одной из вершин его является незагруженная клетка, для которой и строится контур. Все остальные вершины —загруженные клетки. Построим такую цепь (рис. 25). Для того чтобы ее построить, необходимо от незагруженной клетки 13 подняться по столбцу Бг до загруженной клетки 1, затем под углом в 90° провести отрезок прямой по строке Л i до загруженной клетки 2, после чего опуститься под углом 90° по столбцу £>2 Д° клетки 6, повернуть под углом 90° по строке Л2 до клетки 7, далее по столбцу £3до клетки 15 и, повернув еще раз па 90°, пройдя по строке Л4, замкнуть контур. Полученный контур имеет 6 вершин, 5 из них загружены.
Метод наименьших (наибольших) значений. При составлении отправной программы по методу наименьших (наибольших) значений разыскиваем в матрице (табл. 47) минимальное значение (оценку) при решении задачи па минимум и наибольшее значение при решении задачи па максимум. В данном примере задача решается на минимум и наименьшее значение находится в клетке (3.1).
На пересечении строки А и столбца Б в этой клетке помещаем максимально возможную поставку — 70 тыс. т, полностью удовлетворяющую потребность в строительных материалах потребителя Б ь и поэтому первый столбец из дальнейшего рассмотрения исключаем. Затем в оставшихся клетках матрицы снова находим минимальный элемент (2.3) и в эту клетку помещаем максимальную поставку — 80 тыс. т. Очевидно, что вторая строка должна быть исключена после этого из рассмотрения, так как теперь полностью потреблена вся продукция завода. Снова находим минимальный элемент из оставшихся — (3.3); даем в эту клетку максимальную поставку 180 тыс. т9 равную разности между мощностью завода в 250 тыс. т, уже запланированной поставкой А$Би равной 70 тыс. mt и исключаем третью строку из матрицы. Опять в оставшейся части ищем минимум. Следующая по величине стоимость равна 4 и находится она в клетке (4.1). Но при первом же шаге потребность площадки Б{ была удовлетворена и поэтому оценки первого столбца были исключены из рассмотрения. Далее загружаем клетку (1.2), оценка по которой равна 5. Для этого помещаем в клетку максимальную поставку в 120 тыс. т, равную мощности завода Aiy и исключаем из дальнейшего рассмотрения первую строку. Для того же примера себестоимость перевозок по исходному плану, составленному по методу северо-западного угла, равнялась 37(30 тыс. руб., т. е. была примерно па 12% выше и только после второй итерации была получена стой-, мость, примерно равная приведенной выше (3150тыс. руб.).
Таким образом, оптимальный план при улучшенном исходном варианте уменьшает число итераций.
Дальнейший ход решений ведется по одному из методов, предложенных ниже.
Для решения транспортной задачи в матричной форме существуют различные методы (потенциалов, дифференциальных рент, разрешающих слагаемых).
Перечисленные методы, наиболее часто используемые для решения транспортных задач, основаны на принципах: 1) последовательного улучшения плана (потенциалов) 2) последовательного сокращения невязок, именуемых также методами условно-оптимальных планов (дифференциальных рент, разрешаемых слагаемых).
Трудоемкость решения транспортной задачи во многом определяется рациональностью построения начального (отправного, базисного) плана. От того, как построен начальный план, зависит количество шагов (итераций), необходимых для получения оптимального решения задачи.Диагональный метод, или метод северо-западного угла.
Этот метод описан в литературе одним из первых. Он дает возможность построить базисный план, отличающийся тем, что число корреспонденции (пунктов перевозок грузов) должно быть равно m + п — 1, гдеяг — число поставщиков, an — число потребителей.
Достоинством диагонального метода является его строгая формализации, но первоначальное распределение весьма далеко от оптимального, что увеличивает число итераций при решении задачи.
Рассмотрим построение плана этим методом на примере. Исходные данные систематизируем в табл. 47.
В клетках табл. 47 поставлена стоимость перевозок, принятая в качестве критерия оптимальности. Задача заключается в получении такого плана перевозок, при котором себестоимость перевозок будет минимальна.
Заполнение матрицы исходного плана начинаем с левого верхнего угла и постепенно по диагонали подходим к правому нижнему углу. Количество заполненных (загруженных) клеток, как указано выше, должно быть равно m + п — 1 = 7.
Начинаем заполнение с левой верхней клетки табл. 48, клетка 1. В левом верхнем углу каждой клетки проставлен ее номер, а в правом верхнем — стоимость перевозок.
План перевозок, обращающий в минимум суммарные транспортные издержки, называется оптимальным планом.
План задачи X будем называть опорным, если система векторов Plt у, соответствующая всем коммуникациям, по которым согласно X намечены положительные перевозки, линейно независима. Систему векторов опорного плана, соответствующих положительным перевозкам, назовем базисом этого плана.
В том случае, если в качестве критерия оптимальности в решении транспортной задачи принимается минимум грузооборота (в Ткм), то транспортная задача может быть решена в двух формах — сетевой и матричной.
При сетевой форме решения задачи вычерчивается схема путей сообщения с указанием на ней длин отдельных участков, и на основании этой схемы составляется оптимальный план.
В матричной форме задачи можно определять не только расстояния, но и стоимости перевозок от каждого пункта отправления к каждому пункту назначения. Математическая форма постановки задачи, приведенная выше, относится к матричной форме.
Необходимо отметить, что приведенная общая постановка транспортной задачи имеет ряд ограничений, в частиости: требование однородности груза для сбставЛенйй оптимального плана перевозок; требование равенства суммы спроса продуктов сумме имеющихся мощностей предприятий.
В том случае, если приходится решать задачи, в которых указанные требования снимаются, используются специальные приемы для их решения, изложенные далее в § 3.
От правильного выбора критерия оптимальности1 в любой задаче линейного программирования и в транспортной, в частности, в значительной степени зависит эффект ее решения.
Схема перевозок является оптимальной, если при условии полного обеспечения спроса получается минимум затрат на осуществление заданного объема перевозок. Показателями критерия оптимальности в таких задачах являются затраты на перевозки данной продукции. В некоторых случаях в качестве критерия могут приниматься расстояния перевозок.
Для отдельных видов экономических задач созданы специальные методы, значительно сокращающие объем вычислений при их решении. К числу таких задач относится так называемая «транспортная» задача. Эта задача была поставлена в СССР, и поиски ее решения были связаны с необходимостью получения наиболее рационального плана перевозок.
Начало исследования транспортной задачи относится к 30-м годам. В эти годы советский ученый А. Н. Толстой предложил метод решения этой задачи при наличии не более двух поставщиков1.
В американской литературе первая работа, посвященная решению транспортной задачи, относится к 1941 г. и принадлежит Хичкоку. В связи с этим в некоторых американских литературных источниках эта задача иногда именуется задачей Хичкока.
Необходимо также отметить, что ни в работах А. Н. Толстого, ни у Хичкока не было дано законченного метода решения рассматриваемой задачи. Первый общий метод решения транспортной задачи, получивший в дальнейшем название «метода потенциалов», предложен ныне академиком Л. В. Канторовичем и опубликован в 1949 году, хотя разработан был им еще в 1941 г.
В наиболее общем виде транспортная задача может быть поставлена, когда требуется выбрать наиболее экономичные связи при перевозках различных грузов от множества поставщиков множеству потребителей.
В том случае, если перевозка груза осуществляется между двумя пунктами, то решить вопрос о целесообразном маршруте грузов, виде транспорта и рассчитать необходимое для этого время не представляет труда. При увеличении же количества пунктов отправления и получения грузов встает вопрос, каким образом провести прикрепления поставщиков к потребителям, чтобы намечаемая схема предусматривала минимальный грузооборот (в Ткм) и минимальную себестоимость (в руб.) перевозок.
В практике применения линейного программирования в нашей стране чаще всего приходится иметь дело с транспортными задачами или с задачами, приводимыми к транспортной. По данным американских ученых, такого типа задачи составляют около 85% всех задач оптимального программирования.
В том случае, когда область изменения переменных может быть изображена на плоскости или в трехмерном пространстве, простые геометрические построения быстро приводят к решению задачи. При этом количество исходных условий не лимитируется.
Решение задач с помощью графического метода содержит элементы не только аналитического, но и графического порядка. Большая наглядность является основным достоинством рассматриваемого метода. Однако область его применения ограничена решением задач с двумя и тремя переменными.
Практически этот метод применяется только при наличии двух переменных, так как уже при трех переменных в пользовании этим методом встречаются значительные трудности. Графический метод применяется при составлении программы по загрузке оборудования, при составлении смесей и т. д.
Решение задачи о загрузке оборудования в строительстве может встретиться при планировании работы производственных предприятий. К числу последних могут быть отнесены деревообрабатывающие предприятия, заводы сборных железобетонных конструкций и т. д. Допустим, что предприятие производит два вида продукции и использует для этого четыре различные группы оборудования. Обозначим имеющиеся группы оборудования через Л, Б, С и Д.На основании перечисленных исходных данных следует определить объем продукции обоих видов, при которых мощность действующего оборудования будет использоваться максимально.
Введем следующие обозначения: количество продукции первого вида (№ 1) обозначим через х, второго вида (№ 2) обозначим через у.
Для наилучшего использования оборудования необходимо, чтобы на каждую единицу продукции первого вида приходилось 3 единицы оборудования А и на единицу продукции второго вида — одна единица оборудования той же группы; общий объем продукции должен быть таков, чтобы обеспечивалось использование всех 15 единиц оборудования. То же с соответствующими модификациями должно быть обеспечено для других групп оборудования (В, С и Д).
Метод сокращения невязок, во многих источниках называемый также методом условно оптимальных планов, отличается тем, что начальный план составляют с учетом оптимума — целевой функции, причем исходные условия учитывают неполностью, а затем, последовательно улучшая этот план, приходят к учету всех исходных условий.
Процесс решения задачи по этому методу начинается с анализа некоторой системы предварительных оценок, т. е. плана сопряженной задачи и одновременно плана производства — опорного плана исходной задачи.
Система предварительных оценок дает суммарную оценку производственных факторов, а опорный план исходной задачи определяет суммарную оценку выпускаемой продукции. Заданная система предварительных оценок и исходный план производства оптимальны, если суммарная оценка затрат совпадает с общей оценкой продукции. Если такого совпадения нет, то образуется невязка в виде превышения расходов над доходами. Метод состоит в последовательном сокращении невязок. Сокращение невязок может производиться путем изменения предварительных оценок производственных факторов и системы базисных технологических способов.
Проводя сопоставление перечисленных выше методов, можно отметить следующее:
1. При решении задач методами, относимыми к группе методов последовательного улучшения плана, задается исходный план производства, путем его анализа устанавливается его оптимальность или пути его улучшения. Для оптимального плана производства определяется система оценок производственных факторов, называемая планом цен.
2. В методе последовательного уточнения оценок задается система предварительных оценок производственных факторов. Построение плана производства, соответствующего системе предварительных оценок, приводит к их последовательному уточнению. До тех пор, пока оценки не уточнены, не может быть получен оптимальный план производства. Система уточненных оценок соответствует оптимальному плану производства.
3. В задачах, решаемых методами последовательного сокращения невязок, процесс решения задачи начинают с плана производства и системы предварительных оценок, которые не согласованы между собой и приводят к невязке плана — превышению суммарной оценки затрат над суммарной оценкой продукции. Последовательное сокращение невязок приводит к оптимальному плану производства, в котором устанавливается система оценок производственных факторов.
Метод последовательного уточнения оценок основан на двойственной задаче.
Решение задачи этими методами сводится к определению оптимального плана сопряженной задачи. Двойственная связь обеих задач позволяет получить при этом и оптимальный план прямой задачи.
Исходя из предварительных оценок условий прямой задачи, приведенных в начальном плане сопряженной задачи, путем последовательного их уточнения получаем точные оценки условий задачи в оптимальном плане сопряженной задачи.
При переходе от одного шага (итерации) к другому значение линейной формы монотонно убывает.Если в методе последовательного улучшения плана приближение к максимуму линейной формы происходит снизу, то в методе последовательного уточнения оценок приближение к оптимуму осуществляется сверху.
Решение задачи по этому методу начинается с анализа некоторого опорного плана сопряженной задачи. По существу, план сопряженной задачи представляет собой план, в котором приведена система предварительных оценок производственных факторов, удовлетворяющая условиям [152] и [ 153]. Опорному плану сопряженной задачи соответствует т рентабельных способов производства с линейно независимыми векторами затрат, называемых базисными способами. Базисные способы, определяющие технологию производства, обозначим Si, s2, sm. Реализация плана производства не всегда может быть проведена, если ограничиться только способами производства, рентабельными относительно заданных предварительных оценок.Наличие отрицательных xio свидетельствует о нереализуемости плана производства, соответствующего выбранным предварительным оценкам производственных факторов. Тогда следует уточнить систему оценок путем исключения из базисных способов такого г, который отвечает отрицательному значению.
Одной из причин нереализуемости плана производства явился выбор r-го способа в качестве рентабельного. Уточнение оценок нужно произвести таким образом, чтобы г-й способ стал нерентабельным, а остальные базисные способы остались бы рентабельными.
Все методы линейного программирования делятся на две группы: конечные и итеративные. Методы первой группы обеспечивают решение задачи за конечное число шагов, методы второй связаны с бесконечным числом итераций и позволяют получить лишь приближенное решение. В настоящем учебном пособии рассматриваются только конечные методы линейного программирования.В зависимости от идеи, которая положена в основу того или иного конечного метода, он может быть отнесен к одному из следующих трех направлений линейного программирования: 1) последовательного улучшения плана; 2) последовательного уточнения оценок; 3) последовательного сокращения невязок (рис. 23).
Рассмотрим принципы, положенные в основу каждого направления, состав шагов и порядок перехода от одного шага к другому.
При решении задач конечными методами линейного программирования отправные планы задачи могут быть составлены с использованием: а) планов прямой задачи, б) планов сопряженной (двойственной) задачи; в) совместным использованием прямой и двойственной задач.Метод последовательного улучшения плана следует отнести к методам первой группы, в которых оптимальный план достигается при движении по опорным планам, составленным для прямой задачи.
В тех случаях, когда при решении задач начальный план составляют с учетом ограничений, обусловленных в задаче, а затем путем последовательных улучшений исходного плана приходят к удовлетворению условий целевой функции, мы имеем дело с методами последовательного улучшения плана.
Метод последовательного улучшения плана складывается из следующих этапов, необходимых для решения задач: способа вычислений опорного плана; установления критерия, позволяющего проверить оптимальность плана на каждом шаге; способа, позволяющего получить план, более близкий к оптимальному.
Прежде чем разбирать проблему двойственности, рассмотрим экономическую интерпретацию прямой и двойственной задач на примере. Предположим, что готовую строительную продукцию в виде жилых домов мы планируем для возведения из различных материалов стен (кирпичные, крупнопанельные, крупноблочные). Наличие разных материалов степ определяет различие в технологии производства работ по возведению этих зданий.Двойственная задача будет заключаться в том, чтобы определить для каждого вида материалов, трудовых затрат, затрат машинного времени такие оценки (цепы), чтобы в оптимальном плане производства (т. е. в соотношении строительства рассматриваемых видов жилых домов) расход материалов, труда и машиносмен по этим оценкам был бы минимальным. Если такие оценки принять в качестве цен на ресурсы, то при заданных условиях они будут стимулировать составление оптимального плана строительства жилых домов. Наименьший расход ресурсов при этом будет только в оптимальном плане. Сведение к минимуму затрат на строительство жилых домов (по оценкам) тем самым будет означать составление наилучшего плана производства строительно-монтажных работ по сооружению жилых домов.
Таким образом, если в задаче поставлено условие минимизировать функцию, то с каждой такой задачей можно связать исходную с ней задачу максимизации, которая называется двойственной или сопряженной. Между такими двумя задачами существует связь — минимум для прямой задачи соответствует максимуму для двойственной. Прямая и двойственная задачи образуют единую двойственную пару. Например, если ставится задача получения минимальной себестоимости строительно-монтажных работ, то это может быть достигнуто за счет максимального (с малыми отходами) использования материалов и полуфабрикатов и максимального использования (без впутриемспных потерь) рабочего времени рабочих и строительных машин. Максимальное, наиболее полное использование ресурсов, предоставленных строительной организации, обеспечит минимальную себестоимость.
