ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД

Чтобы понять основные свойства линейных моделей и из чего скла­дывается процесс получения решения задач линейного программирова­ния, рассмотрим геометрическую интерпретацию линейного программи­рования, получившего название графоаналитического метода. Необходи­мо учитывать, что графоаналитический метод может быть использован только в том случае, если задача содержит два, максимум три неизвестных. В последнем случае приходится пользоваться про­странственной моделью. Несмотря на простоту решения задач этим ме­тодом, его применение при разработке технологических процессов весь­ма ограничено.

Сущность графоаналитического метода рассмотрим на решении сле­дующей задачи:

максимизировать функцию 10Х₁+13Х₂ (8.11)

при наличии ограничений

Решение задачи может быть найдено графически, как показано на рис. 8.2. Ограничения (8.12) и (8.13) на рис. 8.2 изображены прямыми ли­ниями как уравнения, полученные заменой неравенств на равенства. Площадь под каждой из двух прямых эквивалентна математической формулировке, имеющей направленный смысл «меньше, чем» (<). Так как X₁ и X₂ не могут принимать отрицательных значений, область до­пустимых значений переменных ограничивается осями координат. Таким образом, многоугольник ОABC содержит в себе область значений Х_х и Х₂, удовлетворяющих всем имеющимся ограничениям. Множество то­чек, принадлежащих области, ограниченной линиями ОАВС (вместе с граничными точками), называется множеством решений. Это множест­во является выпуклым, т. е. любой отрезок, соединяющий две произвольным образом выбранные точки данного множества, лежит внутри или проходит вдоль границы ОABC.

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

Изменяя степень достижения цели Z₀, получаем на рис. 8.2 семейст­во параллельных изолированных прямых, уравнение которых

Из уравнения (8.16) следует, что чем выше степень достижения цели, тем выше располагается соответствующая изоцелевая прямая. Оптималь­ное решение определяется экстремальной точкой В, для которой

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

то в этом случае все точки, лежащие на отрезке АВ, будут являться опти­мальными (рис. 8.3). Решение X₁ = 0,95, Х₂=1,8 будет оптимальным. Однако оптимальным будет и решение X₁ = 0, Х₂ = 2. Оптимальное значение целевой функции будет равно 28,0.

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

Изменение целевой оптимизирующей функции в определенных пре­делах не приводит к изменению решения задачи. В случае, когда в задаче имеются три переменные величины и три уравнения ограничений, например, максимизировать

при наличии ограничений:

то приходится пользоваться пространственной моделью.

Когда ограничения являются уравнениями, то каждое из них можно считать уравнением плоскости, лежащей в трехмерном пространстве, и точка, общая этим трем плоскостям, есть единственная точка, представ­ляющая собой допустимое решение (рис. 8.4, а). Если ограничения яв­ляются неравенствами, то область оптимальных решений образуют точки некоторого выпуклого многогранника, расположенного в первом октанте. Придавая переменной Z₀, формула (8.18), различные значения, по­лучим семейство параллельных изоцелевых плоскостей (см. рис. 8.4, а), при­чем большим значениям Z₀ будут соответствовать плоскости, располо­женные дальше от начала координат. Решение задачи дается координа­тами одной из вершин выпуклого многогранника допустимых решений.

Если вместо трех уравнений ограничений имеется лишь два, до­пустим, уравнения (8.19) и (8.20), то в этом случае областью допусти­мых решений окажется линия пересечения плоскостей, являющихся изо­бражениями уравнений ограничений (рис. 8.4, б). При одном уравнении ог­раничений областью допустимых решений будет являться треугольник, образованный линиями пересечения плоскости, изображающей это урав­нение, с плоскостями координат (рис. 8.4, в).

В случае, когда необходимо получить не максимум, а минимум функции, то многоугольник будет вогнутым.

Особенности решения задач графоаналитическим методом рас­смотрим на следующих примерах

Задача 8.3. От поставщика А груз перевозится автомобилями КаMA3-5320 двум потребителям B₁ и В₂ на расстояние 15 и 25 км соот­ветственно. При перевозке груза потребителю B₁ на одну ездку затрачи­вается 1,23 ч, а потребителю В₂ - 1,8 ч. Продолжительность работы ав­томобилей на линии -8 ч. Работая на маршруте В₁, водитель делает 6 ездок, затрачивая на это 7,38 ч рабочего времени. На маршруте В₂ во­дитель делает 4 ездки и затрачивает 7,2 ч рабочего времени. Требуется организовать работу так, чтобы максимально использовать рабочее время водителей.

