мого решения. Ниже будут рассмотрены некоторые методы решения задач линейного программирования на конкретных примерах.
Полученное оптимальное решение задачи должно быть тщательно проанализировано. Следует иметь в виду, что оптимальным данное ре шение (план) будет только при тех условиях, которые были учтены при составлении математической модели. Чем полнее и точнее были учтены все факторы, влияющие на ход изучаемого процесса, тем точнее будет рассчитанный план.
§ 55. Оптимальное раскрепление грузополучателей за отдельными участками порта
Для оптимального распределения грузооборота между пунктами отправления и назначения (составления оптимальных планов матери ально-технического снабжения и др.) используется транспортная за дача линейного программирования.
В условиях порта при помощи решения транспортной задачи можно производить оптимальное раскрепление клиентуры за отдельными гру зовыми районами, специализацию отдельных районов и причалов и т. д.
Содержание и математическая модель такой задачи в виде системы линейных уравнений и неравенств (185) — (188) приводились в преды дущем параграфе.
Рассмотрим решение задачи на конкретном примере1. Пусть в порту имеются три отдельно расположенных причала Аи А.г, А 3 для перера
|
ботки песка с грузооборотом соответст |
|
|
|
|
|
|
венно |
аг = 400 |
тыс. т, а2 = 550 тыс. т |
|
|
Т а б л и ц а |
13 |
|
и а3 = |
350 тыс. т. |
Песок |
доставляется |
|
|
|
автотранспортом на 4 предприятия Вг, |
|
|
Предприятия |
|
|
В 2, В 3, В4, потребность каждого из кото |
Причал |
в. |
вг |
в3 |
в4 |
|
рых в песке составляет Ьг |
= 250 тыс. т, |
|
|
|
|
|
|
|
|
Ьп — 400 тыс. т, |
Ь3 = 200 |
тыс. т, |
Ь4 = |
Ai |
40 |
70 |
60 |
80 |
|
= 450 |
тыс. т. |
Стоимость перевозки 1 т |
|
а2 |
30 |
75 |
70 |
70 |
|
песка |
(в коп.) |
|
СД, |
Ci2> |
С13 |
^ 20 |
Аз |
60 |
65 |
75 |
60 |
|
С22, С23 и т. |
д. от |
причалов до пред |
|
|
|
|
|
|
приятий приведена в табл. 13. |
|
|
|
|
|
14). |
|
Все исходные данные вносятся в специальную матрицу (табл. |
В правом верхнем углу каждой средней клетки матрицы проставляется соответствующая стоимость перевозки 1 т песка от причала до потреби теля Ctj. Нижняя часть клетки является операционным полем, куда записываются значения определяемых переменных х и . Кроме того, выделяются колонка и строка для подсчета вспомогательных величин (потенциалов) а г и
Если по тем или иным причинам перевозка из какого-либо пункта {причала) до другого пункта (предприятия) недопустима, то соответ
ствующие клетки матрицы могут зачеркиваться |
или в них ставятся |
1 Во всех примерах данной главы приведены условные цифровые данные. |
10* |
291 |
|
|
|
|
|
|
Т а б л и ц а |
14 |
|
Оценочные |
|
Предприятия-получатели |
|
|
|
|
|
|
|
|
|
|
Количест |
|
числа |
В, |
в 2 |
В г |
1 |
В п |
Причал А ■ |
|
во |
груза |
|
|
|
|
|
|
на прича |
|
|
|
|
|
|
|
|
|
Pi |
р 2 |
Р, |
|
Р п |
|
ле <3- |
|
|
|
|
|
|
|
|Сц |
|С« |
|6 l3 |
|
| £ i n |
|
|
A i |
« 1 |
* 1 1 |
* 1 2 |
*13 |
|
*17! |
|
|
|
|
[ 6 2 1 |
[С22 |
|Сгз |
|
|6 2 7 I |
|
|
|
а 2 |
* 2 1 |
* 2 2 |
*23 |
|
*271 |
|
а 2 |
|
|
|Cm i |
|С*П2 |
|С т з |
|
|С т п |
|
|
А т |
°&7П |
* m i |
Х ТП2 |
х пг з |
|
х т п |
|
а т |
Потребность |
b j |
b x |
&2 |
^3 |
|
ь п |
|
|
произвольные, заведомо высокие затраты на перевозку, что исключает использование этого направления в оптимальном плане.
Задача методами линейного программирования решается по опре деленным формализованным правилам (алгоритму). При этом каждый метод имеет свой алгоритм решения, следуя которому и отыскивают оптимальный план. При решении задачи линейного программирования составляется ряд систематически улучшаемых вариантов, позволяю щих постепенно приблизиться к искомому оптимальному варианту. Для оценки оптимальности варианта в различных методах решения задач выработаны отличительные признаки, которые и позволяют уста новить оптимальность того или иного варианта.
Используем для решения поставленной задачи метод потенциалов а. Составим рабочую матрицу (табл. 15) и занесем в нее все цифровые
исходные данные.
К решению задачи приступают с составления исходного плана, устанавливающего первоначальное распределение перевозок между предприятиями. При этом можно начинать распределение ресурсов (перевозок) с верхней левой клетки матрицы и последовательно разме стить весь грузооборот 1, 2 и 3-го причалов до его полного исчерпыва ния (метод «северо-западного угла»).
Однако применяют и другие методы составления исходного плана, которые позволяют получить улучшенный исходный план и этим самым
уменьшить число шагов (итераций) приближения к оптимальному плану.
В примере в основу составления исходного плана положим прин цип заполнения клеток по самым дешевым направлениям перевозок.1
1 В учебнике не излагаются теоретические основы различных методов реше ния задач линейного программирования. С ними читатель может познакомиться в специальной литературе [72, 52].
|
Оценка |
П р и ч а л |
|
|
ах=0 |
^2 |
а2= —Ю |
|
II СП
|
^3 |
1
|
|
bi
|
|
|
|
|
Т а б л и ц а |
15 |
|
|
П р е д р и я т и я |
|
|
|
|
В, |
|
в2 |
в, |
|
в4 |
|
а1 |
|
|
р2=70 |
|
|
Р*==80 |
|
3 i = 4 0 |
|
Ра = 60 |
|
|
|
| |
40 |
70 |
| |
60 |
I |
80 |
|
— |
|
50 |
200 |
150 |
400 |
|
|
©*---- |
|
|
---- ►© |
|
|
| |
30 |
|
| |
70 |
А |
70 |
|
175 |
| |
|
250 |
— |
|
300 |
|
550 |
|
|
|
| |
60 |
| 65 |
1 75 |
| |
60 |
|
_ |
|
350 |
_ |
|
|
|
350 |
|
|
4 |
|
|
— ►© |
|
|
|
|
0 |
|
|
|
|
250 |
400 |
200 |
|
450 |
|
1300 |
По этому принципу на предприятие Вг направим 250 тыс. т песка с при чала А 2, на предприятиеВ г — 350 тыс. т песка с причала А 3 косталь ную часть потребного песка с причала А и так как на причале А 3 пе сок исчерпан, и т. д. При распределении всех ресурсов сумма чисел в клетках каждого столбца должна равняться ограничению по столбцу bj и в каждой строке—ограничению по строке at.
Далее переходим к улучшению исходного плана и отысканию оп тимального решения.
План будет оптимальным в том случае, если во всех клетках вы
полняются условия: |
|
|
|
при |
х и > 0 |
|
|
|
|
|
|
|
|
§7 4~ |
— Сij > |
(189) |
|
|
|
Pi 4" |
CU, |
|
(190) |
где |
аг и |
|
— вспомогательные |
величины |
(оценочные числа), рас |
|
|
|
считываемые для каждого варианта раскрепления |
|
|
|
предприятий за причалами. |
|
Значение |
вспомогательных величин |
a t |
и |37можно определить |
при |
условии, |
что в матрице заполнено |
не менее т + п — 1 клеток. |
При меньшем количестве занятых клеток |
в одной или нескольких |
свободных |
клетках ставится нуль («значащий нуль»), что позволяет |
определить |
все оценочные числа. |
|
|
|
Зададимся произвольным значением % = 0 и рассчитаем значения а и Р для всех пунктов отправления Ai и пунктов назначения By. Пользуясь уравнением (189), находим:
Ра = |
С 12 — |
a j |
= |
70 |
— |
0 = |
70; |
Рз = |
с13— |
= |
60 — О = |
60; |
|
Р« = |
См — |
ос4 = |
80 |
— |
0 ^ = |
80; |
«2 = |
С24 — Р4 = |
70 — 80 = |
—10; |
сс3 — |
С 32 — Р 2 |
— |
05 ■— |
/0 — — 5, |
P i = |
Сн — а 2 = |
30 — (—10) = |
40. |
Занесем все эти величины в соответствующие клетки табл. |
15. |
|
|
Проверим условия соблюдения оптимальности исходного плана для свобод |
ных клеток, в которых значение x%j = |
0, по неравенству Ру- + |
а г < |
Qy'- |
опти |
Для |
клетки |
1 —1: Р4 + а 4 = 40 + 0 = |
40 < |
Си = |
40 |
условие |
мальности выполняется. Аналогичный расчет делаем для других свободных клеток:
для |
2—2 |
70 + |
(—10) = |
60 < |
С22 = |
75; |
для 2—3 |
60 + |
(—10) = |
50 < |
С23 = |
70; |
для |
3—1 |
40 |
4 - |
( —5) = |
35 < |
С81 = |
60; |
для |
3—3 |
60 |
+ |
( — 5) = |
55 < |
С33 = 75; |
для |
3—4 |
80 + |
( —5) = |
75 > |
С34 = |
60. |
Так как условие оптимальности не соблюдено, поскольку имеются свобод ные клетки, для которых а* -г Ру > Сц, необходимо план улучшить.
Для этого выбираем свободную клетку, где в наибольшей степени не соблю дено условие оптимальности. В нашем случае имеется всего одна такая клетка 3—4. Это свидетельствует о том, что в данной клетке при оптимальном плане должна быть определенная величина распределяемого ресурса.
Улучшение производится перемещением ресурсов (груза) из одной клетки в другую путем обхода по замкнутому прямоугольному контуру («цепочке»). Построение контура начинается из выбранной свободной клетки 3—4. Из нее линия контура идет в заполненные клетки 1—4, далее в клетку 1—2, опускается вниз в клетку 3—2 и снова возвращается в клетку 3—4.
Цепочка начинается и заканчивается в избранной свободной клетке, идет по свободным и занятым клеткам. Необходимо стремиться, чтобы цепочка имела наименьшее число поворотов, но повороты должны быть только в заполненных клетках. Цепочка может образовывать как четырехугольную, так и сложную фигуру. Двигаясь из клетки 3—4 по контуру, расставляют в каждой клетке зна ки плюс и минус, означающие сдвиг в распределении ресурсов (груза). Знак минус указывает, что из данной клетки груз частично или полностью изымает ся, а знак плюс — что груз в данную клетку добавляется.
Наибольшее количество груза, которое можно переключить из клетки 3—2 в клетку 3—4, равно 150.
Изменим (улучшим) на это количество план. Чтобы удовлетворить потреб ность в песке всех предприятий, такое же количество песка переместим из клетки 1—4 в клетку 1—2. Новое распределение перевозок представлено в табл. 16.
Далее проверяется улучшенный вариант плана на соблюдение условий оп тимальности по новым значениям вспомогательных величин (условных оценок). Если условия оптимальности не соблюдаются, то делают следующие шаги (ите рации) улучшения до тех пор, пока во всех клетках не будет выдерживаться условие оптимальности.
Рассчитаем значение вспомогательных величин, соответствующих новому
плану |
распределения: а 4 = 0 , Р2 = 70, |
|33 = 60, а 3 = —5, (34 = 65, а 2 = 5, |
Рх = |
25. |
|
|
|
|
|
|
Проверим соблюдение условия оптимальности в свободных клетках (в за |
полненных клетках оно соблюдается): |
|
в клетке |
1 —1 |
0 -f 25 = |
25 < |
40; |
в клетке |
1—4 |
0 4- 65 = |
65 < |
80; |
в клетке 2—2 |
5 + |
70 = |
75 < |
75; |
в |
клетке 2—3 |
5 + |
60 |
= |
65 < |
70; |
в |
клетке 3—1 |
—5 4- 25 |
= |
20 < |
60; |
в клетке 3—3 |
—5 4- 60 |
= |
55 < |
75. |
|
|
|
|
|
Т а б л и ц а 16 |
|
Оценка |
|
|
Предприятия |
|
|
Л, |
в, |
в. |
в. |
|
Причал |
|
|
|
|
a i |
|
“г |
P i= 25 |
Р„=70 |
(5,=60 |
Р4= 6 5 |
|
|
|
|
|
ocj=0 |
| |
40 |
| |
70 |
| |
60 |
I |
80 |
— |
|
200 |
|
200 |
|
— |
400 |
|
| |
30 |
1 75 |
| |
70 |
| |
70 |
а 2=5 |
250 |
|
— |
|
— |
|
300 |
550 |
|
| |
60 |
| |
65 |
1 |
75 |
| |
60 |
а3= —5 |
— |
|
200 |
|
— |
|
150 |
350 |
|
250 |
|
400 |
|
200 |
|
450 |
1300 |
Т аки м о б р а зо м , д л я |
в сех св ободн ы х кл еток a j + |
< |
Сг-у. С л ед о в а т ел ь н о , |
у л уч ш ен н ы й |
пл ан б у д ет |
опти м альн ы м . |
|
|
Р а сх о д ы |
по |
д о ст а в к е |
п еск а с пр и ч ал ов д о п р едп р и я ти й |
по эт о м у п л а н у б у д у т |
м иним альны м и |
и состав я т |
|
|
тп
2 |
2 |
C|j * |, = 200 000 • 70 + 200 000 -60+250 000 • 30 + 300 000• 70 + |
»=1/=1 |
|
|
|
|
+ |
200 0 0 0 - 6 5 + |
150 0 0 0 -6 0 = 76 500 000 |
к о п .= 7 6 5 ты с. |
р у б . |
П о п ер в он ач ал ь н ом у |
п л а н у , со ст а в л ен н о м у |
по п р и н ц и п у |
сам ы х деш евы х |
н а п р а в л ен и й |
п ер ев о зо к , |
эти р а сх о д ы состав л я л и |
|
тп
2 |
2 Ci j Xi j = 787,5 ты с. р у б ., т. е . были на 2 2 ,5 ты с. р уб . выше. |
г=1/=1
§56. Оптимальное распределение перегрузочных машин по объектам работы
Впрактической деятельности работников порта возникает необ ходимость распределения имеющегося парка перегрузочных машин по отдельным причалам и участкам работы.
Особенно большой маневренностью обладают плавучие и самоход ные стреловые краны на гусеничном и пневматическом ходу. Благодаря своей подвижности они свободно могут перемещаться с одного причала на другой, что позволяет их использовать в разное время на различ ных объектах работы.
Оптимальный план расстановки кранов по объектам работы может быть составлен с использованием методов линейного программирова ния.
За критерий оптимальности в таких задачах могут быть приняты минимальные суммарные затраты машино-часов на выполнение задан ного объема работы, минимальные простои судов под обработкой, ми нимальные эксплуатационные расходы по перегрузочным работам
