Как найти опорный план пример

Транспортная задача линейного программирования

Прочие статьи цикла

Транспортная задача линейного программирования относится к перечню классических задач, решаемых в практике деятельности людей. Эта задача методами классической математики не решается. В задаче необходимо отыскивать экстремум целевой функции. В задаче целевая функция – линейная. Ограничения на переменные (их может быть очень много) описываются также линейными зависимостями. Казалось бы чего проще. Но как раз ограничения и порождают трудности, связанные не просто с поиском max и min при отсутствии ограничений, а с необходимостью учета таких ограничений. Искать требуется не просто экстремум, а условный экстремум. Методы решения задачи позволяют учитывать особенности структуры задачи и даже отказаться от симплексного метода решения в чистом виде.

I. Основные параметры, термины и обозначения

Для ощущения масштаба задачи приведу парочку изображений того, что рассматривается в транспортной задаче линейного программирования.

Зеленый цвет – пассажирские суда, желтые – грузовые, розовый – частные яхты, оранжевый – танкеры и др. Аналогичная картина наблюдается и для авиационных перевозок, перевозок по железной дороге или автотранспортом. Изображения получены в начальном периоде Пандемии короновируса, что привело к огромным пробкам в узостях мирового Океана (Панамский, Суэцкий и др. каналы). Танкеры отправили отстаиваться на рейде, экипажам судов на берег сойти не разрешалось. Это форс-мажорные обстоятельства, которые в теории должны рассматриваться и учитываться специальным образом, что пока к сожалению перевозчиков не сделано.

В теории в тексте задачи Хичкока ничего не говорится о равенстве имеющегося общего запаса судов в портах отправления и общей потребности в судах в портах прибытия (назначения). Если такого равенства нет, то система ограничений несовместна. В случае равенства

транспортная задача называется «сбалансированной». Задачи, в которых условие баланса не задано, должны быть приведены к «сбалансированному» виду. Это можно выполнить использованием «фиктивных» перевозок. Рассматриваем два случая:

Метод содержит три последовательных этапа:

1. Формирование опорного плана;

2. Проверка опорного плана на оптимальность;

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

II. Формирование опорного плана перевозок

Затем, если a₁ > b₁, то определяется остаток (a₁ – b₁) продукта на первом пункте отправления и его запас реализуется на 2-м пункте назначения. Остаток потребностей 2-го пункта назначения удовлетворяется за счет 2-го пункта отправления, остатки которого направляются в 3-й пункт назначения и т.д. Ниже метод будет иллюстрирован числовым примером.

Пример 1. Построение опорного плана методом Северо-Западного угла

Заданы значения: m = 3, n = 4; a₁ = 60, a₂ = 80, a₃ =100, b₁ = 40,b₂ = 60, b₃ = 80, b₄ = 60. Слева в таблице приведены d_ij удельные стоимости перевозок; справа – В_ij стоимости совместно с предложениями a_i и потребностями b_{j .}

Требуется найти план Х [m,n] перевозок, удовлетворяющий условиям на целевую функцию Q и переменные х_ij задачи Q.

РЕШЕНИЕ Построить исходный опорный план способом северо-западного угла. Строим симплексную таблицу:                                        Таблица 3.   Опорный план задачи

Q = d₁₁∙x₁₁ + d₁₂∙x₁₂ + d₂₂∙x₂₂ + d₂₃ ∙x₂₃+ d₃₃ ∙x₃₃+ d₃₄ ∙x₃₄ = = 5∙40 + 2∙20 + 10∙40 + 2∙40 + 8∙40 + 5∙60 = 200+40+400 + 80 + 320+ 300 = 1340 ед

Коэффициенты d_ij называются фиктивными или косвенными стоимостями; их выражают через косвенные величины α и β, d’_ij = α_i +β_j . Здесь параметры α_i и ( – β_j ), по аналогии с механикой называют потенциалами i-го пункта отправления и j-го пункта прибытия. Значения потенциалов определяется из системы линейных уравнений: α_i + β_j = d_ij Каждому из таких уравнений соответствует какая-либо базисная переменная х_ij Система уравнений с потенциалами содержит m+n неизвестных потенциалов, число же уравнений равняется числу базисных ячеек таблицы, т.е. (m + n – 1). Следовательно, один из потенциалов можно задать произвольно, положив его равным, например, нулю.

Решая далее систему уравнений для потенциалов, находим значения потенциалов строк и столбцов, все фиктивные стоимости d_ij и коэффициенты γ_ij. Если для всех свободных клеток γ_rs ≤ 0, то перевод в базис любой свободной переменной не уменьшит значения целевой функции и, следовательно, выбранный опорный план не является оптимальным. Если же некоторые γ_rs >0, то данный план можно улучшить путем перевода в базис свободной переменной, соответствующей max γ_rs, а также путем исключения из базиса, принадлежащей ему переменной, первой обращающейся в нуль. Переход к новому опорному плану и поиск оптимального плана рассмотрим на примере. Другой способ формирования опорного плана предложен Фогелем. Этот способ при первом чтении можно пропустить, так как дальше он в тексте не используется.

