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

 

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

Простота алгоритма распределительного метода позволяет применять его и для решения ряда землеустроительных задач:

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

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

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

- оптимальное размещение вспомогательных хозяйственных центров на территории сельскохозяйственного предприятия (например, зернотоков, летних лагерей и т.д.);

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

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

1. Постановка задачи (словесная формулировка с указанием условий задачи и функции цели);

2. Подготовка исходной информации;

3. Составление исходной матрицы и математическая формулировка задачи;

4. Составление исходного допустимого базисного плана;

5. Анализ плана на оптимальность;

6. Улучшение плана;

7. Анализ оптимального решения задачи и возможная его корректировка.

 

2.1. РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ

 

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

 

1. Постановка задачи

 

Характер постановки задачи предопределяется экономической сущностью землеустроительной задачи, которую предстоит решить с помощью распределительного метода. Функция цели в задаче может быть ориентирована на минимум суммарных транспортных издержек или кратчайшее расстояние перевозок; на максимум чистого дохода или стоимости валовой продукции. Например, требуется составить оптимальный план транспортировки однородного груза Х _ij от «m» поставщиков к «n» потребителям, обеспечивающий минимальные суммарные транспортные расходы. Наличие груза в пунктах отправления составляет: а₁, а₂,….. а _m, а потребность в нем в пунктах назначения, соответственно: b ₁, b ₂,….. b_n. Стоимость перевозки единицы груза от i -го поставщика к j -му потребителю составляет С _ij.

 

2. Подготовка исходной информации

 

Она заключается в предварительной подготовке информации для получения требуемых по условиям задачи показателей. Например, при решении задачи на минимум транспортных расходов предварительно необходимо на плане землевладения/землепользования измерить расстояние от каждого поставщика до каждого потребителя и определить соответственно стоимость перевозки единицы груза С _ij. Полученные значения показателя С _ij представляют в виде таблицы. Далее определяются запасы груза в пунктах отправления а _i и потребности в нем (b_j) в пунктах назначения.

 

3. Составление исходной матрицы и математическая формулировка задачи

 

Исходная матрица составляется следующим образом: число строк соответствует числу пунктов отправления «m», а число столбцов – числу пунктов назначения «n». Переменные Х _ij, проставленные на пересечении строк и столбцов, выражают искомое количество груза, которое требуется перевезти из i -го пункта отправления в j -й пункт назначения. Стоимость перевозки единицы груза (или расстояние) соответственно обозначается коэффициентами С _ij, где i - номер поставщика, j - номер потребителя. Количество груза в пунктах отправления обозначается: а₁, а₂,….. а _m, потребность в пунктах назначения составляет: b ₁, b ₂,….. b_n (таблица 2.1).  

 

Таблица 2.1

Исходная матрица задачи распределительного типа

 

Пункты отправления									Запасы груза а i
	1		2		j		n
1	X	С1.1	X	С1.2	X	С1. j	X	С1. n	а1
2	X	С2.1	X	С2.2	X	С 2 . j	X	С2. n	а2
i	X	С i .1	X	С i .2	X	С i . j	X	Ci . n	а i
m	X	С m .1	X	С m .2	X	Cm . j	X	Cm . n	а m
Потребность в грузах bj	b 1		b 2		bj		bn		∑ аi

 

Математическая модель задачи, решаемой распределительным методом, в общем виде формулируется следующим образом:

Требуется составить оптимальный план перевозок, обеспечивающий минимальную суммарную стоимость перевозимых грузов (Z_min):

                                                                          (2.1)

при следующих условиях:                                                                     

1. Количество перевозимых грузов должно быть равно их запасам на пунктах отправления:

                            / i =1,2,… m /                                    (2.2)

2. Количество перевозимых грузов должно быть равно потребностям в них в пунктах назначения:

                           / j =1,2,… n /                                   (2.3)

3. Запасы грузов и потребности в них должны быть равны:

                                                                                    (2.4)

4. Переменные в задаче должны быть неотрицательны:

               Х _ij ≥0

При равенстве запасов и потребностей груза (2.4) модель называется закрытой, а при нарушенном балансе – открытой. Для приведения модели к закрытому виду вводится фиктивный поставщик или фиктивный потребитель в зависимости от типа неравенства. Если потребность в грузе превышает его запасы ( < ), то вводится фиктивный поставщик с объемом поставок

              .                                                        (2.5)

Если запасы груза превышают потребность в нем ( > ), то вводится фиктивный потребитель с объемом спроса

             .                                                          (2.6)

Для фиктивного поставщика (потребителя) стоимость перевозок груза (С _ij) принимается равной нулю, что позволяет исключить его при расчете функции цели.

 

4. Составление исходного допустимого базисного плана

 

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

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

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

- запись поставок начинается в клетку с наименьшим (ненулевым) значением С _ij. При этом в качестве поставки (Х _ij) записывается меньшее из значений запаса (а _i) или потребности (b _j), относящихся к данной клетке. Элементы С _ij этого столбца (строки) из дальнейшего рассмотрения исключаются;

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

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

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

Исходный план является:

- допустимым, если полученные значения Х _ij (распределенные поставки) удовлетворяют всем условиям задачи, а число занятых в матрице клеток не превышает m + n -1;

- базисным, если число занятых клеток Х _ij равно m + n -1;

- недопустимым (составленным неверно), если число занятых клеток больше m + n -1;

- вырожденным, если число занятых в плане клеток меньше, чем m + n -1.

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

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

