Распределительный метод

Распределительный метод для задачи о назначениях

Распределительный метод

Сдвижков О. А.

Кандидат физико-математических наук, Российский государственный университет туризма и сервиса

Распределительный метод для задачи о назначениях

Аннотация

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

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

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

Ключевые слова: цикл, стоимость, оптимальность.

SdvizhkovO. A.

PhD in Physics and Mathematics, Russian state university of tourism and service

DISTRIBUTIVE METHOD FOR A TASK ABOUT ASSIGNMENTS

Abstract

The task about assignments, which is a special case of a transport task, has many appendices in economy. Therefore, study of methods of the decision of a task about assignments is an urgent problem.

The article considers cycles of recalculation of the allowable plans of a task about assignments, estimations of cycles of recalculation, estimations of rows and columns of the allowable plans, criteria of an optimality and the method of the decision of a task about assignments.

 This method bases on estimations of cycles of recalculation and estimation of rows and columns of the allowable plans. There is an in detail disassembled example. Moreover, the distributive method of the decision of a task about assignments applies to travelling salesman problem.

Keywords: cycle, cost, optimality.

1. Оценкицикловпересчета

Будем рассматривать задачу о назначениях [2] как задачу нахождения по заданной матрице стоимостей выполнения n исполнителями n видов работ   , такого плана распределения исполнителей по работам, при котором суммарная стоимость выполнения всех работ является минимальной. Предполагается, что каждый исполнитель выполняет только одну работу и каждая работа выполняется только одним исполнителем.

В двоичных (булевых) переменных , когда =1, если i-му исполнителю поручается j-ая работа, и =0, в противном случае, задача о назначениях сводится к задаче линейного программирования:

  (1)

  (2)

Двоичные планы Χ=(), удовлетворяющие (2), будем называть допустимыми.­

Первоначальный допустимый план Х можно получить как методом северо-западного угла, принимая =1, так и методом наименьших стоимостей. Он будет вырожденным, поскольку в нем не нулевых значений n, а ранг системы (2) равен 2n-1.

Пусть =0, γ – означенный цикл [1, стр. 242], связывающий переменные:

  (3)

Так как значения не нулевых переменных в (3) равны 1, то сдвиг [1, стр. 243] на величину   по циклу (3) приводит к допустимому плану Х* только, если

Δγ – оценка цикла пересчета γ, вычисляемая по формуле

 – сумма стоимостей, соответствующих элементам цикла γ, имеющим значение 0 (1). Следовательно, справедлива теорема.

Теорема 1. Если все оценки Δγ в допустимом плане Х задачи о назначениях удовлетворяют условию Δγ≥0, то план Х оптимальный.

2. Оценки строк и столбцов допустимых планов

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

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

Введем в рассмотрение оценки строк  и столбцов  плана Х:

Так как в формулы оценок входит функция min, то:

С помощью этих неравенств доказывается теорема 2.

Теорема 2. Если для цикла пересчета γ, расположенного в строках  (столбцах ) допустимого плана Х задачи о назначениях, выполняется , то сумма оценок этих строк (столбцов) отрицательная.

Следствие. Если сумма оценок строк  (столбцов ) допустимого плана Х задачи о назначениях неотрицательная, то не существует 2r-цикла пересчета γ, расположенного в этих строках (столбцах), для которого Δ(γ)2 расположен в строках (столбцах) сумма оценок которых отрицательна, если такого цикла нет, но r1+4, то план можно улучшить, выбирая в цикле  другую пару стоимостей, что дает:

Снова начиная перебор, приходим к соотношению 4+4>2+3, позволяющему улучшить план:

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

Оценки столбцов показывают, что второй столбец надо исключить из рассмотрения. После этого нетрудно заметить, что цикл пересчета, приводящий к улучшенному плану, так как 1+2+1+11+1, улучшить план нельзя. Следовательно, последний план является оптимальным.