Пример 2. Способ аппроксимации Фогеля

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

Этапы алгоритма: 1.     Вычисление разностей в каждой строке и в каждом столбце между наименьшей стоимостью и ближайшей к ней по величине. Разности по строкам записываются справа в столбце разностей, разности по столбцам – внизу в строке разностей. Например, для строк А₁ разность равна А₁В₂ – А₁В₃ = 38 – 24 = 14 и т. д.

ТАБЛИЦА 2 – Метод Фогеля для получения опорного плана транспортной задачи

2.     Поиск из всех разностей, как по строкам, так и по столбцам максимальный. В нашем примере максимальная разность равна 38 и находится в строке А₂. Обведем максимальную разность рамкой.

3.     Размещение в клетку, где находится наименьшая стоимость (А₂В₂ = 18) (строка с наибольшей разностью), максимально возможного количества ресурсов. Оно равно 20, т.е. всему ресурсу отправителя А₂. Поскольку все ресурсы отправителя А₂ исчерпаны, строку А₂ исключаем из дальнейших расчетов, для чего отметим все клетки этой строки точками.

4.     Вычисление разностей столбцам и строкам, не принимая во внимание стоимость в клетках, имеющих ресурсы и клетках с точкой (исключенную строку или столбец) и определение максимальной разности в строке или столбце (В₃ = 76).

5.     Поиск минимального элемента в строке или в столбце с максимальной разностью (А₁В₃ = 24) и размещения в данную клетку максимально возможного количества ресурса, возвращение к этапу №4 и т.д. Окончательно

ЦФ Q=23∙19 + 7∙3 + 20∙18 + 2∙10 + 14∙24 + 1∙100 +3∙48 = = 437 + 21 + 360 + 20 +3 36 + 100 + 272 =1546 ед. Это значение соответствует опорному плану Фогеля.

III. Транспортная задача линейного программирования

Как основной метод решения транспортной задачи – используется метод потенциалов. Ни симплексный метод, ни распределительный метод здесь не рассматриваются. У них имеются свои плюсы и минусы, но объем изложения достаточно велик. Возможно этому позднее я уделю внимание и время, но пока отвечаю на пожелание читателя Хабра.

Пример 3 – Транспортная задача. Метод потенциалов

Исходные данные задачи удобно представить двумя матрицами.

ТАБЛИЦА – Исходные данные

Базисные n + m – 1 = 3 + 4 – 1 = 6 переменные:  
x₁₁ =70, x₁₂ = 20, x₂₂ = 10, x₂₃ = 20, x₂₄ = 0, x₃₄ = 40.
Остальные переменные nm – n + m – 1 = 12 – 6 = 6 свободные:
x₁₃ = x₁₄ = x₂₁ = x₂₄ = x₃₁= x₃₂ = 0 .
Суммарная стоимость перевозок для опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₂∙x₁₂ + d₂₂∙x₂₂ + d₂₃∙x₂₃+ d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 3∙10 + 1∙20 + 2∙0 + 2∙40 = 140 + 60 + 30 + 20 + 0 +80  = 330 ед.

2. Проверка опорного плана на оптимальность

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

Выделяем в Г [m, n] свободные ячейки, содержащие γ_rs. Проверяем наличие положительных переменных γ_i,j > 0. Так как в матрице (в свободных ячейках) имеем γ₃₂ = 2 > 0, то исходный опорный план может быть улучшен, он не является оптимальным.

3. Переход к новому (улучшенному) опорному плану

Переменную x₃₂ =x следует ввести в базис.  Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок

Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок   Очевидно, что наибольшее x определяется теми x_ij в базисных клетках, из которых этот х вычитается. Следовательно, x₁₁ = min{х₂₂, х₃₄} = {10, 40} = 10. При x >10 перевозка х₂₂ становится отрицательной. Переменную х₂₂ исключаем из базиса и переводим ее в разряд свободных переменных. Далее повторяются рекурсивно три пункта алгоритма.

1. Получаем из модифицированного плана новый опорный план

   В нем объемы перевозок распределены иначе чем в начальном опорном плане.

Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₂∙x₁₂ + d₂₃∙x₂₃ + d₃₂∙x₃₂ + d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 2∙10 + 1∙20 + 1∙10 + 2∙30 = 140 + 60 + 20 + 20 + 10 + 60  = 310 ед. Затраты на перевозки при этом плане уменьшились на 330 – 310 = 20 ед.

Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.

2. Проверка опорного плана на оптимальность

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

Свободные ячейки матрицы Г [m, n] содержат γ_i,j > 0 (γ₁₄ = 1>0). План не оптимален.

3. Переход к новому (улучшенному) опорному плану

Из свободных переменных с x_ij > 0, выбираем одну x₁₄  для введения ее в базис. Обозначим ее как и ранее через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся очередным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок  

Очевидно, что наибольшее x определяется теми x_ij в базисных клетках, из которых этот х вычитается. Следовательно, x₁₁ = min{х₁₂, х₃₄} = {20, 30} = 20. При х₁₂ >20 перевозка х₁₂ становится отрицательной. Переменную х₁₂ исключаем из базиса и переводим ее в разряд свободных переменных. Переходим к новой итерации

