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

Вид материала

Содержание

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

Подобный материал:

1 2 3 4 5 6 7

Рис. 2.1. Разновидности транспортных задач

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

Σ X_ij < A_i (i=1,2, …m ), где

m – отправители;

n – получатели.

Каждая конкретная переменная входит в два условия: типа (2.1) для данного потребителя и типа (2.2) для данного поставщика.

Критерием оптимальности решения является минимум общих расходов по перевозке или с пробега в тонно-километрах (вагоно-километрах) по всем планируемым корреспонденциям. Если стоимость перевозки (расстояние) от i до j - обозначить как С_ij то целевая функция определится следующим образом:

F = Σ Σ C_ij X_ij → min

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

Сетевая задача:

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

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

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

А В Б

Рисунок 2.2. Схеме транспортной сети

+

10 Б - Пункты и размеры отправления

-8 Д - Пункты и размеры прибытия

- линии соединения – «дуги» или «звенья»

- стрелка – поток груза

Х_АВ = 8 - размер груза

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

Переменными сетевой транспортной задачи являются потоки груза по каждой дуге. Поток может включать много отправок, например, поток по дуге Б-Д включает поставки из Б в Д – 8 единиц груза, а из Б в Г – 7 единиц груза.

до решения, как правило, неизвестно, в какую сторону будет перевозиться груз по участку в оптимальном варианте. поэтому в число переменных включаются потоки в обоих направлениях, а общее число переменных принимается равным удвоенному числу участков сёти. (При значительном числе поставщиков и получателей число переменных при сетевой постановке значительно меньше чем при матричной, что облегчает решение задачи, Например, при наличии на сети 600 участков, 50 пунктов отправления и 200 пунктов назначения, число переменных при сетевой постановке составит 1200 (6002), а при матричной постановке оно будет гораздо больше (200*50=10000 переменных).

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

Σ X_ks – Σ X_kr = R_k (2.3)

где К – произвольная вершина;

R_k – погрузка (+) или выгрузка (-) (R_k -О для транзита);

Х_ks – потоки от К по всем соседним вершинам S;

Х_kr – потоки к К от соединительных вершин r;

Целевая функция закрытой сетевой задачи имеет вид:

F = Σ C_rs X_rs → min (2.4)

Суммирование выполняется по всем дугам сети.

Итак, сетевая транспортная модель включает в себя:

а) расчетную транспортную сеть

б) переменные Х_rs для каждой дуги

в) уравнение (2.3) для каждой вершины

г) целевую функцию (2.4) с коэффициентами С_rs, равными расстояниям или показателям стоимости перевозок по дугам сети.

Описанная модель сетевой задачи не учитывает пропускной способности участков сети - для этого вводится дополнительное ограничение:

Х_rs < d_rs (2.5)

где d_rs – пропускная способность участка сети r-s в направлении от r к s.

С учетом (2.5) получаем сетевую транспортную задачу с ограничением пропускной способности в простейшем виде (для перевозки одного груза).

Сетевая и матричная модели в большинстве случаев взаимозаменяемы.

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

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

Критерии оптимальности:

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

Примерами локального критерия оптимальности транспортной задачи могут служить:

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

б) при оптимизации перевозок в пределах года обычным стоимостным критерием является сумма зависящих приведенных расходов:

С = Э_зав + Э_пер + Е_n (К_пс + C_гр)

где Э_зав – зависящие от движения эксплуатационные расходы;

К_пс – капитальные вложения в подвижной состав;

С_гр – стоимость грузов, находящихся в процессе перевозки;

Э_пер – издержки по перевалкам.

в) При составлении оптимальных схем перевозок на перспективу возможно усиление пропускной способности линий в зависимости от размещения на них оптимальных грузопотоков. Поэтому в критерии оптимальности учитывается:

К_пост. – затраты на необходимое развитие пропускной способности по постоянным устройствам;

Э_нез – независящие эксплуатационные расходы.

С = Э_зав + Э_нез + Е_п + (К_пс + К_пост. + С_гр)

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

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

2.2. Решение матричных транспортных задач методом условно-оптимальных планов

Из многих методов решения матричных задач наиболее распространенными является

метод потенциалов (Канторович П.А. и Говорин М.В.)
метод условно- оптимальных планов (Лурье А.Л.)

Метод условно- оптимальны планов относится к методам сокращения невязок:

в начальном варианте допускается нарушение основных ограничений транспортной задачи;
Σ Х_ij = B_i (j=1,2, … n);
Σ X_ij = A_i (i= 1,2, … m);
допущенные невязки и разбалансировки устраняются путем внесения ряда поправок.

Основные этапы метода условно- оптимальных планов рассмотрим на примере некоторой транспортной задачи (таблицы 2.1.), требующей увязать ресурсы трёх поставщиков А1, А2, АЗ,А4 (строки таблицы 2.1.) с потребностями четырёх потребителей В1÷В6 (столбцы таблицы 2.1). В правых верхних углах клеток матрицы 2.1 показаны, стоимости перевозки С_ij единицы груза от поставщика А_i и потребителя В_j — оптимальное решение будет получено за четыре этапа решения, которые называются приближениями задачи и также показаны в таблице 2.1