Если исходный план оказался вырожденным, то его приводят к допустимому базисному виду, используя нуль-прием. Сущность нуль-приема заключается в том, что одну или несколько свободных клеток матрицы (плана) считают условно занятыми нулевыми поставками (т. е для них Х _ij =0) с таким расчетом, чтобы общее количество занятых клеток стало равным m + n -1.

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

- в каждом столбце и строке должно быть не менее одной занятой клетки, а занятая клетка не может быть единственной одновременно в столбце и строке;

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

Например, по условиям задачи имеется 3 поставщика груза (m =3) и 4 потребителя (n =4). Если при составлении исходного плана оказалось 5 занятых клеток, то план вырожденный, т.к по выражению m + n -1 их должно быть 6 (3+4-1). Необходимо, используя нуль-прием, привести план к базисному виду.

 

5. Анализ плана на оптимальность

 

На оптимальность анализируется допустимый базисный план. При этом соблюдается следующая последовательность действий:

- строятся замкнутые контуры для каждой свободной клетки матрицы (плана);

- для каждого контура (многоугольника) вычисляются числовые характеристики;

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

Замкнутые контуры (многоугольники) для каждой свободной клетки плана строятся с соблюдением следующих правил:

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

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

в) все углы контура прямые, его стороны располагаются по строкам и столбцам матрицы;

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

д) число вершин контура четное, минимальное равно четырем, максимальное не превышает m + n;

е) построение контуров можно производить как по ходу часовой стрелки, так и против неё;

ж) для каждой свободной клетки можно построить только один контур;

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

На основе матрицы для каждого построения контура вычисляют характеристику (∑ _ij) как алгебраическую сумму значений С _ij находящихся в его вершинах.

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

Признаками оптимальности плана в зависимости от направления оптимизации задачи (Z) являются:

- при решении задачи на минимум (Z_min) – наличие положительных характеристик (∑ _ij >0) у всех контуров. Если хоть одна из характеристик отрицательная, то план не оптимален и следует его улучшить;

- при решении задачи на максимум (Z_max) – наличие отрицательных или равных нулю характеристик (∑ _ij =0) у всех контуров. Если хоть одна из характеристик положительная, то план не оптимален и следует его улучшить.

 

6. Улучшение плана

 

Улучшение неоптимального плана заключается в перераспределении поставок по контуру. При этом выбор контура для улучшения осуществляется в зависимости от направления оптимизации функции цели (Z):

1) при решении задач на минимум (Z_min) для улучшения выбирается контур с наибольшей по абсолютной величине отрицательной характеристикой;

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

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

Порядок улучшения плана:

- из матрицы (плана) выносят для отдельного рассмотрения контур, выбранный для улучшения с соответствующими значениями поставок (Х _ij) со своими знаками «+», «-» в его вершинах;

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

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

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

В случае получения оптимального плана определяется значение целевой функции (Z) как сумма произведений поставок Х _ij на коэффициенты С _ij в занятых клетках плана, т.е. по формуле 2.1

 

7. Контроль решения задачи

 

Контроль правильности решения задачи выполняется посредством сравнения значений цели (Z), рассчитанных по указанной выше формуле 2.1 и по формуле:

              Z ´ _opt = Z ₁ + ∆ Z ₁ +∆ Z ₂ +……+∆ Z_k,                             (2.7)

где k – число улучшений (итераций);

Z ₁ – значение функции цели исходного допустимого базисного плана;

∆ Z ₁, ∆ Z_k – величина улучшений значений целевой функции при каждом из улучшений плана.

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

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

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

 

ПРИМЕР РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ

 

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

1. Постановка задачи (словесная формулировка условий задачи и функции цели)

В сельскохозяйственном предприятии имеются три откормочные площадки, на которых содержится молодняк крупного рогатого скота, зеленый корм для него доставляют с трех разных полей севооборотов. Потребность скота в зеленом корме по откормочным площадкам составляет (т): 1-й – 1600, 2-й – 1300, 3-й – 700.

Валовой запас (выход) зеленого корма с полей севооборотов соответственно составляет (т): 1 – 1800, 2 – 700, 3 – 1500.

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

 

Таблица 2.2

Расстояния перевозки зеленого корма с полей севооборотов

на откормочные площадки (км)

 

Поля севооборотов	Откормочные площадки
	1	2	3
I	3	6	4
II	5	7	2
III	6	8	9

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

 

2. Подготовка исходной информации

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

 

3. Составление исходной матрицы задачи

 

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

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

Суммарный запас зеленого корма на трех полях севооборотов составил 4000 т, а суммарная потребность в нем скота, размещенного на трех откормочных площадках – 3600 т, т.е. мы имеем открытую модель задачи. Алгоритм распределительного метода позволяет решать задачи только закрытого типа, поэтому открытую модель рассматриваемой задачи преобразуем в закрытую. Для этого введем фиктивную откормочную площадку (т.к. суммарный запас зеленого корма превышает суммарную потребность в нем) с объемом потребления в₄=4000-3600=400 (т) и расстояниями до неё от полей С _{i 4} =0.

Условие задачи занесем в исходную матрицу (таблица 2.3). В исходной матрице по строкам заносятся сведения по поставщикам, а по графам – по потребителям. Кроме этого имеются итоговые: столбец запасов (а _i) и строка потребностей (b_j). 

Таблица 2.3

Исходная матрица задачи

 

Поля севооборотов	Откормочные площадки								Запасы а i
	1		2		3		4 (фикт.)
I		3		6		4		0

1800