Ответ: I – 3, II – 5, III – 4, IV – 1, V – 2, zmin =8.

4. Применение распределительного метода к задаче коммивояжера

Задача коммивояжера [2] – задача нахождения замкнутого маршрута минимальной длины, по которому коммивояжер (бродячий торговец) может объехать n населенных пунктов, расстояния между которыми заданы матрицей . Предполагается, что каждый из n пунктов он посещает только один раз.

Математическая модель задачи коммивояжера [2] также имеет вид (1, 2), но есть дополнительное условие, состоящее в односвязности плана Х. Поэтому, если под циклами пересчета понимать такие циклы пересчета (3, 4), которые переводят односвязный план Х в односвязный план Х*, то распределительный метод данного пункта можно применять к задаче коммивояжера.

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

Решение. Составляем первоначальный план:

Перебирая 4-циклы, приходим к соотношению 3+9>3+8, то есть план можно улучшить, но пересчет по циклу  приводит к распадающемуся маршруту 1→2→5 →6→1, 3→4→3. Поэтому этот цикл из рассмотрения исключаем.

По этой же причине исключаем из рассмотрения цикл , несмотря на то, что 4+9>2+8. В результате приходим к тому, что с помощью 4-циклов пересчета улучшить первоначальный план нельзя, переходим к 6-циклам.

Наибольшее положительное значение разность принимает для стоимостей . Составляем 6-цикл, содержащий, например, :

Так как 3+3+9>7+2+3 и пересчет по циклу приводит к односвязному маршруту, то переходим к новому улучшенному плану:

Рассматривая цикл

,

получаем 2+4+4>1+2+3, причем пересчет по циклу приводит к односвязному маршруту. Поэтому переходим к новому улучшенному плану:

Выписываем оценки строк и столбцов:

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

Ответ: 1→2→4 →3→6→5→1, zmin=19.

Литература

  1. Карпелевич Ф.И., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. – М.: Физматгиз, 1963. – С. 232-262.
  2. Сдвижков О.А. Практикум по методам оптимизации. – М.: Вузовский учебник: ИНФРА-М, 2015. – С. 45-95.

References

  1. Karpelevich F.I., Sadovskij L.E. Jelementy linejnoj algebry i linejnogo programmirovanija. – M.: Fizmatgiz, 1963. – S. 232-262.
  2. Sdvizhkov O.A. Praktikum po metodam optimizacii. – M.: Vuzovskij uchebnik: INFRA-M, 2015. – S. 45-95.

Источник: https://research-journal.org/physics-mathematics/raspredelitelnyj-metod-dlya-zadachi-o-naznacheniyax/

Большая Энциклопедия Нефти и Газа

Распределительный метод

Cтраница 1

Распределительный метод, несомненно, менее информативен, чем масс-спектральный, но он более дешев и прост.

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

Распределительный метод имеет еще РѕРґРЅСѓ важную функцию — концентрирование примесей, значение определения которых постоянно увеличивается РІ современной науке Рё технике.

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

РџРѕ нашему мнению, вполне оправдано, особенно РїСЂРё анализе очень сложных смесей, компоненты которых находятся РІ ничтожных концентрациях ( примеси), использование следующих комбинаций методов: распределение — хроматография — масс-спектрометрия.  [1]

Распределительный метод решения транспортной задачи отличается РѕС‚ метода потенциалов некоторым изменением вычислительного процесса Рё иным ( РїРѕ форме) критерием оптимальности.  [2]

Распределительный метод определения оптимального решения транспортной задачи заключается РІ том, что, отправляясь РѕС‚ некоторого начального базисного решения, последовательно1 переходим Рє РґСЂСѓРіРёРј базисным решениям СЃ меньшим значением линейной формы Рё через конечное число шагов РїСЂРёС…РѕРґРёРј Рє оптимальному решению.  [3]

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

