Метод Гомори

Варианты заданий

Таблица 6.24

Варианты заданий

Таблица поставок

Таблица 6.23

Таблица поставок

Таблица 6.22

Таблица поставок

Таблица 6.21

Таблица поставок

Таблица 6.20

Таблица поставок

Таблица 6.19

Таблица поставок

Таблица 6.18

Таблица поставок

Таблица 6.17

Таблица поставок

Таблица 6.16

Таблица поставок

Таблица 6.15

Таблица поставок

Таблица 6.14

Таблица поставок

Таблица 6.13

Таблица поставок

Таблица 6.12

Таблица поставок

Таблица 6.11

Таблица поставок

Таблица 6.10

Таблица поставок

Таблица 6.9

Таблица поставок

Таблица 6.8

Таблица поставок

Таблица 6.7

Таблица поставок

Таблица 6.6

Таблица поставок

Таблица 6.5

Таблица поставок

Таблица 6.4

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1
A2
A3
A4
Потребности заводов-потребителей

С учетом фиктивного поставщика математическая модель будет иметь вид:

2 этап: разработка исходного опорного плана.

Для отыскания исходного опорного плана воспользуемся методом минимальной стоимости. Согласно таблице поставок (таблица 6.4) минимальная стоимость соответствует клеткам строки фиктивного поставщика. Рассмотрим, к примеру, клетку «4-3». Объем поставок для данной пары поставщик-потребитель составит:

Запишем в клетку «4-3» объем поставок x₄₃ =200 (таблица 6.5). Запасы фиктивного поставщика исчерпаны (зачеркиваем остальные клетки данной строки, они в дальнейших рассмотрениях не участвуют).

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1
A2
A3
A4	0				200-200 = 0
Потребности заводов-потребителей			300-200 =100

Из свободных клеток минимальная стоимость соответствует клеткам «1-1» и «1-4» (c_ij =1), выберем, к примеру, клетку «1-4». Вписываем в данную клетку объем поставок x₁₄ =100 (таблица 6.6). Запасы первого поставщика исчерпаны (зачеркиваем остальные клетки данной строки, они в дальнейших рассмотрениях не участвуют).

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1				100-100=0
A2
A3
A4
Потребности заводов-потребителей				300-100 = 200

Следующая свободная клетка с наименьшей стоимостью поставок единицы груза – клетка «2-1» (c₂₁ =2). Объем поставок для данной пары поставщик-потребитель составит:

Запишем в клетку «2-1» объем поставок x₂₁ =100 (таблица 6.7). Потребность первого завода-потребителя полностью удовлетворена (зачеркиваем незадействованную клетку данной колонки – «3-1», она в дальнейших рассмотрениях не участвуют).

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1
A2					200-100 = 100
A3
A4
Потребности заводов-потребителей	100-100 = 0

Оставшиеся запасы второго поставщика целесообразно направить для удовлетворения потребностей второго завода-потребителя, так как стоимость доставки единицы груза здесь наименьшая (c₂₂ =3). Вписываем в соответствующую клетку объем поставок x₂₂ =100 (таблица 6.8).

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1
A2					100-100 = 0
A3
A4
Потребности заводов-потребителей		100-100 = 0

Таким образом, потребность второго завода-потребителя полностью удовлетворена и мощность второго поставщика полностью задействована, поэтому вычеркиваем незадействованные клетки «2-3», «2-4» и «3-2», в дальнейших рассмотрениях они не участвуют.

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

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1	1
A2
A3
A4
Потребности заводов-потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

3 этап: проверка вырожденности опорного плана.

Количество задействованных клеток в таблице поставок (таблица 6.9): N =6. Ранг r системы ограничений транспортной задачи равен:

.

Так как, , следовательно, опорный план транспортной задачи вырожденный. Определим количество фиктивных поставок:

.

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

Заводы-потребители Базы-поставщики	B1	B2	B3	B4	Запасы баз-поставщиков
A1
A2
A3
A4
Потребности заводов-потребителей

4 этап: расчет потенциалов.

Для первой строки принимаем α ₁=0. Рассмотрим загруженную клетку «1-4»:

.

Для загруженной клетки «3-4»: .

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

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4
Потребности потребителей
βj	–8	–7	–4

5 этап: проверка плана на оптимальность.

По таблице 6.11 для незагруженных клеток проверим условие оптимальности ():

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-3»: ,

«2-4»: ,

«3-1»: ,

«4-1»: ,

«4-2»: ,

«4-4»: .

Опорный план не оптимальный, так как имеются клетки, для которых условие оптимальности не выполняется: «2-3», «2-4», «4-4».

6 этап: поиск «вершины максимальной неоптимальности» (ВМН).

Для клеток «2-3», «2-4», «4-4» рассчитаем оценки: .

,

,

.

.

Выбор ВМН неоднозначен (можно выбрать любую), примем клетку «4-4» в качестве ВМН. Пометим ее в таблице поставок знаком (таблица 6.12).

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4
Потребности потребителей
βj	–8	–7	–4

7 этап: построение контура перераспределения поставок.

Построим контур перераспределения поставок (таблица 6.13).

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3			7
A4
Потребности потребителей
βj	–8	–7	–4

В таблице 6.13 начиная с ВМН разделим вершины на загружаемые

и разгружаемые.

8 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.

В рамках построенного контура из клеток со статусом «разгружаемые» выберем клетку с наименьшим объемом поставок (полностью разгружаемую клетку):

.

