книги / Математические основы теории систем. Методы оптимизации

Потребность ј-го потребителя в продукции aj (j = 1...n). Содержимое i-го склада bi (i = 1...m).

Стоимость перевозки единицы продукции с i –го склада к j-му потребителю рij.

Составить такой план перевозок, при котором суммарная стоимость перевозок минимальна.

2.8.2. Математическое описание задачи

Обозначение:

xij – количество продукции, поставляемой с i-го склада к j-му потребителю.

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

Специфика транспортной задачи: единичные коэффициенты при переменных.

Транспортная задача называется сбалансированной, если сумма потребностей потребителей равна сумме содержимого складов:

Если равенство не выполняется, то задача считается несбалансированной и сводится к сбалансированной путем введения фиктивных потребителей с P ij = 0.

51

2.8.3. Транспортная таблица

Это таблица, в которую заносится допустимый план перевозок (план, удовлетворяющий ограничениям). Элемент Xij транспортной таблицы – количество продукции, завезенной с i-го склада к j-му потребителю. Таблица имеет следующий вид:

Сумма элементов i-й строки равна bi, сумма элементов j-го столбца равна aj.

2.8.4. Таблица издержек

Это таблица, содержимое которой – pij – стоимость перевозки единицы продукции с i-го склада к j-му потребителю. Имеет вид:

2.8.5. Метод «северо-западного» угла

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

Дано: незаполненная транспортная таблица.

Определить: допустимый план перевозок, т.е. заполнить транспортную таблицу.

52

Алгоритм:

Сравниваются а1 иb1. Меньшеезначение записывается вклетку x11. Находится разность a1– x11, b1–x11. Полученные значения записы-

ваются соответственно над a1 и b1.

Строка (столбец), в которой окажется 0, вычеркивается. Переход к заполнению следующей клетки транспортной табли-

цы. Повторение пп. 1– 3.

Окончание процесса, когда над всеми коэффициентами ai и bj окажутся 0.

В результате должны оказаться заполненными (m + n – 1) клеток.

Пример

a1 = 10, a2 = 20, a3 = 30, a4 = 45;

b1 = 25, b2 = 45, b3 = 35.

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

25

45

35

Решение:

1.Сравниваются a1 и b1: 10 < 25, значит, x11=10.

2.a1 – x11 = 10 – 10 = 0, b1– x11 = 25 – 10 = 15. 0 записывается над a1, т.е. над 10, 15 – над b1, т.е. над 25.

3.Оставшиеся клетки в столбце с a1 = 10 вычеркиваются.

4.Переход к заполнению следующей клетки таблицы, т.е. к x12. Сравниваются a2 и b1 – x11 (то, что осталось от b1), т.е. 15 и 20. Выбирается меньшее, т.е. 15. В этом случае x11 = 15. В соответствующую клетку таблицы заносится 15.

5.Процесс заканчивается, когда рядом со всеми коэффициента-

ми ai и bi будут стоять нули.

Заполненная транспортная таблица с начальным допустимым планом перевозок имеет вид:

53

2.8.6.Алгоритм решения транспортной задачи

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

2.Полученный план проверяется на оптимальность.

2.1.В таблицу задачи переносятся соответствующие значения из транспортной таблицы.

2.2.Находится ui и vj из равенства ui + vj = pij. Полученные значения заносятся в соответствующую строку и столбец.

2.3.Заполняются пустые клетки таблицы задачи. В них заносятся значения qij:

qij = pij – ui – vj.

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

3.Улучшение полученного плана.

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

3.2.В заполненных клетках транспортной таблицы ставятся знаки «+» и «–» таким образом, что во всех строках и столбцах количество плюсов равно количеству минусов.

54

3.3.Анализируется содержимое клеток, помеченных знаком «–». Из анализируемых значений выбирается минимальное. Пусть минимальное значение F.

3.4.Содержимое помеченных клеток изменяется на величину F. Причем содержимое клеток с «–» уменьшается на F, а с «+» – увеличивается на F.

3.5.Переход к п. 2.

Пример 1

Дано: транспортная задача задана транспортной таблицей с начальным планом и таблицей издержек:

Транспортная таблица:

Решение:

1. Составляется таблица задачи. Для этого берется таблица такой же размерности, что и транспортная таблица. В этой таблице отмечаются занятые клетки транспортной таблицы. Затем в отмеченные клетки переносится содержимое соответствующихклетоктаблицыиздержек:

55

2. Находятся значения vi, ui из уравнений:

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

3. Пустые клетки таблицы заполняются по приведенной выше формуле. Например, содержимое клетки Q13 находится как разность содержимого соответствующей клетки таблицы издержек 4 и u3, v1:

Q13 = p13 – u3 – v1 = 4 –3 –2 = –1.

В итоге таблица задачи принимает вид:

4. Анализ полученной таблицы задачи. В таблице имеется отрицательный коэффициент, следовательно, план перевозок, представленный транспортной таблицей, не является оптимальным.

56

5. Улучшение полученного плана.

5.1. В таблице задачи находится клетка с максимальным по модулю отрицательным коэффициентом. Это Q33 = –6. В соответствующей клетке (синдексом «33») транспортной таблицыставится знак«+».

5.2. В соответствии с п. 3.2 алгоритма проставляются знаки «+» и «–» в заполненных клетках транспортной таблицы

5.3. Сравнивается содержимое клеток, помеченных знаком «–». Выбирается минимальное F = 30.

5.4. Содержимое помеченных клеток транспортной таблицы изменяется на величину F = 30.

Целевая функция для данного плана Q = 200. 6. Повторение предыдущих пунктов алгоритма. 6.1.

6.2.

57

6.3.

6.4.

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

Ответ:

Х11 = 10; Х12 =15; Х24 = 45; Х32 = 5; Х33 = 30;

Х13 = Х14 = Х21 = Х22= Х23 = Х31 = Х34 = 0.

Целевая функция Q = 180.

Пример 2

Имеется печатная плата с тремя разъемами: 48, 40, 56 выводов соответственно; 1, 2, 3, 4 – микросхемы, имеющие 18,13,14,17 выводов соответственно.

Определить оптимальное число связей каждой микросхемы с каждым разъемом. Критерий оптимизации – минимальная суммарная длина связей. Для получения сбалансированной задачи вводится 5-я микросхема с 14 выводами и pij = 0.

58

Рис. 2.5. Печатная плата

Решение 1. Составляем таблицу издержек:

где Pij – число связей i-го разъема с j-й микросхемой.

3. Составляется таблица задачи. Для этого берется таблица такой же размерности, что и транспортная таблица. В этой таблице отмечаются занятые клетки транспортной таблицы. Затем в отмеченные клетки переносится содержимое соответствующих клеток таблицы издержек:

Пустые клетки таблицы заполняются по формуле qij = pi – ui – vj.

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

5.Улучшение полученного плана.

5.1.В таблице задачи находится клетка с максимальным по мо-

дулю отрицательным коэффициентом. Это Q32 = –1. В соответствующей клетке (с индексом «32») транспортной таблицы ставится знак «+».

5.2.В соответствии с п.3.2. алгоритма проставляются знаки «+»

и«–» в заполненных клетках транспортной таблицы

5.3.Сравнивается содержимое клеток транспортной таблицы, помеченных знаком «–». Выбирается минимальное F = 18.

5.4.Содержимое помеченных клеток транспортной таблицы изменяется на величину F = 18.

6. Составляем таблицу задач:

60