1. Получаем из модифицированного плана новый опорный план.

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

Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₄∙x₁₄ + d₂₃∙x₂₃ + d₃₂∙x₃₂ + d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 140 + 60 + 20 + 20 + 30 + 20  = 290 ед. Затраты на перевозки при этом плане уменьшились на 310 – 290 = 20 ед. Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.

2. Проверка опорного плана на оптимальность

Определим систему уравнений для потенциалов и вычислим их значения:
α₁ + β₁ = d₁₁ = 2;
α₁ + β₄ = d₁₄ = 3;
α₂ + β₃ = d₂₃ = 1;
α₂ + β₄ = d₂₄ = 2;
α₃ + β₂ = d₃₂ = 1;
α₃ + β₄ = d₃₄ = 2. Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пусть β₁ = 0. Тогда после решения системы получены значения потенциалов: α₁= 2, α₂= 2, α₃= 2, β₁ =0, β₂=1, β₃ =–1, β₄ =0.

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

При переходе к новому опорному плану проверяем наличие положительных свободных переменных γ_i,j >0. Но таких переменных не оказалось. Отсюда следует вывод, что полученный последним модифицированный план является оптимальным и ему соответствует значение линейной формы
Q’= 2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 290.

Заключение

Вся теория исследования операций с позиций математики решает неклассические задачи оптимизации целевых функций. Отличие от классики в том, что те ограничения на переменные, которые исследователи вынуждены накладывать в рамках моделей, созданы и вызваны реальностью. Отыскивать требуется экстремумы функций при многих ограничениях, так называемые условные экстремумы. Классика не позволяет этого делать. Взятие производных и приравнивание их нулю “не видит” ограничений. Лучшее, что там имеется это функция Лагранжа, но ее использование также весьма ограничено. Транспортные задачи – частный, но важный случай в исследовании операций. Надеюсь, что читатель разобравшись в приведенных примерах, лучше стал понимать логику задачи и сумеет самостоятельно постигать интересующие его вопросы по другим публикациям в учебниках и журнальных статьях.

Литература

Транспортная задача. Методы решения

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

1. Математическая постановка транспортной задачи.

Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления A₁, A₂,…, A_m в пункты назначения B₁, B₂,…, B_n. Критерий оптимальности берется минимальная стоимость перевозки или минимальное время доставки груза.

Рассмотрим транспортную задачу, где в качестве критерия оптимальности взята минимальная стоимость перевозок всего груза. Обозначим через С_ij тарифы перевозки единицы груза из пункта отправления i в пункт назначения j. Обозначим через A_i запасы груза i-м пункте отправления, а через B_j потребности груза j-м пункте назначения, а через X_j количество единиц груза переводимого из пункта отправления i в пункт назначения j.

Тогда математическая модель транспортной задачи состоит в определении минимального значения функции

(1.1)

при условиях

(1.2)

(1.3)

(1.4)

Поскольку удовлетворяется условия (1.2)−(1.4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения, вывоз груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 1. Любое неотрицательное решение X_ij=∥x_ij∥ (i=1,..,m; j=1,…,n) систем (1.2) и (1.3) называется допустимым планом транспортной задачи.

Определение 2. План при котором функция (1.1) принимает минимальное значение, называется оптимальным планом транспортной задачи.

Если сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения:

(1.5)

то модель транспортной задачи называется закрытой (или сбалансированной). Если (1.5) не удовлетворяется, то модель транспортной задачи называется открытой (или несбалансированной).

Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие (1.5).

В случае превышения запаса над потребностью, т.е. при

,

вводится фиктивный (n+1)-ый пункт назначения с потребностью

.

Соответствующие тарифы считаются равными нулю: c_i n+1=0 (i=1,…,m). После этих преобразований получим закрытую модель транспортной задачи.

Аналогично, при вводится фиктивный (m+1) пункт отправления с грузом а тарифы полагаются равными нулю: c_m+1j=0 (j=1,…,n). После этих преобразований получим закрытую модель транспортной задачи.

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

Обычно данные транспортной задачи записывают в виде таблицы:

Число переменных X_ij равно mn, где m число пунктов отправнения , а n число пунктов назначения. Число уравнений в (1.2) и (1.3) равно m+n. Так как мы рассматриваем закрытую модель транспортной задачи (выполняется равенство (1.5)), то число линейно независимых уравнений равно m+n−1. Следовательно опорный план транспортной задачи может иметь не более m+n−1 отличных от нуля неизвестных.

Если в опорном плане количество отличных от нуля компонентов равно в точности m+n−1, то опорный план называется невырожденным, а если меньше − то вырожденным.

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

Для определения начального опорного плана существует несколько методов. Мы рассмоьтрим три метода. Метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.

2. Определение опорного плана. Предварительные сведения

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

В первом случае временно исключаем из рассмотрения столбец j и изменяем запас груза пункта отправления i. Во втором случае временно исключаем из рассматрения строку i и изменяем потребность груза пункта назначения j. Далее повторяем процедуру с таблицей условий с исключенной строкой или столбцом.

В m+n−1-ом шаге получаем задачу с одним пунктом отправления и одним пунктом назначения. Остается свободной одна клетка. Запасы оставшегося пункта отправления будут равны потребностям пункта назначения. Заполнив эту клетку заканчиваем m+n−1-ый шаг и получаем опорный план.

Если на некотором шаге (но не на последнем) потребности очередного пункта назначения равны запасам пункта отправления, то временно исключаем из рассмотрения либо столбец, либо строку (только одно из двух). Тогда либо запасы данного пункта отправления, либо потребности данного пункта назначения считаем равным нулю. Этот нуль при очередном шаге записываем в очередную заполняемую клетку. Данный подход обеспечивает ровно m+n−1 занятых клеток, что обеспечивает возможность проверки полученного опорного плана на оптимальность и нахождение оптимального плана.

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

3. Метод северно-западного угла

При нахождении опорного плана транспортной задачи методом северно-западного угла, заполнене клеток таблицы условий начинают с верхней левой клетки K₁₁ поэтому метод и называется “метод северно западного угла”).

