|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
П.1. Постановка транспортной задачи линейного программирования
Особое место в линейном программировании занимает так называемая транспортная задача. Традиционно она формулируется следующим образом. Некоторый однородный продукт сосредоточен у m поставщиков A1, A2, …, Am в количестве а1, а2, …, аm единиц соответственно. В данном товаре нуждаются n потребителей B1, B2, …, Bn причем их запросы составляют b1, b2, …, bn единиц товара соответственно. Стоимость перевозки единицы товара i-го поставщика j-му потребителю составляет Cij у.е. Необходимо составить план перевозок, позволяющий вывести все грузы, удовлетворить все потребности и имеющий минимальную стоимость. К настоящему времени транспортная задача нашла свое применение в областях от теоретической физики до планирования экономических процессов. Для удобства условия транспортной задачи задают в виде таблицы. Таблица 6.1.
В случае. Если суммарные запасы совпадают с суммарными потребностями, транспортную задачу называют закрытой. В противоположном случае, то есть, если запасы недостаточны или наоборот превышают потребности, то транспортная задача называется открытой. Составим экономико-математическую модель закрытой транспортной задачи. Пусть xij – количество продукта, перевозимого от i-го поставщика j-му потребителю. Целевая функция задачи будет иметь вид: Z = С11 x11 + С12 x12 +…+ С1n x1n + С21 x21 +…+ С2n x2n +…+ Сmn xmn = (6.1) = Систему ограничений получим из условий, что весь товар должен быть вывезен от поставщиков, и все потребители должны получить товар согласно своим запросам. Математически эти требования запишутся следующим образом:
Как видно из экономико-математической модели, транспортная задача является частным случаем задачи ЛП. Открытую транспортную задачу саму по себе рассматривают достаточно редко. Чаще ее сводят к закрытой транспортной задаче, пользуясь следующими правилами. 1. Если суммарные запасы превышают суммарные потребности, т.е. 2. Если суммарные запасы меньше суммарных потребностей ( Таким образом, любую открытую транспортную задачу можно свести к закрытой. П р и м е р 6.1. Перевести открытую транспортную задачу (см. таблицу 6.2) в закрытую. Таблица 6.2.
Решение. Найдем суммарные запасы. 25 + 5 + 20 + 10 = 60. Найдем суммарные потребности 15 + 5 + 10 + 20 = 50. Таким образом, перед нами открытая задача, в которой запасы больше потребностей. Вводим фиктивного потребителя, выделяем ему 10 единиц продукта. При этом таблица 6.2 преобразуется следующим образом. Таблица 6.3.
В данной задаче выполняются условия Как уже говорилось, транспортная задача является частным случаем задачи ЛП. Следовательно, ее можно решать, используя симплексный метод. Однако существуют менее громоздкие методы решения транспортной задачи. Один из них – метод потенциалов, будет рассмотрен в данном параграфе. Как и для любой задачи ЛП при решении транспортной задачи возникают следующие вопросы: 1) Как составить первоначальный опорный план? 2) Как проверить план на оптимальность? 3) Как в случае, если план не оптимальный, перейти к лучшему (не худшему) плану?
П. 2. Построение первоначального опорного плана Для транспортной задачи ЛП справедливы следующие утверждения. Теорема 6.1. Любая закрытая транспортная задача имеет решение. Теорема 6.2. Из m + n уравнений в системе ограничений транспортной задачи независимыми являются n + m – 1 уравнений. Приведенные утверждения примем без доказательств. Согласно утверждению теорем 6.1 и 6.2 первоначальный опорный план транспортной задачи можно составить всегда, причем в матрице xij(i=1, …, m; j = 1, …, n) значений компонент опорного плана содержится n + m – 1 положительный компонент. Остальные компоненты равны нулю. Значения xij удобно проставлять прямо в таблице 6.1. Существует несколько способов составления первоначального опорного плана. 1. Метод северо-западного угла. Этот метод состоит в том, что заполнение таблицы 6.1 начинается последовательно с левой верхней ячейки, без учета стоимости перевозок. 2. Метод наименьшей стоимости. В этом методе из всей таблицы выбирают клетку с наименьшей стоимостью (Сij), помещают туда наименьшее из чисел ai или bj. Если потребности потребителя Bj удовлетворены, то его исключают из рассмотрения. Обратно, если при заполнении клетки AiBj израсходованы все запасы, то в дальнейшем распределении поставок не участвует поставщик Ai. После этого выбирают следующую клетку с наименьшей стоимостью и т.д. 3. Метод двойного предпочтения. Этот метод особенно удобен в случае, когда таблица 6.1 велика. Суть его заключается в следующем. В каждом столбце знаком Ú (или любым другим, как кому захочется) отмечается клетка, имеющая наименьшую стоимость cij. Затем отмечается клетка, имеющая наименьшую стоимость в строке. В результате появятся клетки, имеющие отметки Ú Ú, клетки, имеющие отметку Ú, и клетки, не имеющие отметок. В клетки Ú Ú, помещают максимально возможные поставки, каждый раз, исключая соответствующих поставщиков или потребителей. Затем заполняются клетки Ú. Затем клетки без отметок с использованием метода наименьшей стоимости. В среднем наилучший результат дает метод двойного предпочтения, а худший – метод северо-западного угла. Замечание 6.1. Метод двойного предпочтения лучше именно в среднем. Какой метод окажется лучше в конкретной задаче сказать нельзя. П р и м е р 6.1 (продолжение). Используя метод двойного предпочтения, составить первоначальный опорный план транспортной задачи. Решение. Таблица 6.4.
Замечание 6.2. Клетки в добавленном столбце В5 заполняются в последнюю очередь, несмотря на то, что имеют нулевую стоимость. Две отметки получили клетки А2В1, А2В3, А2В4 и А3В2. Начнем составление опорного плана с заполнения клетки А2В1. Максимальная поставка в эту клетку составляет 5 ед. продукта (min (5; 15) = 5). При этом запасы поставщика А2 полностью исчерпаны, и ни одна из клеток строки А2 не может быть больше заполнена. Таблица 6.5.
Следующую поставку делаем в клетку А3В2, поскольку это последняя клетка с двумя пометками, в которую можно сделать поставку. Максимальная поставка равна 5 ед. продукции. При этом потребности потребителя В2 удовлетворены полностью, и клетки, расположенные в столбце В2, не участвуют в дальнейшем рассмотрении. Заполняем теперь клетки, имеющие одну отметку, которые не находятся в строке А2 и столбце В2. Это клетки А1В1, А1В3, А3В1, А4В1, А3В4. Сделаем максимальную поставку в клетку А3В1. Она равна 10 ед. продукта, т.к. 5 ед. продукта из необходимых 15 ед. были получены потребителем В1 от поставщика А2. Теперь потребности потребителя В1 полностью удовлетворены, столбец В1 не рассматривается. Делаем поставку в клетку А3В4. Максимально возможная поставка равна 5 ед. продукта, оставшимся у поставщика А3. При этом строка А3 в дальнейшем распределении товара не участвует. Больше клеток с отметками нет, поэтому оставшиеся клетки заполняются по методу наименьшей стоимости. Наименьшую стоимость имеет клетка А1В3. Туда можно сделать максимальную поставку 10 ед. продукта. Потребности потребителя В3 удовлетворены полностью. Столбец В3 исключается из рассмотрения. Остаются незаполненными клетки А1В4, А4В4, а также клетки добавочного столбца А1В5 и А4В5. Стоимость перевозки в клетках А1В4 и А4В4 одинакова – 4 у.е. На выбор сделаем поставку 15 ед. продукции в клетку А1В4. Оставшиеся 10 ед. продукции у поставщика А4 заносим в столбец фиктивного потребителя В5 в клетку А4В5. Первоначальное распределение товара закончено. Общая стоимость перевозок равна Z = 3 × 10 + 4 × 15 + 1 × 5 + 2 × 10 + 2 × 5 + 2 × 5 = 135 (у.е.). Замечание 6.2. При составлении первоначального плана перевозки удобно карандашом вычеркивать те строки и столбцы, которые выходят из рассмотрения. Замечание 6.3. Типичные ошибки при составлении опорного плана появляются из-за того, что решающий забывает, сколько тот или иной поставщик доставил продукта тому или иному потребителю. Для проверки достаточно просуммировать поставки по строкам и столбцам и сравнить их с соответствующими запасами и потребностями, например, для первой строки Вернемся к решению задачи 6.1. В первоначальном плане перевозок содержится 7 положительных компонент. Согласно утверждению теоремы 6.2 опорный план транспортной задачи должен содержать n + m – 1 положительных компонент, т.е. 4 + 5 – 1 = 8. В полученном плане не хватает одной положительной компоненты. Такой план перевозок, в котором число положительных перевозок меньше, чем n + m – 1 называется вырожденным опорным планом. Как будет видно в дальнейшем вырожденность не очень «испортит» процесс решения транспортной задачи. При составлении первоначального плана перевозок может возникнуть ситуация, когда число положительных компонент больше, чем n + m – 1. В этом случае план не будет являться опорным, т.к. ему соответствует линейно зависимая система векторов. В этом случае можно уменьшить число занятых клеток до n + m – 1. Для этого следует рассмотреть одно из центральных понятий данной темы – понятие цикла. Определение 6.1. Циклом называется набор клеток вида (А1 В1), Построение цикла начинается с какой-либо занятой клетки. После этого двигаются по занятым клеткам, поворачивая в них под прямым углом, стараясь возвратиться к первоначальной клетке. Выражаясь шахматными терминами, движения в цикле могут осуществляться по правилам движения ладьи. Клетки, в которых происходит поворот цикла, называются вершинами. Опорный план и вырожденный опорный план обладают свойствами ацикличности, т.е. цикла, вершинами которого являются занятые клетки, не существует. Если число занятых клеток больше, чем n + m – 1, то можно построить замкнутый цикл, с помощью которого число занятых клеток уменьшается. Построение цикла более подробно будет рассмотрено при дальнейшем решении примера 6.1.
П. 3. Оценка плана транспортной задачи на оптимальность Метод потенциалов является одним из самых распространенных методов решения транспортной задачи линейного программирования. Под потенциалами будем понимать набор чисел (ui, vj) (i = 1, …, m, cij = ui + vj. Если число занятых клеток n + m – 1, то все значения потенциалов кроме одного определяются однозначно. Справедливо следующее утверждение. Теорема 6.3. Если план (
и
Таким образом, для проверки опорного плана на оптимальность можно воспользоваться следующим алгоритмом. 1) Задаем какой-либо потенциал. Удобно приравнять к нулю потенциал той строки или столбца, в которых больше всего занятых клеток. 2) Получим систему потенциалов из условия cij = ui + vj для n + m – 1 занятой клетки. 3) Составим оценочную матрицу (aij), элементы которой получаются следующим образом aij = cij – (ui + vj). Если среди элементов оценочной матрицы нет отрицательных, то план (xij) является оптимальным, в противоположном случае план не является оптимальным. П р и м е р 6.1 (продолжение). Используя метод потенциалов, проверить на оптимальность первоначальный план перевозок. Решение. Перепишем таблицу 6.5 в следующем виде.
Таблица 6.6.
Наиболее удобно потенциалу u3 дать значение 0. Значение потенциалов v1, v2, v4 определим из системы. Таблица 6.7.
Зная потенциалы v1, v2, v4 определим потенциалы u2, u1, v3. u2 + v1 = u2 + 2 = 1 Þ u2 = - 1, u1 + v4 = u1 + 2 = 4 Þ u1 = 2, u1 + v3 = 2 + v3 = 3 Þ v3= 1. Больше ни одного потенциала определить нельзя. Это связано с тем, что полученный ранее опорный план является вырожденным. Не хватает одной заполненной клетки. Чтобы превратить вырожденный опорный план в невырожденный применяется следующий прием. Вводится фиктивная поставка размером 0 ед. продукта в незанятую клетку, соответствующую столбцу или строке, в которой находится только один неизвестный потенциал. Желательно, чтобы эта клетка не была среди добавленных и имела наименьшую стоимость. Замечание 6.3. Случается, что приходится вводить не одну, а несколько фиктивных поставок. При этом, если ввести фиктивную поставку в клетку, которая находится на пересечении неизвестных потенциалов, то, естественно, ничего определить не получится. С этим связано замечание, что фиктивная поставка вводится в ту клетку, где неизвестен только один потенциал. Делаем нулевую фиктивную поставку в клетку А4В1 со стоимостью перевозки 2 у.е. Определяем оставшиеся потенциалы: u4 + v1 = 2 Þ u4 = 0, v5 + u4 = 0 Þ v5 = 0, Система потенциалов построена. Составим оценочную матрицу (aij), рассчитывая ее элементы по формулам: a11 = с11 – u1 – v1 = 3 – 2 – 2 = –1 и т.д., a45 = с45 – u4 – v5 = 0 – 0 – 0 = 0. Получим
Индекс «0» означает номер итерации. Поскольку среди элементов матрицы a0 есть отрицательные (А1В1 и А1В5), полученный первоначальный план перевозок не является оптимальным.
П. 4. Переход от одного опорного плана транспортной задачи к другому Переход от одного опорного плана к другому происходит по аналогичной с симплексным методом схеме. Для улучшения плана в клетку плана перевозок, которой соответствует отрицательный элемент в матрице оценок. При этом план улучшается (стоимость изменяется) на qij(ui + vj – cij), где qij – размер поставки. Для перераспределения груза нужно построить цикл с началом и концом в клетке, куда делается поставка. Такой цикл можно составить единственным образом, поскольку клеток с поставками будет n + m. В клетке, куда делается поставка, ставится знак «+». Далее поочередно подставляем знаки «–» и «+» в вершинах цикла. Затем находим наименьшее значение перевозки хij, стоящей в клетке со знаком «–». Это наибольшая возможная поставка в незанятую клетку qij. При перераспределении в клетках со знаком «–» вычитаем значение qij из величины перевозки, в клетках со знаком «+» прибавляем. В случае, если циклов несколько, выбирается тот, которому соответствует наибольшее значение |qij(ui + vj – cij)|. П р и м е р 6.1 (продолжение). Найти оптимальный план перевозок для транспортной задачи, заданной таблицей 6.2. Решение. В матрице (6.3) имеются два отрицательных элемента a11= –1 и a15= –2. Следовательно, можно сделать поставки в эти клетки. Составить циклы можно непосредственно в таблице 6.7, однако это требует известной доли аккуратности, которой обладают не все читатели. Удобнее составить упрощенную матрицу перевозок
В матрице (6.4) знаком «
Определим экономию от поставки в клетку А1В1. В полученном цикле две вершины с отрицательными отметками А1В4 и А3В1. Получим q11 = min (10; 15) = 10, DZ = a11 × q11 = –1 × 10 = –10 у.е. Проделаем аналогичную операцию в случае, когда поставка делается в клетку А1В5. Получается, что поставку в клетку А3В1 наиболее выгодна. q15 = min (15; 10; 10) = 10, DZ = a15 × q15 = –2 × 10 = –20 у.е. Делаем поставку в клетку А1В5. Для этого в вершинах цикла, отмеченных знаком «+», добавим к поставкам 10 ед. продукта, в вершинах, отмеченных знаком «–» отнимем 10 ед. продукта. Получим
В плане Х1 имеется 9 занятых клеток, тогда как опорный невырожденный план должен содержать n + m – 1 = 8 занятых клеток. Для того, чтобы план Х1 стал опорным, нужно вычеркнуть одну из фиктивных нулевых перевозок. Вычеркиваем ноль в столбце фиктивного потребителя В5. Новый план Х1 нужно оценить на оптимальность. Можно снова построить систему потенциалов, однако для ручных расчетов удобнее воспользоваться следующим приемом. Подчеркнем в матрице a0 те элементы, которые соответствуют занятым клеткам матрицы Х1.
Поскольку клетка А1В5 теперь занята, то в новой матрице оценок a1 элемент a15 должен быть равен нулю. Для этого достаточно уменьшить на 2 либо потенциал u1, либо потенциал v5. При этом либо к строке А1, либо к строке В5 нужно прибавить 2. В том и в другом случае итоговые результаты совпадут. Однако для упрощения расчетов лучше выбрать ту строку или столбец, где меньше подчеркнутых элементов. В этом смысле гораздо «лучше» столбец В5. Прибавляя к столбцу В5 двойку, мы не затрагиваем ни одной подчеркнутой клетки, следовательно не надо менять ни один из оставшихся потенциалов. Получим
В матрице a1 остался отрицательный элемент a11= –1. Составляем цикл с началом в клетке А1В1.
Поскольку min(0; 5) = 0, то экономия от поставки равна нулю, т.е. план не ухудшится.
В матрице a1 отметим те клетки, которые соответствуют занятым клеткам матрицы Х2. Прибавим к столбцу А1 единицу, чтобы получить a11 = 0. При этом изменяются подчеркнутые клетки a12 и a14, которые должны быть равными нулю. Изменим потенциалы u2 и u4, отняв от строк А2 и А4 единицу. Теперь всем занятым клеткам в матрице Х2 соответствуют нули в матрице a2.
Делаем поставку в клетку А2В4.
Найдем экономию от данной поставки q24 = min (5; 5) = 5, DZ = –1 × 5 = –5 у.е. Получим (мнимый ноль в клетке А1В2 вычеркиваем)
Проведем преобразование оценочной матрицы аналогично тому, как это делалось раньше.
Поскольку в матрице a3 нет отрицательных элементов, то план Х3 является оптимальным. Найдем общую стоимость перевозок Z3 = Zопт = 5 × 3 + 10 × 3 + 10 × 0 + 5 × 1 + 5 × 2 + 15 × 2 + 10 × 2 = 110 у.е. Данный результат можно было получить иным способом, взяв за основу затраты на перевозки в первоначальном опорном плане: Z0 = 135 у.е. За три итерации была достигнута экономия DZ = DZ1 + DZ2 + DZ3 = 20 + 0 + 5 = 25 у.е. Тогда Zопт = Z0 – DZ = 135 – 25 = 110 у.е. Такой двойной подсчет может служить простой проверкой правильности расчетов. Проведем небольшой анализ решения. Оптимальный план перевозок задается матрицей Х3, причем общая стоимость перевозок Zопт = 110 у.е. У первого поставщика осталось не вывезенными 10 ед. продукта (вспомним, что клетка А1В5 соответствует фиктивному потребителю). Можно выяснить, является ли полученный оптимальный план перевозок единственным. Для этого нужно в матрице a3 подчеркнуть элементы, соответствующие занятым клеткам в матрице Х3.
В матрице a3 есть нулевые элементы, которые не соответствуют занятым клеткам матрицы Х3, поэтому полученное оптимальное решение не единственное (можно сделать поставку в клетки с нулевыми оценками, от этого стоимость перевозок не изменится). Более того, согласно свойствам решений задачи линейного программирования, линейная комбинация оптимальных решений транспортной задачи будет оптимальным решением.
Примеры для самостоятельного решения Решить транспортную задачу, в которой имеющиеся запасы однородного груза ai, его потребности bk и стоимости перевозок единицы груза из пункта Ai в пункт Bk указаны в следующих таблицах.
7. Элементы целочисленного линейного |
Последнее изменение этой страницы: 2017-04-12; Просмотров: 1168; Нарушение авторского права страницы
.
(6.2)
, то следует ввести фиктивного потребителя. Его потребности будут равны разности 
, а цена перевозки ему товара от любого поставщика будет равна нулю.
), то следует ввести фиктивного поставщика, выделив ему запасы продукта в размере 
. Цена перевозки также будет равна нулю.
. Значит открытая транспортная задача сведена к закрытой.
) транспортной задачи является оптимальным, то для соответствующей ему системы потенциалов 
и 
выполняются условия: 
. (6.3)
. (6.4)
» обозначается незанятая клетка. Рассмотрим два цикла, с помощью которых делаются поставки в клетки А1В1 и А1В5.
, 
.
.
.
.
, 
.
.
.
, 
.
.