Подсчитывая ( РїРѕ таблице 7) алгебраическую СЃСѓРјРјСѓ стоимостей РїРѕ циклам пересчета, найдем, что для неизвестной С…21 РѕРЅР° отрицательна.  [4]

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

 [5]

Модифицированный распределительный метод линейного программирования ( обычно называемый методом РњРћР”Р�), индексный метод программирования Рё статистические методы контроля Р·Р° загрузкой можно применять РЅР° мелких предприятиях Рё РЅРµ прибегая Рє помощи Р­Р’Рњ. Теоретические РѕСЃРЅРѕРІС‹ перечисленных методов сложны, РЅРѕ если принимать эти методы, РЅРµ вникая РІ теорию, то РїСЂРё применении РёС… можно обойтись простейшими арифметическими расчетами. Например, метод РњРћР”Р� РЅРµ сложнее обыкновенной карточной РёРіСЂС‹, РЅРѕ РѕРЅ может оказать большую помощь РІ составлении оптимальных производственных планов РЅР° небольших заводах, Р° также РІ оптимальном решении проблем складирования Рё распределения продукции.  [6]

Алгоритм распределительного метода заключается РІ следующем.  [7]

РџРѕ распределительному методу суммируются РІСЃРµ первичные РґРѕС…РѕРґС‹ РІ материальном производстве населения, принимавшего участие РІ создании РґРѕС…РѕРґР°, Р° также первичные РґРѕС…РѕРґС‹ предприятий, строительных организаций.  [8]

РџСЂРё распределительном методе формирования производится поочередное подключение Рє линии СЃРІСЏР·Рё источников Рё соответствующих РёРј получателей информации. Каждый источник имеет своего получателя. Телемеханические устройства обеспечивают циклические переключения СЃРѕ строгой синхронностью.  [9]

РџСЂРё распределительном методе кодирования используется лишь РѕРґРёРЅ импульсный признак ( РѕРґРЅРѕ качество), варьируется же длина РєРѕРґРѕРІРѕР№ комбинации.  [10]

Здесь используется распределительный метод: РІ порах бумаги или адсорбента содержится растворитель определенного состава, Р° разделение проводится растворителем РґСЂСѓРіРѕР№ РїСЂРёСЂРѕРґС‹, СЃРІРѕР±РѕРґРЅРѕ перемещающимся РїРѕ бумаге или пластинке.  [11]

Большим преимуществом распределительного метода РїРѕ сравнению СЃ адсорбционным является то, что адсорбент уже предварительно насыщен сильноадсорбируемым сольвентом — метанолом Рё адсорбционные силы РЅР° фенолы РЅРµ действуют, фенолы РЅРµ подвергаются никаким изменениям Рё РёС… удается полностью вымывать.  [12]

Вместо существовавшего ранее распределительного метода доведения РґРѕ цехов фондов заработной платы Рё материального поощрения РІ условиях полного хозрасчета применяют нормативный метод, который является основным методом Рё внутрипроизводственного планирования.  [13]

Аналогичная формула РІ распределительном Методе записывалась РІ РІРёРґРµ Дг Р”5 Рђ, РіРґРµ Рљ также представляет СЃРѕР±РѕР№ значение переменной xst, РІРІРѕРґРёРјРѕР№ РІ базис.  [14]

В устройстве ТМЭ-1 использован распределительный метод селекции с непрерывной передачей сигналов.

�мпульсами движения для непрерывно работающих распределителей Р в полукомплектах ДП и КП ( рис.

8 — 9) служат полуволны выпрямленного переменного тока, сформированные формирователями импульсов Р¤Р�.

РќР° ДП используются положительные полуволны, Р° РЅР° РљРџ — отрицательные. Запуск распределителя РЅР° РљРџ осуществляется автоматически РїСЂРё подаче РЅР° Р¤Р� Рё схему запуска A3 напряжения питания.  [15]

Страницы:      1    2    3

Источник: https://www.ngpedia.ru/id149934p1.html

8. Распределительный метод