Рассмотрим метод на конкретном примере.

Пример 1. На три базы A₁, A₂, A₃ поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B₁, B₂, B₃, B₄ в количествах 150, 90, 100, 80. Тарифы перевозок представлена матрицей

.

Найти план перевозок даной транспортной задачи методом северно-западного угла.

Решение. Запишем все данные в таблицу условий:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы.

Наличие груза у поставщиков равно: ∑A_i=140+160+120=420.

Общая потребность в грузе в пунктах назначения равна: ∑B_j=150+90+100+80=420.

∑A_i=∑B_j. Модель транспортной задачи является закрытой. Следовательно она разрешима.

Найдем опорный план задачи методом северно-западного угла.

A₁≤B₁. Следовательно в клетку (A₁, B₁ ) помещаем число min(A₁, B₁)=140. Запасы пункта A₁ полностью исчерпаны. Поэтому исключаем из рассмотрения строку A₁ и будем считать потребности пункта B₁ равными 150−140=10.

A₂>B₁. Следовательно в клетку (A₂, B₁) помещаем число min(A₂, B₁)=10. Потребности пункта B₁ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₁ и будем считать запасы пункта A₂ равными 160−10=150.

Таким образом, продолжая процедуру в m+n−1-ом шаге получим:

Запишем полученный опорный план:

При этом плане стоимость перевозок вычисляется так:

F=2·140+8·10+4·90+ 1·60+3·40+6·80=1380.

4. Метод минимального элемента

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

Рассмотрим метод минимального элемента на примере.

Пример 2. Найти опорный план транспортной задачи представленной в таблице условий ниже методом минимального элемента:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из кажного пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно: .

Общая потребность в грузе в пунктах назначения равна: .

Модель транспортной задачи является закрытой. Следовательно она разрешима.

Минимальный тариф равный 1 находится в клетке (A₁, B₃). Поэтому заполняем эту клетку.

A₁>B₃. Следовательно в клетку (A₁, B₃) помещаем число 70. Потребности пункта B₃ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₃ и будем считать запасы пункта A₁ равными 150−70=80.

Минимальный тариф равный 1 находится в клетке (A₂, B₄). Поэтому заполняем эту клетку.

A₂>B₄. Следовательно в клетку (A₂, B₄) помещаем число 40. Потребности пункта B₄ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₄ и будем считать запасы пункта A₂ равными 100−40=60.

Таким образом, продолжая процедуру в m+n−1-ом шаге получим:

Запишем полученный опорный план:

При этом плане стоимость перевозок вычисляется так:

5. Метод аппроксимации Фогеля

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

Среди указанных разностей выбираем максимальную. В строке (или в столбце), которой данная разность соответствует, определяем минимальный тариф. Клетку, в которой он записан заполняем на данной итерации.

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

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

Рассмотрим метод аппроксимации Фогеля на примере 2, рассмотренной выше.

Пример 3. Найти опорный план транспортной задачи представленной в таблице условий ниже методом аппроксимации Фогеля:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из кажного пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно: .

Общая потребность в грузе в пунктах назначения равна: .

Модель транспортной задачи является закрытой. Следовательно она разрешима.

Для каждой строки A_i найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце.

В строке 1 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 3, разность между ними 3−3=0.

Для каждого столбца B_j найдем разности между двумя минимальными тарифами, записанными в данном столбце и поместим их в соответствующей дополнительной строке.

В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1.

Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этом столбце минимальный тариф равен 1 и находится в пересечении строки A ₁ и столбца B₃. Следовательно заполняем эту клетку.

A₁>B₃. Следовательно в клетку помещаем число 70. Потребности пункта B₃ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₃ и будем считать запасы пункта A₁ равными 150−70=80.

Для каждой строки A_i найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце.

В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 1 минимальный тариф равен 2, а следующий за ним равен 2, разность между ними 2−2=0. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1.

Для каждого столбца B_j найдем разности между двумя минимальными тарифами, записанными в данном столбце и поместим их в соответствующей дополнительной строке.

В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1.

Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этой строке минимальный тариф равен 1 и находится в пересечении строки A₂ и столбца B₄. Следовательно заполняем эту клетку.

A₂>B₄. Следовательно в клетку помещаем число 40. Потребности пункта B₄ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₄ и будем считать запасы пункта A₂ равными 100−40=60.

Таким образом, продолжая процедуру в m+n−1-ом шаге получим:

Запишем полученный опорный план:

При этом плане стоимость перевозок вычисляется так:

F=2·40+3·40+1·70+ 4·60+1·40+3·100=850.

Для определения оптимального плана транспортной задачи разработано нескольно методов. Мы расмотрим метод потенциалов и метод дифференциальных рент.

6. Метод потенциалов

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

Для определения опорного плана будем пользоваться методом северно-западного угла, методом минимального элемента или методом аппроксимации Фогеля рассмотренных выше.

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

При применении этих методов получаем m+n−1 занятых клеток в исходном плане. Отметим, что в некоторых клетках могут стоять нули. Полученный план следует проверить на оптимальность.

Теорема. Если для некоторого опорного плана (i=1,..,m; j=1,…,n) транспортной задачи существуют такие числа α₁, α₁, …, α_m, β₁, β₂, …, β_n, что

для всех i=1,..,m; j=1,…,n, то − оптимальный план транспортной задачи.

Определение 6.1. Числа α_i и β_j (i=1,..,m; j=1,…,n) называются потенциалами пунктов отправления и пунктов назначения, соответственно.

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

Алгоритм состоит в следующем. Предположим, что одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы α_i и β_j (i=1,..,m; j=1,…,n) из системы уравнений

где с_ij − тарифы транспортной задачи в заполненных клетках.

Так как число заполненных клеток равно m+n−1, то система (6.1) с m+n неизвестными содержит m+n−1 уравнений. Для решения данной задачи одно из неизвестных можно сделать равным нулю и найти остальные неизвестные. После этого, для свободных клеток определяем числа

Если среди чисел α_ij нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки α_ij>0, то данный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых α_ij>0 и среди данных чисел выбирают максимальное. Клетку с данным числом следует заполнить.

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

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

Если ломаннная линия, образующая цикл, самопересекается, то место пересечения не является вершиной. Некоторые циклы представлены на рисунке Рис.6.1.

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

Далее в свободную клетку переносят меньшее из чисел x_ij, находящихся в минусовых клетках. Это число прибавляют к числам, стоящим в плюсовых клетках а вычисляют из чисел, стоящих в минусовых клетках. Клетка, которая была свободной, становится занятой, а минусовая клетка с минимальным из чисел x_ij, находящихся в минусовых клетках считается свободным.

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

При сдвиге по циклу пересчета число занятых клеток не изменяется и равно m+n−1. Если в минусовых клетках имеется два и более одинаковых минимальных числа x_ij, то освобождают только одину, о остальные оставляют занятыми с нулевыми значениями.

Далее полученный опорный план проверяют на оптимальность. Для этого определяют потенциалы пунктов отправления и назначения и находят числа α_ij=β_j−α_i−c_ij для всех свободных клеток. Если среди них не окажется положительный, то получен оптимальный план. Если же среди них есть положительный, то нужно перейти к новому опорному плану. После конечнего числа шагов получяют оптимальный план.

Таким образом алгоритм нахождения оптимального плана содержит следующие этапы:

1. Нахождение опорного плана. При этом число заполненных клеток должно быть равным m+n−1.

2. Нахождение потенциалов α_i и β_j (i=1,..,m; j=1,…,n) пунктов отправления и назначения соответственно.

3. Определение числа α_ij для каждой свободной клетки. Если среди α_ij нет положительных, то получен оптимальный план транспортной задачи. Если же они имеются, то делается переход к новому опорному плану.

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

5. Проверка полученного опорного плана на оптимальность, т.е. переход к пункту 2.

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

Рассмотрим метод потенциалов на примере.

Пример 6.1. Решить транспортную задачу, заданную в таблице условий методом потенциалов:

Решение. Найдем сначала опорный план с помощью одного из методов описанного выше. Пусть это будет метод минимального элемента. Тогда после m+n−1 шагов получим следующую таблицу с опорным планом:

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными:

Полагая α₁=0, находим β₂=2, β₃=1, α₂=-1, α₃=-3, β₄=0, β₂=5

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij. α₁₂=2, α₁₄=-2, α₂₂=2, α₂₃=-3, α₃₃=-1, α₃₄=-3.

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

Среди чисел α_ij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 2 находится в пересечении строки A₁ и столбца B₂. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак “+” а остальные клетки цикла поочередно знаки “−” и “+”.

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

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными:

Полагая α₁=0, находим β₂=3, β₃=1, α₃=-3, β₁=0, α₂=-3, β₄=-2

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij. α₁₁=-2, α₁₄=-4, α₂₂=2, α₂₃=-1, α₃₃=1, α₃₄=-3.

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

Среди чисел α_ij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 2 находится в пересечении строки A₂ и столбца B₂. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак “+” а остальные клетки цикла поочередно знаки “−” и “+”.

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

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными:

