Приближённые методы решения задач

Линейного программирования.

 

1. Метод простейших аппроксимаций (метод Фогеля)

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

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

      Рассмотрим алгоритм метода простейших аппроксимаций на примере расстановки кранов на причалах.

      Дано: m – количество типов кранов.

                  i = 1 ÷ m – индекс типа крана.

                  n – количество грузовых причалов.

                  j = 1 ÷ n – индекс причала.

                  ki – количество кранов каждого типа, имеющееся в порту.

                  Qj – навигационный грузооборот на каждом j – ом причале

                         (тыс. тонн)

                   Рij – производительность i- ого типа крана при работе на

                          j – ом причале, тысяч тонн за навигацию.

      Необходимо расставить перегрузочные механизмы (краны) так, чтобы выполнить заданный грузооборот на каждом причале min – ым количеством кранов.

      Искомая переменная.

      Kij – это количество кранов i – ого типа, работающих на j – ом причале.

Z = → min

Ограничения:

1) Kij ≥ 0

2) Q_j

3)

 

m = 5       k₁ = 4, k₂ = 7, k₃ = 2, k₄ = 3, k₅ = 10

n = 5

                 Q₁ = 600, Q₂ = 2890, Q₃ = 1100, Q₄ = 2500, Q₅ = 300

   i

P_ij =

     j

 

Алгоритм решения.

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

      Z = k₁₁ + k₁₂ + k₁₃ + k₁₄ + k₁₅ +

              k₂₁ + k₂₂ ……………… +

              k₃₁ + k₃₂………………. → min

1. 170k₁₁ + 180k₂₁ + 130k₃₁ + 200k₄₁ + 150k₅₁ = 600

2.  380*k₁₂ + 380*k₂₂ + 200*k₃₂ + ………. = 2890

3.                                                                        = 1100

4.                                                                        = 2500

5.                                                                        = 300

6. k₁₁ + k₁₂ + k₁₃ + k₁₄ + k₁₅ ≤ 4

7. k₂₁ + k₂₂ + k₂₃ + k₂₄ + k₂₅ ≤ 7

8.                                          ≤ 2

9.                                          ≤ 3

10.                                          ≤ 10

11. Kij ≥ 0

2) Представим исходные данные в виде матрицы, в которой будем осуществлять решение задачи.

 

 

j			1		2			3	4		5
i	Qj Кi		600		2890			1100	2500		300	Столбцы разности
1		4		170	3,5кр-1330 2)380		200			220	0,5кр-40 8)80	160 380-220 160		20	50	50	90
2		7		3,35кр 6)180	380		230			1,55кр-400 5)260	2,1кр-189 7)90	120	120	30	80 80		90
3		2		130	200		100			140	1кр 9)70	60	60	10	10	10	50
4		3		200	3кр-1560 1)520		280			300	120	220
5		10		150	470		3,25кр 3)340			6,75кр-2100 4)310	100	130	130	160 30
		Строки разности.		20	50	60				10	20
				10	90	110 110				50	10
				10						50	10
				10						50	10
				10						40	10
				10							10

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

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

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

4)        После постановки кранов на причал в таблице вычёркивается строка или столбец с заполненным квадратом. Строка вычёркивается, если расставлены все краны соответствующего типа; столбец – если выполнен заданный грузооборот.

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

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

Z

      = 3, 5 + 0, 5 +

              3, 35 + 1, 55 + 2, 1 +

              1 +

25

               3 +

               3, 25 + 6, 75 =

      Ограничения:

3, 35*180 = 600

3, 5*380 + 3*520 = 2890

3, 25*340 = 1100

1, 55*260 + 6, 75*310 = 2500

0, 5*80 + 2, 1*90 + 1*70 = 300

 

3, 5 + 0, 5 = 4

3, 35 + 1, 55 + 2, 1 = 7

1 < 2

3 = 3

3, 25 + 6, 75 = 10

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

      Сравнительный показатель трудоёмкости данного приближённого метода и любого точного метода составляет ≈ 50 единиц.