logo
Методичка по исследованию операций

Иллюстративный пример

Проиндексировав исходные данные, приведенные выше, получим (шаг 1):

Ai

||tij||

400

2(1)

1(0)

–

2(1)

1

100

3(2)

2(1)

–

1(0)

1

400

–

–

1(0)

2(1)

1

160

3(1/2)

–

2(1)

2(0)

2

Bj

240

330

200

560

Сделав загрузку таблицы ||хij|| в перспективные клетки (Iij = 0) и рассчитав баланс для каждого столбца (шаги 2 и 3), убеждаемся, что баланс в разных столбцах разного знака. Следовательно, необходима перезагрузка столбцов (шаг 4).

Выбираем варианты перегрузки из перегруженных столбцов с учетом замечания 1. Получаем таблицу:

400 · 1

–

1) |I12 – I11| = 1;

2) |I12 – I14| = 1;

3) |I33 – I34| = 1;

4) |I43 – I41| = 1/2;

5) |I43 – I44| =

–

100 · 1

–

–

400 · 1

–

160 · 1

0

400

720

100

+240

–70

–520

+460

Вычислив разности индексов для каждого варианта, находим вариант с нулевой разностью (правило 1). Используя этот вариант для перегрузки, по правилу 2 находим количество перегружаемых изделий типа Р4 и переводим их из третьего столбца в четвертый. Получаем новый план и снова переходим к шагу 3.

400 · 1

–

1) |I12 – I11| = 1;

2) |I12 – I14| = 1;

3) |I33 – I34| =

–

100 · 1

–

–

400 · 1

–

160 · 2

0

400

400

420

+240

–70

–200

+140

Получив баланс и выписав возможные варианты перезагрузок, обнаруживаем, что все разности индексов равны единице. Учитывая замечание 2, выбираем третий вариант. По правилу 2 находим Δх34 и производим перегрузку из третьего столбца в четвертый по третьей строке (шаги 3 и 4).

400 · 1

–

|I12 – I11| = 1

Другого варианта нет

(см. замечание 1).

–

100 · 1

–

–

330 · 1

70 · 2

–

160 · 2

0

400

330

560

+240

–70

–130

0

Проделав с этим планом уже известные операции, получим очередной новый план.

70 · 2

330 · 1

–

1) |I24 – I21| = 2;

2) |I44 – I41| =

(см. замечание 5).

–

100 · 1

–

–

300 · 1

70 · 2

–

160 · 1

140

330

330

560

+100

0

–130

0

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

70 · 1

330 · 1

–

|I33 – I34| = 1.

–

100 · 1

–

–

330 · 1

70 · 2

33 · 3

–

127 · 2

239

330

330

494

+1

0

–130

+66

70 · 2

330 · 1

–

–

100 · 1

–

–

297 · 1

103 · 2

33 · 3

–

127 · 2

239

330

297

560

~0

0

–97

0

Нулевой баланс в четвертом столбце восстановлен. В таблице больше нет столбцов с положительным балансом. Однако, прежде чем переходить к шагу 5, следует проверить в соответствии с замечанием 4, нет ли второго плана с таким же балансом. Для этого нужно отыскать вариант разгрузки третьего столбца с нулевой разностью индексов. Такого нет, так как для единственного варианта |I33 – I34| = 1 ≠ 0! Второго плана нет, а в полученном плане следует сделать коррекцию А3 (шаг 5):

х33 = 297 – 97 = 200.

70 · 2

330 · 1

–

–

100 · 1

–

–

200 · 1

103 · 2

33 · 3

–

127 · 2

239

330

200

560

~0

0

0

0

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

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4