Полагая α₁=0, находим β₂=3, β₃=1, α₂=-1, β₁=2, β₄=0, α₃=-1

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij. α₁₁=0, α₁₄=-2, α₂₃=-3, α₃₂=-2, α₃₃=-1, α₃₄=-3.

Среди чисел α_ij нет положительных. Следовательно данный опорный план является оптимальным.

Ответ. Оптимальный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

7. Метод дифференциальных рент

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

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

Определение 7.1. Строки, соответствующие пунктом отправления, запасы которых полностью распределены а среди пунктов назначения, связанные с этим распределением есть неудовлетворенные потребности называются недостаточными или отрицательными.

Определение 7.2. Строки, запасы которых не распределены полностью называются избыточными или положительными.

После определения недостаточных и избыточных строк, в дополнительном столбце записываем величину избытка или недостатка. Избыток записывается со знаком “+”, а недостаток со знаком “-“.

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

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

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

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

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

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

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

Пример. Найти решение транспортной задачи представленной в таблице условий методом дифференциальных рент:

Решение. Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно:

Общая потребность в грузе в пунктах назначения равна:

. Модель транспортной задачи является закрытой. Следовательно она разрешима.

Найдем оптимальный план транспортной задачи методом дифференциальных рент.

Итерация 1:

В каждом из столбцов таблицы находим минимальные тарифы и заключаем в рамки. Если в каком-либо столбце окажется несколько одинаковых минимальных тарифов, то выбираем какой-нибудь из них, причем неважно какой. Заполняем клетки, в которых стоят указанные числа. Сначала находим те столбцы (строки) в которых есть только одна клетка для заполнения. Заполнив ее, исключаем из рассмотрения данный столбец (строку) и переходим к заполнению следующей клетки.

Последовательность заполнения клеток следующее: A₁B₁, A₃B₂, A₂B₃, A₂B₄.

В результате заполнения отмеченных клеток получен условно оптимальный план.

После получения условно оптимального плана определяем избыточные и недостаточные строки. Строка A₁ является недостаточной, поскольку запасы пункта отправления A₁ распределены полностью, а потребности пункта назначения B₁ удовлетворены частично. При этом величина недостатка равна 20. Строка A₃ является недостаточной, поскольку запасы пункта отправления A₃ распределены полностью, а потребности пункта назначения B₂ удовлетворены частично. При этом величина недостатка равна 20. Строка A₂ является избыточным, поскольку запасы пункта отправления A₂ распределены не полностью. При этом величина избытка этой строки равна 40.

Нераспределенный остаток равен 40. Суммарный объем поставок равен 150.

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

В столбце 1 минимальный тариф в избыточных строках равно 4 а число стоящее в рамке равно 2. Cледовательно, разность для данного столбца равна 4−2=2. В столбце 2 минимальный тариф в избыточных строках равно 3 а число стоящее в рамке равно 2. Cледовательно, разность для данного столбца равна 3−2=1. Для столбца 3 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке. Для столбца 4 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке.

Избыточные и недостаточные оценки помещаем в дополнительный столбец, а разности в дополнительную строку:

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

Итерация 2:

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

Последовательность заполнения клеток следующее: A₁B₁, A₂B₃, A₂B₄, A₂B₂, A₃B₂.

В результате заполнения отмеченных клеток получен условно оптимальный план.

После получения условно оптимального плана определяем избыточные и недостаточные строки. Строка A₁ является недостаточной, поскольку запасы пункта отправления A₁ распределены полностью, а потребности пункта назначения B₁ удовлетворены частично. При этом величина недостатка равна 20. Строка A₃ является избыточным, поскольку запасы пункта отправления A₃ распределены не полностью. При этом величина избытка этой строки равна 20.

Нераспределенный остаток равен 20. Суммарный объем поставок равен 170.

Избыточные и недостаточные оценки помещаем в дополнительный столбец.

Определяем положительность или отрицательность нулевой строки A2. Для этого запасы этой строки увеличиваем на 1 и снова заполняем таблицу. Если суммарный объем поставок не изменится, то строка положительная, в противном случае − отрицательная.

Последовательность заполнения клеток следующее: A₁B₁, A₂B₃, A₂B₄,A₂B₂, A₃B₂:

Суммарный объем поставок не изменился (170). Следовательно строка A₂ избыточна (положительна).

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

В столбце 1 минимальный тариф в избыточных строках равно 4 а число стоящее в рамке равно 3. Cледовательно, разность для данного столбца равна 4−3=1. Для столбца 2 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке. Для столбца 3 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке. Для столбца 4 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке.

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

Итерация 3:

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

Последовательность заполнения клеток следующее: A₂B₃, A₂B₄, A₁B₁, A₂B₁, A₃B₁,A₂B₂, A₃B₂.

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

Посмотрев на таблицу выше мы видим, что избыточных и недостаточных строк нет. Нераспределенный остаток равен 0. Суммарный объем поставок равен 190. Все имеющие запасы распределены в соответствии фактическими потребностями пунктов назначения. Следовательно получен оптимальный план.

Ответ.

Оптимальный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

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