Математическая модель запишется в следующем виде:

максимизировать

при наличии ограничения

где: X₁ - число ездок на маршруте В₁;

Х₂ - число ездок на маршруте В₂.

Решение может быть найдено графически, как показано на рис. 8.5. При X1 = 0, Х2 = 4,4. При Х2 = 0, X1 = 6,5. Соединив полученные точки А и В, получим область допустимых решений X, и Х2. Левые части уравнений целевой функции (8.22) и ограничения (8.23) совпадают. Это значит, что все точки, лежащие на линии 1,23Х1+1,8Х2=8.

будут оптимальными. Точки Q, С₂ и так далее, заключенные между прямой АВ и осями координат, имеющие координатами целые числа, изображают все возможные варианты работы автомобиля. Точки, которые ближе расположены к прямой или лежат на ней, дают наилучшие - оптимальные решения.

В рассматриваемом примере точки C₁ с координатами X₁=5 и Х₂ = 1 и С₄ с координатами X₁ = 2, Х₂ =3 ближе всех расположены к линии АВ. В первом случае продолжительность работы водителя на ли­нии составит

1,23-5 + 1,8*1 = 7,95 ч,

а во втором

1,23-2 + 1,8*3 = 7,86 ч.

Задача 8.4. Определить потребное число поддонов для перевозки грузов пакетами, упакованными в потребительскую тару двух размеров - А и В. Количество грузов в таре типа А составляет 600 единиц и типа В - 300 единиц. Количество тары, загружаемой на поддон различными спо­собами, приведено в табл. 8.1.

Таблица 8.1

Математическая модель задачи будет сформулирована следующим образом:

минимизировать Х_{ + Х₂ + Х₃ + Х₄ = Z₀, (8.24)

при наличии ограничений

где: X_i - число поддонов, загруженных по i-способу размещения тары.

Для решения задачи начертим прямоугольную систему координат АОВ (рис. 8.6) и каждому возможному способу размещения тары на под­доне поставим точку, координаты которой соответствуют числу соответ­ствующей тары, размещаемой на поддоне. Буквой С с индексом обозначим номер способа размещения тары на поддоне. Множество всевозможных планов размещения тары на поддоне изображается совокупностью точек выпуклого многоугольника С₁ С₂ С₄ С₃. Например, точки на отрезке С₁ С₂ будут указывать

своими координа­тами количество тары типа А и ти­па В, приходящейся на один под­дон в различных способах разме­щения их, сочетающих собой размещения по способу С1 и С2 (рис. 8.6). Из всех решений нас ин­тересует выполнение условия ком­плектности, т. е. отношение числа тары А к числу тары В. В соот­ветствии с заданием это соотно­шение равно 2 (600:300). Если из начала системы координат про­вести луч, координаты которого А= 2, В = 1, то оптимальным бу­дет план размещения тары на под­доне, которому соответствует точка, одновременно принадлежащая многоугольнику и лучу, и имеющая наи­большие координаты, т. е. соответствующая плану наибольшего исполь­зования площади поддонов. Такой точкой будет Р, лежащая на отрезке С1 С3. Это указывает на то, что оптимальный план размещения тары на поддонах представляет собой комбинацию размещения тары по способу C1 и С3.

Обозначим через δ долю поддонов, загружаемых по способу C₁, а остальную часть (l-δ) - по способу С₃, долю одного и другого способа размещения поддонов найдем из условия комплектности

Минимальное число поддонов Z₀ определится из уравнения

откуда Z₀ =212. Таким образом, по способу C₁ будет загружено 194 поддона и по способу С₃ - 18.

МЕТОД ПОТЕНЦИАЛОВ

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

Математическая модель классической транс­портной задачи в общем виде записывается в следующей форме:

минимизировать

при ограничениях

где: m - число поставщиков;

n - число потребителей;

Xij - объем перевозок между i и j пунктами;

S_i- - ограничения по предложению;

Di - ограничения по спросу;

a_ij - расстояние от пункта i до пункта j.

Условия задачи можно представить следующим образом. Каждый по­ставщик должен дать потребителям столько продукции, сколько у него есть, т. е.

Каждый потребитель должен получить столько, сколько ему требует­ся, т. е.

Необходимо найти такой вариант плана перевозок, чтобы транспорт­ная работа была минимальна, т.е.

Запись и решение транспортной задачи методом потенциалов вы­полняется в таблично-матричной форме. Совокупность всех элементов матрицы х_ij называется планом перевозок или распределением поставок. Элементы матрицы называются показателями критерия оптимальности.

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

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

Критерий «минимум тонно-километрового пробега» (показатель критерия - расстояние) наиболее прост для применения и оп­ределения. К его недостаткам следует отнести то, что при одинако­вом расстоянии транспортирования могут быть различные затраты (движение подвижного состава по различным дорожным покрытиям, пе­ревозки по дорогам с различной интенсивностью движения и т. д.).

Критерий «минимум провозных плат» (показатель кри­терия - тарифы) применяется для получения схемы грузопотоков, обес­печивающей минимальные затраты грузоотправителей. К недостаткам этого критерия следует отнести то, что тарифы не обладают свойством аддитивности, т. е. суммы тарифных плат от пункта А до пункта Б и от пункта Б до пункта В не идентичны тарифу от пункта А до пункта В. Это не дает возможности использовать тарифы в качестве критерия опти­мальности при сетевой постановке задачи, а также при использовании машинных методов составления матриц.

Критерий «минимум эксплуатационных расходов на транспортиро­вание грузов» (показатель критерия - себестоимость транспортирова­ния) отражает затраты автотранспортного предприятия, осуществляю­щего выполнение перевозок. Этот критерий может также использовать­ся при распределении перевозок между различными видами транспорта. Его недостатками являются: себестоимость транспорти­рования рассчитывается на обезличенный груз и не учитывает затрат, возникающих при перевозке отдельных видов специальных грузов; не учитывает изменение затрат на погрузочно-разгрузочные работы при использовании различных видов подвижного состава; сложность расче­та себестоимости транспортирования по отдельным участкам дорожной сети.

Критерий «минимум тонно-часов транспортирова­ния груза» (показатель критерия - время транспортирования) может применяться при перевозке скоропортящихся грузов, овощей, живности и другой продукции. К его недостаткам относится то, что он не учитывает затрат, связанных с транспортированием груза.

Линейные уравнения, описывающие условия транспортной задачи, отражают пропорциональные зависимости. Наличие линейных зависимо­стей - обязательное условие применения методов линейного программи­рования. Однако для транспортной задачи это требование условно. На­пример, затраты на транспортирование грузов не прямопропорциональны расстояниям транспортирования, однако они используются в качестве показателей целевой функции.

Чтобы задача имела допустимое решение, требуется, чтобы общие ресурсы поставщиков были не меньше общего спроса потребителей S_i ≥ Dj, а также естественным представляется и требование неотрица­тельности объема поставок и спроса, т. е. Si ≥ 0, Dj≥ 0.

Рассмотрим применение метода потенциалов на следующем примере:

Задача 8.5. Из трех грузообразующих пунктов A₁, А₂, А₃ необхо­димо перевезти однородный груз четырем потребителям B_l, В₂, B₃, B₄. Количество груза в пункте А₁ = 300 т, в пункте А₂ = 500 т, A₃ = 800 т. Спрос потребителей на данный груз составляет: В₁ = 200 т, В₂ = 350 т, B₃ = 650 т, В₄ = 400 т. Расстояния между грузоотправите­лями и грузополучателями приведены в табл. 8.2. Необходимо так закре­пить потребителей груза за грузополучателями, чтобы общая транспорт­ная работа была минимальной (показатель критерия оптимальности - расстояние).

Таблица 8.2

Расстояние между грузообразующими и грузопоглощающими пунктами

Для решения задачи обозначим через х_ij количество тонн груза, ко­торое должно быть перевезено от i-поставщика j-потребителю. Тогда ма­тематическая модель задачи выразится системой уравнений (8.35), а це­левая функция, представляющая собой сумму произведений расстояний на соответствующий объем перевозок груза в тоннах, уравнением (8.36).

Минимизировать

Полученная система уравнений (8.35) является линейно зависимой, так как любое ее уравнение можно представить в виде линейной комби­нации остальных уравнений. Действительно, если из суммы уравнений 1, 2, 3 вычесть сумму уравнений 4, 5, 6, то получим уравнение 7 и т. д. Чис­ло линейно независимых уравнений должно быть меньше на одно общего числа уравнений в системе, т. е. базис системы должен быть равен коли­честву уравнений в системе ограничений за вычетом единицы. Так как общее число уравнений в системе определяется суммой поставщиков и потребителей, то в базисе должно быть уравнений

т + п-1, (8.37)

где: m - число поставщиков;

n - число потребителей.

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

Матрица - прямоугольная таблица чисел, состоящая из m строк и n столбцов, в которой на пересечении строк и столбцов, обычно в пра­вых верхних углах, указывается расстояние между данным поставщи­ком и потребителем (в общем случае указывается показатель целевой функции).

К базисному плану предъявляются следующие требования:

он должен быть допустимым, содержать m + n — 1 загруженных клеток, чтобы загруженные клетки были расположены в порядке вычеркивае­мой комбинации. Для сокращения числа итераций при последующем ре­шении желательно, чтобы базисный план был, возможно, ближе к оп­тимальному.

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

Число неизвестных Х в задаче равно произведению числа строк m на число столбцов n. Максимальное число уравнений, которое можно полу­чить при решении транспортной задачи, определяется суммой поставщи­ков и потребителей, т. е. т + п. В этом случае, как показано выше, система уравнений является линейно зависимой. Для решения транспортной задачи базис системы должен содержать т + п-1 уравнений, а следовательно, в матрице должно быть т + п-1 загруженных клеток.

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

Самый простой способ составления базисного плана - это так назы­ваемый способ северо-западного угла. Сущность этого спо­соба заключается в следующем. Распределение груза по потребителям начинается с клетки А₁ В₁ (табл. 8.3). Если предложение больше спроса, то следующая цифра ставится в клетке А₁ В₂ и т. п.

Таблица 8.3

Базисный план, составленный способом северо-западного угла

Клетки таблицы, в которых отмечено количество груза, перевозимого от грузоотправителя к данному грузополучателю, называются загружен­ными. Остальные клетки - незагруженными. Способ северо-западного угла является плохим способом составления базисного плана, так как в большинстве случаев дает базисный план, очень далекий от оптималь­ного. Положительная сторона его заключается в том, что он очень прост и обеспечивает получение т + п-1 загруженных клеток.

При полученном базисном плане закрепления поставщиков за потребителями (табл. 8.3), транспортная работа составит

200 • 11 +100 • 7 + 250 • 13 + 250 • 7 + 400 • 5 + 400 -9 = 13500 т-км.

Несколько лучшими способами составления базисного плана являют­ся способы наименьшего элемента по столбцу или наименьшего элемента по строке. При составлении базис­ного плана способом наименьшего элемента по столбцу поочередно в столбцах матрицы отмечаются клетки с минимальным значением ау и в

них заносятся поставки. Если при записи поставок спрос по столбцу удовлетворен не полностью, ищется следующий по величине показа­тель a_ij, и так до полного удовлетворения спроса. Только после этого переходят на следующий столбец. Когда в столбце два или несколько одинаковых по величине минимальных показателей a_ij, то поставки мо­гут быть размещены в любом из них. Результаты составления базисного плана этим способом приведены в табл. 8.4.

Таблица 8.4

Базисный план, составленный способом наименьшего элемента по столбцу

При базисном плане, полученном способом наименьшего элемента по столбцу (табл. 8.4), транспортная работа составит

200-3 + 300-7 + 50-12 +100-7 +550-5 + 400-8 = 9950т-км.

Базисный план получился лучше (транспортная работа сократилась на 3550 т-км), однако нельзя сказать, является ли он оптимальным или нет. Для ответа на этот вопрос необходимо составленный базисный план проверить на оптимальность. Для этих целей разработано несколько ме­тодов. Наиболее широкое применение находят методы потенциалов (ме­тода МОДИ), Хичкока, Креко.

Идея метода потенциалов была высказана Л. В. Канторовичем в 1940 г. В 1951 г. американский ученый Дж. Д. Данциг предложил ту же идею, назвав ее модифицированным распределительным методом (МО­ДИ). Идея метода потенциалов, или метода МОДИ, заключается в том, что для проверки допустимого базисного плана на оптимальность опре­деляются особым образом числа, называемые потенциалами. Главное требование к потенциалам заключается в том, чтобы каждый показатель a_ij в загруженной клетке был равен сумме потенциалов своих строки и столбца

a_ij=V_i+Vj, (8.38)

где: Ui - значение потенциала строки;

Vj - значение потенциала столбца.

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

Потенциалы незагруженных (свободных) клеток определяются по формуле

где: Е_ij - потенциал свободной клетки.

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

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

Проверим на оптимальность базисный план, составленный способом наименьшего элемента по столбцу. Для этого матрицу распределительно­го метода дополним одним столбцом и строкой (табл. 8.5). Поставим в строке A₁ величину потенциала, равную нулю. Тогда, согласно форму­ле (8.38), потенциал столбца В₂ будет равен 7. Потенциал строки A₃ будет равен 5, а столбца B₃ - 0 и т. д. Потенциалы незагруженных кле­ток находим по формуле (8.39).

В результате проверки допустимого плана на оптимальность получе­на клетка А₂В₂, имеющая отрицательный потенциал. Это указывает на то, что план не оптимален и необходимо выполнить перераспределение закрепления поставщиков за потребителями. Это выполняется сле­дующим образом. Строится контур. Контуром называется замкнутая ломаная линия, образованная прямыми отрезками, углы со­единений между которыми равны 90°. Строится контур так, чтобы все углы, кроме одного, располагались в загруженных клетках, а один угол в свободной, наиболее потенциальной клетке. При соблюдении этих правил для каждой свободной (незагруженной) клетки можно построить только один контур. Определяют положительные (+) и отрицательные (-)углы контура. Первый положительный угол лежит в незагруженной клетке, для которой строится контур, рядом с ним находятся отрица­тельные углы и т. д.

Таблица 8.5

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

Ранее загруженные клетки, которые не оказались расположенными в углах контура, переносятся в матрицу нового варианта закрепления по­требителей груза за поставщиками без изменения (табл. 8.6).

Таблица 8.6

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

200-3 + 300-7 + 50-13 + 50-7 + 600-5 + 400-8 = 9900 т-км.

Последовательность решения транспортной задачи методом по­тенциалов схематически показана на рис. 8.7.

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

Ранее отмечалось, что способ северо-западного угла является самым неудачным способом со­ставления базисного плана. Распределение поставок способом наимень­шего элемента по столбцу или по строке значительно улучшает базисный план поставок. Помимо этих приемов, улучшающих базисный план, рас­смотрим еще три способа: способ аппроксимации У. Фогеля, способ по­следующего анализа (способ стрелок) и способ двойного предпочтения.

Способ аппроксимации У. Фогеля. По мнению У. Фо­геля, его способ может заменить во многих случаях методы линейного программирования. На самом деле его можно применять только для со­ставления базисного плана, а затем для решения задачи использовать обычную процедуру линейного программирования.

При составлении базисного плана поставок способом аппроксимации У. Фогеля исходные данные заносятся в таблицу, которая отличается от матрицы метода потенциалов тем, что имеет дополнительную строку и столбец разностей (табл. 8.7).

Таблица 8.7

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

Так, в столбце минимальный элемент равен 3 в клетке А₃В₁. Сле­дующий за ним по величине элемент, равный 5, находится в клетке А₂В₁. Разность между ними равна 2. Эта и другие разности по строкам и столбцам записаны в табл. 8.7.

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

Смысл способа У. Фогеля заключается в следующем. Найденные разности показывают, насколько больше будут расстояния, если в со­ответствующем столбце или строке поставка будет записана не в клетку, где находится минимальный в этом столбце или строке элемент, а в клетку, где находится элемент, следующий за ним по величине. Там, где разность оказывается наивысшей, будут наибольшие потери на единицу продук­ции, если поставка не попадет в клетку с наименьшим оптимизирую­щим элементом.

В нашем примере, записав максимальную поставку в клетку А₁ В₂ в количестве 300 т, исключаем показатели критерия оптимальности по этой строке, поскольку мощность поставщика А₁ полностью исчерпа­на, и вновь определяем разности между наименьшими элементами по строкам и столбцам матрицы (табл. 8.8.)

Таблица 8.8

Если оказывается несколько одинаковых разностей, имеющих мак­симальное значение (в нашем примере столбцы В₁ В₃ и строки А₂ и A₃), то в соответствующих им столбцах или строчках находят и загружают седловую точку. Седловой точкой называют клетку таблицы, рас­стояние которой имеет наименьшее значение (при решении задачи на минимум) из всех расстояний ее строки и столбца или наибольшее значе­ние при решении задачи на максимум.

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

В нашем примере седловой точкой будет клетка А₃В₁ в которую за­писывается максимально возможная поставка, и т. д.

Способ последующего анализа (способ стрелок). Первоначальное закрепление потребителей за поставщиками, начиная с первого столбца с учетом наименее возможного расстояния транспор­тирования, потребности грузопотребителя и возможности поставщика (см. табл. 8.4). Полученный базисный план анализируется с целью выяв­ления возможностей его улучшения. В строке А₃ можно передвинуть из клетки А₃В₂ в клетку A₃В₁ 50 т, а из клетки А₂В₃ в клетку А₂В₂ вместо это­го - 50 т. В результате этого в первом случае расстояние перевозки уве­личится на 7 км, а во втором случае сократится на 6 км. Суммарное со­кращение расстояния перевозки составит 1 км.

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

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

Если при составлении базисного плана число загруженных клеток получается больше, чем m + n-1, то при проверке на оптимальность для какой-либо строки или столбца будут найдены два потенциала. Чтобы устранить такую ситуацию, нужно произвести следующие действия:

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

углы контура обозначить попеременно знаками «плюс» и «минус». Углу, лежащему в загруженной клетке, для которой построен контур, присваивается знак «плюс»;

выявить наименьшую загрузку в клетках, занятых углами со знаком «плюс», вычесть ее из всех клеток и прибавить во все клетки, занятые углами со знаком «минус».

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

Если число загруженных клеток при составлении базисного плана окажется меньше, чем т + п - 1, то недостающее число клеток загру­жают нулями. Загружать следует те клетки, которые лежат на пересече­нии строк и столбцов, не имеющих потенциалы, со строками или столб­цами, для которых потенциалы уже определены и имеют наименьшие значения показателя критерия оптимальности.

Дополнительные условия при решении транспортных задач ме­тодом потенциалов. Предложение больше спроса. Условия задачи записываются в таблицу, в которую вводится фиктивный столбец Р с ограничением по спросу, равный разности между предложением и спросом. Так как груз никуда не вывозится, то в углах клеток столбца Р ставятся нули. Задачу решают по алгоритму метода потенциалов, рас­сматривая столбец Р как потребитель груза.

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

Запрещение корреспонденции. Если необходимо по каким-либо при­чинам наложить запрет на перевозку груза из пункта A₁ в пункт В₁, то для этого достаточно вместо реального элемента целевой матрицы, стоящего в клетке А₁ В₁, поставить очень большую величину М, которая больше лю­бого наперед заданного числа, имеющегося в данной задаче.

Обязательная поставка. Если из пункта А_i- в обязательном порядке не­обходимо перевезти в пункт Bj какой-то объем груза, то в этом случае ве­личина обязательной поставки вычитается из суммы спроса и суммы пред­ложений и при решении задачи не учитывается. При определении оконча­тельного результата затраты, связанные с обязательным объемом перевозок, прибавляются к полученному оптимальному варианту.

Открытая модель возникает в случаях, когда отсутствует ка­кая-либо из групп ограничений - спрос или предложение. Это означает, что любой потребитель может взять всю сумму имеющихся у поставщи­ков материалов или любой из поставщиков может удовлетворить спрос всех потребителей данного материала.

Решение задачи. Если отсутствуют ограничения по предложению, то ограничения по спросу в каждом столбце таблицы переносятся в клет­ки с оптимальным элементом целевой матрицы данного столбца, а при от­сутствии ограничений по спросу - в клетку каждой строки.

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

Не нашли, что искали? Воспользуйтесь поиском: