Матричная форма задачи

Таблица 3.1

Поставщики	Потребители	Итого, запас
		…	N
	с11 х11	с12 х12	….	с1n х1n	A1
	с21 х21	с22 х22	….	с2n х2n	A2
…	…	….	….	….	….
m	сm1 хm1	сm2 хm2	….	сmn хmn	Am
Итого, потребность	B1	B2	….	Bn	SAi=SBj

 

При решении задач симплексным или распределительным методом

вначале составляют вариант распределения, удовлетворяющий всем ограни чениям, но не оптимальный. Затем его поэтапно улучшают до оптимального.

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

Распределительный метод, основан на принципе принятия начального вари­анта плана с последующим его улуч­шением вплоть до получения оптималь­ной программы.

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

1. Предварительно распределяются ресурсы, перевозки и др. При этом наиболее приемлемо «правило северо-­западного угла», согласно которому максимально допустимое количество ставится верхнюю левую клетку модели. Затем заполняются следующие клетки (впра­во и вниз), заполняются и другие клет­ки до окончательного распределения всего груза. При этом количество за­полненных клеток должно составить т+п — 1, где п — количество потреби­телей, т — количество поставщиков. Если для клетки нет числовых значе­ний, то в нее проставляется нуль. Этот план называется вырожденным.

2. Для каждой свободной клетки со­ставляется многоугольник с вершина­ми, лежащими в загруженных клетках. В вершинах многоугольника простав­ляются критерии оптимальности (рас­стояние, затраты и пр.) с чередующимися знаками, начиная с положитель­ного для свободной клетки. Алгебраи­ческая сумма этих показателей выражает потенциальную возможность данной клетки, а отрицательный итог— гарантию улучшения плана. Таким об­разом, в итоге второго этапа устанав­ливается, может ли быть улучшен ис­ходный вариант и в каком направлении следует вести его улучшение.

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

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

Для начального распределения по­ставок, помимо «правила северо-запад­ного угла», применяют и другие, на­пример: минимум матрицы, метод ап­проксимации, минимум по строке, ми­нимум по столбцу. Последние являют­ся разновидностями метода минимума

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

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

Считаем, что всего с заводов ежедневно отправляется 200 т конструкций, в частности, первый поставщик от­сылает 100, второй — 50, третий — 50 т. На строительство первого моста долж­но быть доставлено 75, второго — 60, третьего — 65 т конструкций. Кроме то­го, определены затраты на производ­ство 1 м³ железобетона на каждом за­воде. Необходимо закрепить поставщи­ков за потребителями таким образом, чтобы спрос каждого потребителя пол­ностью удовлетворялся, а общие затра­ты на производство и транспортировку были минимальными. Таким образом, критерием оптимальности искомого решения является минимум затрат на изготовление и перевозку сборных мос­товых железобетонных конструкций.

Составляется исходная матрица (таблица 1).

Математически данная задача формулируется следующим образом. Тре­буется минимизировать общий пробег груза, т/км.

5Х11 + 4Х12 + Х13 +2Х21 + 6X2 2 + ЗX23 + 10X31 + 7Х32 + 2X33 ® min

Ограничения в данной задаче обуслов­лены тем, что каждый поставщик от­правляет потребителям определенное количество груза. Например, постав­щик А может отправить груз трем по­требителям, но общее его количество должно составлять 100 т. Математичес­ки это условие может быть выражено уравнением: Х11 + Х12 +Х13 = 100.

Для поставщиков Б и В имеем урав­нения:

Х₂₁ + Х₂₂ +Х₂₃ = 50

Х₃₁ + Х₃₂ +Х₃₃ = 50

К первому потребителю может по­ступать также груз от трех различных поставщиков, но только с общим коли­чеством 75 т.

Следовательно, должно выполняться условие:

Х11 + Х21 +Х31 = 75

Соответственно для второго и третьего потребителей имеем уравнения:

Х12 + Х22 +Х32 = 60

Х13 + Х23 +Х33 = 65

Шесть приведенных уравнений вы­ражают ограничивающее условие дан­ной транспортной задачи.

Для составления исходного плана перевозок пользуемся «правилом севе­ро-западного угла». Запишем матрицу задачи с заполнением верхней левой клетки (табл. 2).

В первой клетке указывают количе­ство груза, перевозимого от поставщи­ка А к потребителю 1. В ней может находиться только число 75 (т), удов­летворяющее полностью потребите­ля 1. Но поставщик А имеет 100 т гру­за, т. е. 25 т он может передать потре­бителю 2. Значит, во второй клетке может находиться не более 25 т. За­полнив две клетки, мы использовали полностью возможности поставщика А. При этом потребителю 2 доставлено 25 т груза при потребности 60 т. Недо­стающие 35 т могут быть доставлены от поставщика Б. внесем в клетку на пересечении строки Б и столбца 2 не­достающий груз 35 т, а оставшиеся у поставщика Б 15 т — в соседнюю клетку второй строки. Таким образом, возможности поставщика 2 исчерпаны. В клетку на пересечении строки В столбца 3 внесем цифру 50. Составле­ние первоначальной программы пере­возок закончено. Этот вариант не яв­ляется оптимальным, но он удовлетво­ряет всем ограничениям задачи.

 

Таблица 2

Поставщики	Потребители	Итого, запас
	5 75	4 25	1
		35	15
	10	7	2 50
Итого, потребность

 

В клетках таблицы расположены де­вять неизвестных величин задачи хij, которые обозначают объем перевозок от i-го поставщика j-му потребителю. В тех же клетках в первом верхнем уг­лу показано расстояние перевозки меж­ду пунктами, км.

По этому варианту общий пробег груза составит 5 км·75 т+4 км·25 т+ +6 км ·35 т+3 км ·15 т+2 км·50 т= =830 т· км.

На втором этапе расчетов определя­ют оптимальность плана. С целью уменьшения суммарного пробега груза улучшают первоначальную программу.

В исходном варианте заполнены пять клеток (m+n — 1=3+3-1==5), а четыре не заполнены.

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

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

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

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

Каждой свободной клетке соответ­ствует один многоугольник.

Возьмем свободную клетку АЗ в пер­вой строке. Для сохранения равнове­сия всей программы изменяют цифры в трех примыкающих к ней заполнен­ных клетках. Таким образом, четыре клетки (одна незаполненная, а три за­полненные) образуют своеобразный квадрат, одна из вершин которого при­ходится на свободную клетку, а три — на занятые.

 

-4 +1 - 6 +3

 

А3 В2
+6 -3 +7 -2

 

-5 +4 -5 +4

Б1 В1 -6 +3
+2 -6 +10 -2

Рис.3.2

 

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

Алгебраическая сумма величин, стоящих в вершинах первого прямоугольника, — 3+6- 4+1 = 0. Для незанятой клетки на пересече­нии строки Б и столбца 1 строится вто­рой аналогичный квадрат, алгебраи­ческая сумма которого +4- 5+2- 6= -5. Свободной клетке В1 соответствует более сложный многоугольник с вершинами, лежащими в шести клетках (В1, А1, А2, Б2, БЗ, ВЗ). Алгебраи­ческая сумма величин у вершины это­го многоугольника +10—5+4-6+3-2 = +4. Для четвертой свободной клетки В2 построен аналогичный квад­рат с алгебраической суммой у вер­шины +3- 2+7- 6 = +2.

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

—5; +4; +2), улучшать программу перевозок следует в направлении клет­ки с отрицательным результатом —5, т. е. наличие отрицательной алгебраи­ческой суммы в одной из клеток гово­рит о том, что программа не является оптимальной и ее нужно улучшать.

Третий этап расчетов заключается в улучшении программы. При этом в свободную клетку, как правило, пере­носится меньшее из чисел, стоящих в клетках с отрицательными знаками (в нашем примере число 35 в клетке Б2).

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

 

Таблица 3.3

Поставщики	Потребители	Итого, запас
	5 40	4 60	1
	35		15
	10	7	2 50
Итого, потребность

 

Суммарный пробег груза после такого распределения составит 5 км·40 т+4 км·60 т+2 км ·35 т+3 км·15 т+2 км·50 т=655 т·км, т. е. будет на 175 т·км меньше, чем при исходном варианте.

Затем проверяют на оптимальность второй вариант перевозок. С этой целью аналогично предыдущему строим многоугольники для клеток АЗ; Б2; В1; В2.

И т.д. до тех пор, пока распределение не будет оптимальным.