Метод
северо-западного угла.
На
примере конкретной задачи продемонстрируем
этот метод нахождения опорного плана.

З
а д а ч а 12. На три базы А₁,
А_2,
А₃
поступил
однородный груз в количествах,
соответственно равных 140,
180, 160 ед. Этот
груз требуется перевезти в пять пунктов
назначения В₁,
В₂,
В₃,
В₄,
В₅
соответственно в количествах 60,
70, 120, 130, 100 ед. Тарифы
перевозок единичного количества груза
с каждого из складов в соответствующие
пункты назначения указаны в табл.16.
Найти план перевозок данной транспортной
задачи методом северо-западного угла.

Таблица
16

Структурная
запись задачи

Поставщик	Пункт назначения	Запасы
В1	В2	В3	В4	В5
А1	2	3	4	2	4	140
А2	8	4	1	4	1	180
А3	9	7	3	7	2	160
Потребность	60	70	120	130	100	480

Р
е ш е н и е. Введем понятие маршрута –
наименование клетки А_iB_j,
где i
– порядковый
номер поставщика, j
– порядковый
номер потребителя.

Задача
является закрытой, так как количество
имеющегося у поставщиков грузов равно
объему грузов, запрашиваемых потребителями.
Здесь число пунктов отправления m=3,
а число
пунктов назначения n=5.
Следовательно,
невырожденный опорный план задачи будет
определяться числом заполненных
маршрутов (ненулевых переменных) в
количестве 5+3-1=7.

По
рассматриваемому методу заполнение
маршрутов начнем с клетки, стоящей в
левом верхнем углу. Потребность в грузе
пункта В₁
составляет 60
ед и от
поставщика А₁
можно эту потребность полностью
удовлетворить. Иначе, по маршруту А₁В₁
будет
запланирована поставка в размере 60
ед. Следующий
потребитель В₂
нуждается в поставке 70
ед груза,
что также можно выполнить, доставив
требуемый объем груза от поставщика А₁
, у которого после первой поставки
осталось 140-60=80
ед. Таким
образом, по маршруту А₁В₂
можно
запланировать доставку груза в полном
объеме. Оставшийся у поставщика А₁
объем
груза в 10
ед
запланируем доставить потребителю
В₃,

т.е.
по маршруту А₁В₃.
Так как ресурсы поставщика А₁
полностью израсходованы, потребителю
В₂
оставшиеся 110
ед груза
запланируем доставить по маршруту А₂В₃
, т.е. от
поставщика А₂.
Пользуясь подобным алгоритмом, по
маршруту А₂В₄
запланируем
доставку 70
ед, по маршруту
А₃В₄
доставку
60 ед
и по маршруту А₃В₅
оставшиеся
100 ед
груза (табл.17).

Таблица 17

Результирующая
таблица опорного плана задачи 12

Поставщик	Пункт назначения	Запасы
В1	В2	В3	В4	В5
А1	2 60	3 70	4 10	2	4	140
А2	8	4	1 110	4 70	1	180
А3	9	7	3	7 60	2 100	160
Потребность	60	70	120	130	100	480

Теперь
рассчитаем суммарные затраты на доставку
всего объема грузов:

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

.

План
имеет 7 заполненных маршрутов.
Следовательно, полученный опорный план
невырожденный, может быть проанализирован
на оптимальность и при необходимости
улучшен (см. ниже).

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

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

В
общем наборе тарифов есть два маршрута
со ставкой «1» и три маршрута со ставкой
«2», два маршрута со ставкой «3», четыре
маршрута со ставкой «4», два маршрута
со ставкой «7», по одному маршруту со
ставками «8» и «9». В такой же
последовательности будем перераспределять
груз. При равенстве тарифов маршрут
выбирают произвольно.

Начнем
с маршрута А₂В₅.
Назначим объем перевозок по нему 100
ед, а по
маршруту А₂В₃
оставшиеся
у поставщика А₂
80
ед груза.
Естественно, маршруты А₁В₅
и А₃В₅
, а также А₂В₁,
А₂В₂,
А₂В₄
должны быть
выключены из списка свободных (знак Х).
Теперь заполним маршрут А₁В₁
, назначив
по нему перевозку груза в объеме 60
ед (таков
запрос потребителя В₁)
и выведем из состава свободных маршрут
А₃В₁.
Следующим заполняем маршрут А₁В₄
количеством груза в объеме 80
ед (оставшиеся
у поставщика А₁
после заполнения маршрута А₁В₁).
Соответственно исключаем маршруты
А₁В₂,
А₁В₃.
Оставшиеся маршруты закрываем безвариантно
(табл.18).

Таблица
18

Заполнение
таблицы при методе минимального элемента

Поставщик	Пункт назначения	Запасы
В1	В2	В3	В4	В5
А1	2 60	3 Х	4 Х	2 80	4 Х	140
А2	8 Х	4 Х	1 80	4 Х	1 100	180
А3	9 Х	7 70	3 40	7 50	2 Х	160
Потребность	60	70	120	130	100	480

В
результате получаем следующий опорный
план:

,

для
которого функция цели принимает значение

.