Выбор неоднозначен, полностью разгружаем, к примеру, клетку x ₃₄ и загружаем ВМН (x ₄₄=200). Для обеспечения соответствия объемов запасов и потребностей перераспределим поставки по контуру – разгрузим клетку «4-3» на 200 ящиков (x ₄₃=0) и загрузим на этот же объем клетку «3-3» (x ₃₃=100+200=300).

9 этап: получения нового опорного плана.

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

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков
A1
A2
A3
A4
Потребности потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

II итерация:

1 этап: проверка вырожденности опорного плана.

Опорный план невырожденный.

2 этап: расчет потенциалов.

Результаты расчета потенциалов приведены в таблице 6.15.

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–3	–2

3 этап: проверка плана на оптимальность.

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-3»: ,

«2-4»: ,

«3-1»: ,

«3-4»: ,

«4-1»: ,

«4-2»: .

Опорный план не оптимальный, так как имеются клетка «2-3», для которой условие оптимальности не выполняется.

4 этап: поиск «вершины максимальной неоптимальности» (ВМН).

Клетку «2-3» примем в качестве ВМН. Пометим ее знаком (таблица 6.16).

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–3	–2

5 этап: построение контура перераспределения поставок.

Построим контур перераспределения поставок (таблица 6.17).

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2		3
A3
A4						–1
Потребности потребителей
βj	–3	–2

В таблице 6.17 начиная с ВМН разделим вершины на загружаемые

и разгружаемые.

6 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.

В рамках построенного контура из клеток со статусом «разгружаемые» выберем клетку с наименьшим объемом поставок (полностью разгружаемую клетку):

.

Полностью разгружаем клетку x ₂₂ и загружаем ВМН (x ₂₃=100). Для обеспечения соответствия объемов запасов и потребностей перераспределим поставки по контуру – разгрузим клетку «3-3» на 100 ящиков (x ₃₃=200) и загрузим на этот же объем клетку «3-2» (x ₃₂=100).

7 этап: получения нового опорного плана.

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

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков
A1
A2
A3
A4
Потребности потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

III итерация:

1 этап: проверка вырожденности опорного плана.

Опорный план невырожденный.

2 этап: расчет потенциалов.

Результаты расчета потенциалов приведены в таблице 6.19.

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–1	–2

3 этап: проверка плана на оптимальность.

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-2»: ,

«2-4»: ,

«3-1»: ,

«3-4»: ,

«4-1»: ,

«4-2»: .

Опорный план не оптимальный, так как имеются клетка «3-1», для которой условие оптимальности не выполняется.

4 этап: поиск «вершины максимальной неоптимальности» (ВМН).

Клетку «3-1» примем в качестве ВМН. Пометим ее знаком (таблица 6.20).

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–1	–2

5 этап: построение контура перераспределения поставок.

Построим контур перераспределения поставок (таблица 6.21).

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2	2
A3
A4						–1
Потребности потребителей
βj	–1	–2

В таблице 6.21 начиная с ВМН разделим вершины на загружаемые

и разгружаемые.

6 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.

В рамках построенного контура из клеток со статусом «разгружаемые» выберем клетку с наименьшим объемом поставок (полностью разгружаемую клетку):

.

Полностью разгружаем клетку x ₂₁ и загружаем ВМН (x ₃₁=100). Для обеспечения соответствия объемов запасов и потребностей перераспределим поставки по контуру – разгрузим клетку «3-3» на 100 ящиков (x ₃₃=100) и загрузим на этот же объем клетку «2-3» (x ₂₃=200).

7 этап: получения нового опорного плана.

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

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков
A1
A2
A3
A4
Потребности потребителей

Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):

.

VI итерация:

1 этап: проверка вырожденности опорного плана.

Опорный план невырожденный.

2 этап: расчет потенциалов.

Результаты расчета потенциалов приведены в таблице 6.23.

Потребители Поставщики	B1	B2	B3	B4	Запасы поставщиков	αi
A1
A2
A3
A4						–1
Потребности потребителей
βj	–3	–2

3 этап: проверка плана на оптимальность.

«1-1»: ,

«1-2»: ,

«1-3»: ,

«2-1»: ,

«2-2»: ,

«2-4»: ,

«3-4»: ,

«4-1»: ,

«4-2»: .

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

Ответ: оптимальное распределение поставок:

.

Данное распределение поставок обеспечит оптимальные транспортные издержки в размере 2300 усл. ден. ед.

Четырем торговым базам поставляется однотипное оборудование с трех заводов. Исходные данные представлены в нижеследующей таблице.

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

1)		2)		3)
4)		5)		6)
7)		8)		9)
10)		11)		12)
13)		14)		15)
16)		17)		18)
19)		20)		21)
22)		23)		24)
25)		26)		27)
28)		29)		30)
31)		32)		33)

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

оно должно быть линейным;

должно отсекать найденный оптимальный нецелочисленный план;

не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.

Одним из методов отсечения является метод Гомори, который можно представить в виде следующих этапов:

1 этап: решение исходной задачи с ослабленными ограничениями симплекс-методом.

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

2 этап: формирование правильного отсечения.

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

, (6.22)

где S – множество индексов свободных переменных;

(6.23)

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

Z – множество целых чисел.

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

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

4 этап: решение скорректированной задачи.

Полученная расширенная задача решается симплекс-методом. Если найденный план удовлетворяет условию целочисленности, то задача целочисленного линейного программирования (6.1) решена. В противном случае повторяются этапы 2-4.

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

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

Пример 6.2. Решить следующую задачу целочисленного линейного программирования методом Гомори:

.

Решение:

Дата добавления: 2013-12-12