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

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) Представим исходные данные в виде матрицы, в которой будем осуществлять решение задачи.

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

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

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

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

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

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

Z

= 3, 5 + 0, 5 +

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

1 +

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 единиц.