Распределительный метод

Распределительныйметод решения транспортной задачиотличается от метода потенциаловнекоторым изменением вычислительногопроцесса и иным (по форме) критериемоптимальности.

Алгоритмраспределительного метода заключаетсяв следующем.

1.Отыскиваем первоначальный ациклическийплан, содержащий (k+l-1) компонент (при недостатке компонентдописываем нули).

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

3.Проделываем указанную в п.2 операциюдля каждой свободной клетки, строявсякий раз свой цикл пересчета. Врезультате в каждой свободной клеткепоявится число (положительное,отрицательное или нуль).

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

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

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

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

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

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

Основнаячасть макета выделена двойными линиями.Она содержит k×lклеток. Каждая клетка в этой частиобозначается символом (i,j).Например, клетка, стоящая во второйстроке и первом столбце, будет обозначена(2, 1). Макет содержит в себе матрицутарифов. Назначение строки vjистолбца uiбудетвыяснено в дальнейшем.

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

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

Примерцепи приведен в табл.2.

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

Еслипоследняя клетка цепи расположена водном ряду с первой, то такая замкнутаяцепь называется циклом. Некоторыеразновидности циклов показаны в табл.3.

Теорема.Пусть в макете (или матрице) из kстрок и lстолбцов произвольно отмечено k+lклеток, причем k+l£ kl.В этом случае всегда можно построитьцикл, вершины которого лежат в отмеченныхклетках (может быть не во всех).

Замечание.Числа kи lцелые, и для них не всегда будет выполненонеравенство k+l£ kl.Если одно из этих чисел — единица, этонеравенство не выполняется. Например,при k=3, l=1 имеем 3 + 1 > 3·1. Однако при k=2 и l=2будет 2+2 = 2·2, а при kи l,одновременно больших двух, неравенствовсегда выполняется.

Условиеk+l£ klисключает случаи матриц с одной строкойили одним столбцом, в которых вообщецикла построить нельзя.

Доказательство.Рассмотрим минимальный возможныйслучай: k=2, l=2 (табл.4).

Вмакете надо выбрать k+l=4, т.е. все 4 клетки. Для этого случаятеорема справедлива: выбранные клеткиобразуют цикл.

Возьмемтеперь любые k>2, l>2. Доказательство будем вести методомматематической индукции.

Допустим,теорема справедлива для макета, укоторого сумма строк и столбцов наединицу меньше взятых нами (k+l). Докажем, что при этом предположениитеорема будет справедлива для принятых(k+l).

Первыйслучай. Среди отмеченных клеток имеетсяодна клетка, единственная в ряду (строкеили столбце) (табл.5).

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

Число строкв сумме с числом столбцов будет меньше(k+l) на одну единицу, но и число отмеченныхклеток уменьшится на одну. Для этогослучая можно построить цикл по принятомудопущению.

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

Второйслучай. Нет таких ситуаций, когда клеткаодна. В каждой строке (столбце) большечем одна клетка (или нет ни одной)(табл.6).

Отметимодну клетку знаком плюс, пойдем от неепо строке, попадем в клетку, которая вдругом столбце и неединственная в нем;по столбцу перейдем в другую строку, поэтой строке в другой столбец и т.д.

Этоможно было бы продолжать до бесконечности,если бы не было конечным число отмеченныхклеток. На каком-то этапе придем в строку(столбец), в которой уже были, чем будетзамкнута цепь, т.е. получен цикл.

Вышебыло показано, что теорема справедливадля k=2, l=2, т.е. для k+l=4. По доказанному она справедлива дляслучаев: k+l=5, т.е. k+l>4; k+l=6, т.е. k+l>5; k+l>6 и т.д., т.е. для любого макета.

Допустимыйплан Х(xij)называется ациклическим (нециклическим),если набор клеток с отличными от нулякомпонентами плана xij>0не содержит ни одного цикла.

Примерациклического плана приведен в табл.7,