Полученный
план имеет 7 заполненных маршрутов,
поэтому план невырожденный и может быть
в дальнейшем улучшен (если при первом
шаге начать составление плана с маршрута
А₂В₃,
то получим
план со значением функции цели F=1480).

Видим,
что для данной задачи метод северо-западного
угла дает более перспективный план.

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

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

Таблица
19

Нахождение
опорного плана по Фогелю

Склад	Потребитель	Запас	Разность по строкам
В1	В2	В3	В4	В5
А1	2 60	3 Х	4 Х	2 80	4 Х	140	1	1	1	1	–
А2	8 Х	4 60	1 120	4 Х	1 Х	180	3	3	3	0	0
А3	9 Х	7 10	3 Х	7 50	2 100	160	1	1	5	0	0
Потреб- ность	60	70	120	130	100	480
Разность по столбцам	6	1	2	2	1
–	1	2	2	1
–	1	–	2	1
–	1	–	2	–
–	3	–	3	–

В
таблице соблюдался следующий порядок
заполнения маршрутов: А₁В₁,
А₂В₃,
А₃В₅,
А₁В₄,
А₂В₂,
А₃В₂,
А₃В₄.
Максимальные
разности по столбцам и строкам выделены
жирным шрифтом.

В
результате получен следующий опорный
план:

,

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

.

Очевидно,
наилучший опорный план получен по методу
Фогеля, но и он может быть в дальнейшем
улучшен (см. ниже).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

Зачем нужен план текста?

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

Особенности написания плана

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

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

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

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

Виды планов текста

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

Назывной план

Назывной план состоит из небольших заголовков, включающих обычно от 2 до 4 слов. Глаголы в таком типе плана не используются, содержание пунктов выражается существительными в именительном падеже и прилагательными. Каждый пункт такого плана состоит из опорных слов и словосочетаний, которые отражают какой-то процесс, явление либо состояние.

Пример назывного плана для данной статьи:

1. Назначение плана текста.
2. Особенности написания плана.
3. Виды планов текста.
4. Требования к плану текста.

Вопросный план

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

Например, к текущей статье вопросный план может быть таким:

1. Зачем нужен план текста?
2. В чем заключаются особенности написания плана?
3. Какие существуют виды планов текста?
4. Как проверить правильность составления плана?

Тезисный план

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

На каждую тысячу знаков рекомендует отводить один пункт в тезисном плане. Соответственно, если в статье 5000 знаков, пунктов-тезисов должно быть 5.

Рассмотрим, что такое тезисный план на примере этой статьи:

1. Причины, по которым имеет смысл составлять план текста.
2. Действия, которые необходимо выполнить в начале написания плана.
3. Нюансы, которые необходимо учесть при составлении плана в зависимости от характера текста.
4. Виды планов могут быть разными и каждый подходит для определенных типов текста.
5. Требования, которым должен соответствовать правильно составленный план.

Опорный план

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

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

Пример опорного плана:

1. 4 причины целесообразности написания плана текста.
2. Какие особенности надо учитывать при написании плана.
3. 5 видов планов текста с примерами.
4. В каких случаях можно обойтись простым, а когда нужен сложный план.
5. Чек-лист проверки правильности составления плана текста.

Смешанный план

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

1. Зачем нужен план текста?
2. Особенности написания плана.
3. Какие существуют виды планов текста?
4. Чек-лист проверки правильности составления плана.

Простые и сложные планы текста

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

В других случаях можно ограничиться составлением простого плана, в котором пункты располагаются последовательно.

Сложный план для данной статьи может выглядеть так:

1. Зачем нужен план текста?
2. В чем заключаются особенности написания плана?
   • С чего начинается составление плана
   • Зависимость от характера текста
3. Какие существуют виды планов текста?
   • Назывной план
   • Вопросный план
   • Тезисный план
   • Опорная схема
   • Смешанный тип
   • Простые и сложные планы текста
4. Как проверить правильность составления плана?

Требования к плану текста

Правильно составленный план текста должен соответствовать ряду требований:

• Во-первых, он должен иметь четкую, логичную структуру, при взгляде на которую сразу должно быть ясно, о чем пойдет речь в статье. Все пункты плана должны быть связаны между собой. При прочтении плана не должно возникать дополнительных вопросов, ход повествования должен быть плавным, а пункты должны подробно раскрывать основной вопрос или задачу текста.
• Следите за тем, чтобы информация в разных пунктах не повторялась – в двух разных пунктах плана не должно описываться одно и то же разными словами.
• Обратите внимание на полноту раскрытия темы – план должен содержать исчерпывающую информацию и отражать все нюансы выбранной тематики.
• В плане не должно быть лишних пунктов. Если по определенной подтеме нечего написать кроме краткой формулировки, объединяйте такие пункты с другими.
• Пункты плана не должны напоминать целые абзацы, их длина не должна превышать 9 слов. Они должны содержать только краткую информацию о том, что вы собираетесь осветить в статье.
• Будьте лаконичны – придерживайтесь небольшого числа пунктов. 5-7 пунктов для простого плана вполне достаточно. Маленькие пункты можно объединять с другими.

Заключение

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

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