Материал: 1436

Пример3.1.Построениеопорногопланаметодом«северо-западногоугла». Дана транспортная таблица (табл. 3.2). При построении опорного

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

Рассуждения ведут следующим образом. Пункт В1 подал заявку на 120 единиц груза. Удовлетворим эту заявку за счет запаса, имеющегося в

полностью. Пункту В2 требуетсяД160 единиц груза. Запишем в клетку №6 перевозку 130, т.к. запасы А2 150 исчерпаны.ИОставшиеся 30 единиц груза для пункта В2 удовлетворим из А3, записав перевозку 30 в клетку №10.

пункте А1 – 100 единиц груза, записав перевозку 100 в клетку №1. После

этого запасы в А1 исчерпаны, а заявка в пункте В1 осталась

неудовлетворенной. Удовлетворим ее, взяв из пункта А2 20 единиц груза,

и запишем эту перевозку в клетку №5. Теперь заявка В1 выполнена

Заявку В3 полностью перекроим из оставшихся запасов А3 и запишем в клетку №11 80 единиц груза. Заявку пункта В4 удовлетворим из А3, запасы которого будут полностью исчерпаны, а в клетку №12 запишем перевозку 90 единиц груза.

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

Клетки таблицы, в которых стоят перевозки, являются базисными, их число удовлетворяет условию r=m+n-1=6. Следовательно, опорный план построен верно.

24

После проверки правильности построения опорного плана считаются затраты на перевозку по формуле (3.8):

S1 2 100 3 20 4 130 9 30 12 80 15 90 3360..

Пример 3.2. Построение опорного плана методом нахождения

Начинаем распределять поставки с 1-йИстроки (пункт отправления А1,табл. (3.3). Минимальная стоимость перевозок единицы груза, равная 1, в клетке №2. В нее записывается максимальное количество груза – 100, которое есть в А1. Переходим к строке 2, пункт отправления А2, наименьшая стоимость – 3 в клетке №5. Заявка В1 – 120 удовлетворена полностью (запасы А2 – 150 позволяют). Следующая клетка в этой строке с минимальной стоимостью – клетка №6. В ней мы можем поставить перевозку 30, и запасы А2 на этом будут исчерпаны. Последняя, третья строка, имеет минимальную стоимость перевозки груза в клетке №10. Перекроем оставшиеся 30 единиц груза из запасов А3, заявка В2, таким образом, будет полностью удовлетворена. Оставшиеся заявки В3 и В4 в клетках №11 и 12 будут удовлетворены за счет запаса А3. Распределяя поставки подобными рассуждениями, получили опорный план. Число

25

базисных клеток соответствует условию правильности построения опорного плана (r=m+n-1=6).

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

3.4. Метод потенциалов

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

отлич Потенцстолбцуалы – это система чисел, присвоенных каждой строке и

свободным клеткам, а только к тем, где характеристика клеток таблицы отрицательная.

каждому транспортной таблицы. Потенциал такой-то строки или

такого-то столбца – это цифры у этой строки или этого столбца. Суть

Обозначим ui – потенциалы столбцов, а vj – потенциалы строк транспортной та лицы. Тогда сумма потенциалов в базисных клетках должна быть равна стоимости перевозок (условие 1), а для свободных

По условию (1) назначаются потенциалы, а по условию (2) проверяется оптимальность плана.

Пример 3.2. Пусть дана транспортная задача (табл. 3.4).

1.Составление опорного плана

Опорный план составлен методом нахождения минимального элемента по всей таблице.

2.Определение значений потенциалов

Начинаем расставлять значение потенциалов с базисных клеток. Для удобства назначим v1=0. Тогда для того чтобы в клетке №1 выполнялось равенство (1), значение u1 должно быть равно 2. Стоимость перевозки

26

27

3.5. Контрольные задачи

Задача 3.1. Построить опорный план методом нахождения минимального элемента по столбцам на примере задачи (см. табл. 3.2).

Контрольные вопросы

1. Что является «потенциалом»?

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

3. В каком месте ставится первый потенциал?

4. В чем состоит смысл метода потенциалов?

5. Что называется опорным планом перевозок? Чем он отличается от других допустимых планов?

28