Каждый этап решения состоит из следующих девяти шагов (пунктов):

Порядок вычислений

1. Построение начального варианта.

В каждом столбце матрицы (2.1) находится клетка с минимальной стоимостью:

С_kj = min С_ij

В эту клетку заносится поставка, равная полной потребности столбца:

X_ki = B_ij

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

В таблице 2.1 для первого, второго и третьего столбца минимальные стоимости обнаружены в первой строке (390, 220, 130), для четвертого, пятого и шестого столбца – во второй строке (160, 430, 420).

2. Определение сумм поставок в невязках

Находятся суммы поставок по каждой строке ΣХ_ij и разности между ресурсами поставщиков и предусмотренными поставками

R_i = A_i – Σ X_ij

Разности R называются невязками или разбалансами Так, в таблице, в приближение № 1 разбалансы показаны в последнем столбце и равны для четырёх поставщиков соответственно -183, -67, +100, +150.

Приближение № 2 (-83, -67, -0, +150)

Приближение № 3 (-56, -67, -0, +123)

Приближение № 4 ( -56, -25, -0, +81)

Приближение № 5 ( 0, -25, -0, +25)

Приближение № 6 ( 0, 0, 0, 0)

3. Проверка наличия отрицательных разбалансов.

Отсутствие. отрицательных разбапансов говорит об оптимальности найденного варианта решения (прибл. № 6). в приближение № 1 таблицы 2.1. первая строка. имеет отрицательный раэбаланс -183, поэтому поиск оптимального решения будет продолжен.

4. Классификация строк.

Строка i считается абсолютно недостаточной, если её разбаланс отрицательный и абсолютно избыточной если разбаланс положительный. При R=0 строки классифицируются на относительно избыточные и относительно недостаточные. В приближение № 1 (таблицу 2.1.) 1-я, 2-я строки абсолютно недостаточные, 3-я, 4-я строки абсолютно избыточные.

Приближение № 2 - 1-я, 2-я строки абсолютно недостаточные, 3-я, 4-я строки абсолютно избыточные.

Приближение № 3 - 1-я, 2-я и 3-я строки абсолютно недостаточные, 4-я строка абсолютно избыточна.

Приближение № 4 - 1-я, 2-я и 3-я строки абсолютно недостаточные, 4-я строка абсолютно избыточна.

Приближение № 5 - 1-я строка абсолютно достаточна; 2-я и 3-я строки абсолютно недостаточные, 4-я строка абсолютно избыточна.

Приложение № 6 – все строки достаточны.

5. Преобразование матрицы стоимостей.

- включает в себя следующие действия:

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

С_rj = min С_ij

I є U , где U – множество абсолютно и относительно избыточных строк.

Например: в приближение № 1 в первом столбце наименьшая стоимость по избыточным строкам:

С_r₁ = min (970, 1090)=970.

Во втором столбце наименьшая стоимость по избыточным строкам С_r₂ (1120,1260) = 1120, в третьем С_r₃, (1090, 1190)=1090. В четвертом, пятом, шестом столбцах С_rj min по избыточным строкам не определяется, т.к. эти столбцы не имеют поставки в единственной недостаточной первой строке.

Приближение № 2 в 1-ом столбце наименьшая стоимость по избыточным строкам:

С_r₁ = min (1090)=1090.

Во втором столбце наименьшая стоимость по избыточным строкам С_r₂ (1260) = 1260, в третьем С_r₃, (1190)=1190.

Приближение № 3 в 3-ем столбце наименьшая стоимость по избыточным строкам:

С_r₃ = min (940)=940.

В четвертом столбце наименьшая стоимость по избыточным строкам С_r₄ (1210) = 1210, в пятом С_r₅, (1160)=1160.

Приближение № 4 во 2-ом столбце наименьшая стоимость по избыточным строкам:

С_r₂ = min (1260)=1260.

В третьем столбце наименьшая стоимость по избыточным строкам С_r₃ (1190) = 1190.

Приближение № 5 во 4-ом столбце наименьшая стоимость по избыточным строкам:

С_r₄ = min (1760, 940)=940.

В пятом столбце наименьшая стоимость по избыточным строкам С_r₅ (1480, 1210) = 1210.

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

Δ_j = C_rj – C_kj

Значение Δ_j фиксируется во вспомогательной строке (строка в таблице 2.1.)

Например, в приближение № 1 в первом столбце Δ_j = 970-390 = 580, во втором стелбце Δ_j = 1120-220 = 900, в третьем столбце Δ_j= 1090-130 =960. В четвертом, пятом, шестом столбцах значение Δ не определяется т.к. поставка находится в избыточной строке.

Приложение № 2 в первом столбце Δ_j = 1090-970 = 120, во втором столбце Δ_j = 1260-800 = 460, в третьем столбце Δ_j= 1190-710 = 480. В четвертом, пятом, шестом столбцах значение Δ не определяется.

Приложение № 3 в четвертом столбце Δ_j = 940-860 = 80, в пятом столбце Δ_j = 1210-1130 = 80, в шестом столбце Δ_j= 1160-1120 = 40. В первом, втором, третьем столбцах значение Δ не определяется.

Приложение № 4 во втором столбце Δ_j = 1260-960 = 300, в третьем столбце Δ_j= 1190-870 = 320. В первом, четвертом, пятом, шестом столбцах значение Δ не определяется.

Приложение № 5 в четвертом столбце Δ_j = 1760-1200 = 560, в пятом столбце Δ_j = 1480-1470 = 10. В первом, втором, третьем, шестом столбцах значение Δ не определяется.

Приложение № 6 – значение Δ не определяется.

в) находится наименьшее значение из всех Δ_j

Δ = min Δ_j, которое прибавляется по всем стоимостям во всех недостаточных строках.

Так, для приближения № 1 получаем:

Δ = min (580, 900, 960) = 580

Все стоимости в недостаточной первой строке увеличиваю на Δ=580, в остальных не меняются. Значения стоимостей на этом этапе решения показываются дробью в правом верхнем углу клеток в недостаточных строках, причём в числителе дроби – первоначальное значение стоимости, в знаменателе – обновлённое в соответствии с шагом 5 алгоритма решения задачи.

Для приближения № 2 - Δ = min (120, 460, 480) = 120

Для приближения № 3 - Δ = min (80, 80, 40) = 40

Для приближения № 4 - Δ = min (300, 320) = 300

Для приближения № 5 - Δ = min (560, 10) = 10

Для приближения № 6 – не определяется

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

Строка S считается связанной со строкой t при соблюдении 2-ух условий:

а) в каком-либо столбце d имеется совпадение стоимостей

С_sd = C_td

б) в клетке sd имеется поставка

X_sd > 0

При этих условиях существует направленная связь клеток

sd → td

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

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

Связь строк указывает возможное направление переноса поставки. Так, в приближение № 1 после изменения стоимостей в первой строки клетка 3.1 стала допустимой. Это означает возможность переноса поставки из клетки 1.1 в клетку 3.1 , те. наличие связи между этими строками.

Приложение № 2 – из клетки 1.1 в клетку 4.1

Приложение № 3 – из клетки 2.6 в клетку 4.6

Приложение № 4 – из клетки 1.2 в клетку 4.2

Приложение № 5 – из клетки 2.5 в клетку 1.5 и из клетки 1.2 в клетку 4.2

Приложение № 6 – не определяется.

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

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

Например, в приближение № 5 новая связь появилась между клетками 2.5 и 4.2.; от прежнего цикла (приближения) осталась связь клетки 1.2 и 4.2, Цепь от абсолютно недостаточной первой строки до избыточной второй строки проходит по клеткам 2.5-1.5. и 1.2-4.2. В приближение № 1 цепь состоит лишь из одной связи 1.1-3.1, т.к. эта связь начинается в абсолютно недостаточной и кончается в избыточной строке.

Приложение № 2 – цепь между клетками 1.1 – 4.1

Приложение № 3 – цепь между клетками 2.6 – 4.6

Приложение № 4 – цепь между клетками 1.2 – 4.2

Приложение № 6 – не определяется.

8. Определение величины переноса поставок ΔХ, выполняемого одновременно по всем связям найденной цепи.

Эта величина равняется наименьшему, из следующих чисел:

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

ΔХ = min [ │R_нач │; │R_кон │; X_ij ]

Х_ij – поставки в нечетных клетках цепи, если переписать их в порядке от недостающей строки к избыточной

R_нач, R_кон – невязки в строках, где начинает и кончается цепь переноса поставок.

Например, величина переноса по цепи, найденной в приближение № 1

ΔХ = min (183, 100, 127) = 100,

а по цепи, найденной в приближение № 5:

ΔХ = min (25, 25, 35) = 25.

Приближение № 2 – ΔХ = min (83, 150, 27) = 27.

Приближение № 3 – ΔХ = min (67, 123, 42) = 42.

Приближение № 4 – ΔХ = min (56, 81, 99) = 56.

Приближение № 6 – не определяется.

9. Перенос поставок.

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

Так, в приближение № 1 переносится 100 единиц поставок из клетки 1,1 в клетку 3.1. и происходит переход к приближению № 2.

При выполнении пункта 9 во втором приближение 27 единиц поставок переносятся из клетки 1.1 в клетку 4.1 и происходит переход к приближению 3. В третьем приближение 42 единицы поставок переносится из клетки 2.6 в клетку 4.6; в четвертом приближении 56 единиц поставок переносятся из клетки 1.2 в 4.2; в пятом приближении 25 единиц поставок переносятся из клетки 5.2 в 2.4 (цепь 2.5-1.5 – 1.2-4.2). Полученное в результате шестого приближение после проверки на шаге 3 алгоритма решения оказывается оптимальным.

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

Blog

Содержание