гдеточки обозначают клетки, в которых xij>0(xij0,будем называть Х-отмеченными.

Еслиже число положительных компонент планаN0(xij(-X)) vj- ui=aij,то план Хбудет оптимальным.

Числаui,vjназываютсяпотенциалами пунктов отправления ипунктов назначения; условия vj- ui£ aijиvj- ui=aijназываютусловиями потенциальности плана Х.

Ккаждой клетке (i,j) относятся два потенциала: i-ro пункта отправления uiиj-ro пункта назначения vj.

Условияпотенциальности словесно можносформулировать так: разность потенциаловдля всех без исключения клеток должнабыть меньше или равна тарифу, а длязанятых (Х- отмеченных) клеток она должна бытьточно равна тарифу.

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

Доказательство.Допустим, что для некоторого плана Х(xij)условия потенциальности выполнены,т.е. существует такая система чисел uiиvj,которая удовлетворяет условиям vj- ui=aijиvj- ui£ aij(табл.8).

Инымисловами, пусть план Хпотенциален. Докажем, что этот планбудет оптимальным. План Хдает значение функционалу .

Таккак мы еще не знаем, оптимален план Хили нет, то возьмем заведомо оптимальныйплан Х'(x¢ij) ипосмотрим, какое значение он доставляетфункционалу: (транспортные расходы минимальны).

Выполняются ли условия потенциальностидля плана Х'- неизвестно, но каждой клетке (i,j) макета 8, исходя из потенциальностиплана Х,соответствует неравенство vj- ui£aijили,наоборот, aij≥vj- ui.

Возьмемиз каждой клетки макета соответствующийх'ij,умножим его на левую и правую частипоследнего неравенства и сложим. Получимнеравенство .

Двойнуюсумму в правой части обозначим длякраткости буквой S:

,ее можно переписать в виде разностидвух двойных сумм: .

Преобразуемэти суммы следующим образом. Первая изних в развернутом виде дает

или

.

Аналогичновторую двойную сумму можно записатьтак:

Тогдаравенство запишется в иной форме: .

Ноесть сумма компонент плана по j-му столбцу, она равна потребности j-ro пункта назначения .

Аналогичноесть сумма компонент плана, взятая поi-й строке, она равна запасам в i-м пункте отправления .

Этиравенства сумм компонент по строке истолбцу соответственно запасам ипотребностям будут выполняться длялюбого допустимого плана, в том числеи для взятого в самом начале плана Х(xij):

Поэтомудля любых допустимых планов будем иметь

ив написанном выше равенстве суммы x¢ijможнозаменить соответствующими суммами xij:

Теперьвернемся к форме записи .

Вплане Х(xij)по условию его потенциальности длякаждой положительной компоненты xij>0 выполняется равенство vj-ui=aij.

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

.

Подставляяв

,приходим к неравенству

илиzmin≥ zX.Инымисловами, транспортные расходы по плануХ меньше или равны минимальным расходам.Но меньше минимальных они быть не могут,остается только равенство zX= zmin..ПланХ доставляет минимальные издержки, т.е.он оптимален, что и требовалось доказать.

Такимобразом, если план потенциален, то оноптимален. Это и является тем критерием,по которому судят об оптимальностиплана.

Справедливои обратное положение: если план оптимален,то он о6язательно потенциален. Этоусловие (необходимость) принимаетсябез доказательства.

Источник: https://studfile.net/preview/8123909/page:4/

Распределительный метод

Распределительный метод

Один из наиболее простых методов решения транспортных задач – распределительный метод.

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

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

Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину , можно получить новое опорное решение .

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции равняется разности двух сумм

,

где – сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+»; – сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком «-«.

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

Если разность сумм для свободной клетки (l, k) меньше нуля,
т. е. , то перераспределение груза величиной q по соответствующему циклу приведет к уменьшению значения на величину , т. е. опорное решение можно улучшить.

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

Следовательно, признаком оптимальности распределительного метода является условие

. (6.11)

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

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

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

Т а б л и ц а 6.7

Решение. Строим начальное опорное решение методом минимальной стоимости (табл. 6.8).

Т а б л и ц а 6.8

Затем вычисляем значение целевой функции на нем

= 20×1 + 30×5 + 10×8 + 40×15 = 850.

Т а б л и ц а 6.9

Находим цикл для свободной клетки (1, 2) таблицы (1, 2), он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку
= (3 + 15) — (2 + 8)= 8. Так как = 8 > 0, переходим к следующей свободной клетке (2, 1).

Для нее цикл таков: (2, 1), (1, 1), (1, 3), (3, 3), (3, 2), (2, 2) (см. табл. 6.8). Оценка = (4 + 2 + 8) — (1 + 15 + 5) = 14 — 21 = -7. Так как = -7 < 0, определяем величину груза, перераспределяемого по циклу . Приращение целевой функции DZ = -7 × 20 = -140.

Получаем новое опорное решение (табл. 6.9).

Значение целевой функции на нем = 20 × 2 + 20 × 4 +
10 × 5 + 30 × 8 + 20 × 15 = 710.

Вычисляем = (1 + 15 + 5) — (2 + 8 + 4) = 7 > 0, = (3 + 15) — (2 + 8) = 8 > 0, = (7 + 8) — (5 + 15) = -5 < 0, = (6 + 5) - (4 + 8) = -1 < 0. Оценки можно вычислять до первой отрицательной. Так как = -5 < 0, осуществляем сдвиг по циклу (2, 3), (3, 3), (3, 2), (2, 2) на величину . Приращение целевой функции DZ = -5×10 = -50. Получаем третье опорное решение (табл. 6.10).

Т а б л и ц а 6.10

Значение целевой функции на нем = 20 × 2 + 20 × 4 +
10 × 7 + 40 × 8 + 10 × 15 = 660.

Вычисляем оценки для свободных клеток:

= (1 + 7) — (2 + 4) = 2 > 0,

= (3 + 15) — (2 + 8) = 8 > 0,

= (5 + 15) — (7 + 8) = 5 > 0,

= (6 + 7) — (4 + 15) = -6 < 0.

Так как = -6 < 0, осуществляем сдвиг по циклу (3, 1), (2, 1), (2, 3), (3, 3) на величину . Приращение целевой функции DZ = -6 × 10 = -60. Получаем четвертое опорное решение (табл. 6.11).

Т а б л и ц а 6.11

Значение целевой функции на нем = 20 × 2 + 10 × 4 +
20 × 7 + 10 × 6 + 40 × 8 = 600.

Вычисляем оценки для свободных клеток = (1 + 7) — (2 + 4) = 2 > 0, = (3 + 7 + 6) — (2 + 4 + 8) = 2 > 0, = (5 + 6) — (4 + 8) =
-1 < 0. Так как = -1 < 0, осуществляет сдвиг по циклу (2, 2),
(3, 2), (3, 1), (2, 1) на величину . Приращение целевой функции DZ = -1×10 = -10. Получаем пятое опорное решение (табл. 6.12).

Т а б л и ц а 6.12

Значение целевой функции на нем = 20 × 2 + 10 × 5 +
20 × 7 + 20 × 6 + 30 × 8 = 590.

Вычисляем оценки для свободных клеток.

= (1 + 7) — (2 + 4) = 2 > 0,

= (3 + 7) — (2 + 5) = 3 > 0,

= (15 + 5) — (7 + 8) = 5 > 0.

Все оценки для свободных клеток положительные, следовательно, решение оптимально.

Ответ: min Z(X) = 590 при .

Дата добавления: 2017-05-18; просмотров: 288; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

ПОСМОТРЕТЬ ЁЩЕ:

Источник: https://helpiks.org/9-15933.html

Refpoeconom
Добавить комментарий