Особые случаи постановки и решения распределительных задач

Выше мы рассмотрели простейший вариант транспортной за­дачи. Реальные ситуации, как правило, сложнее — часто имеются некоторые особенности, которые не позволяют сразу перейти к формализованной записи задачи в виде (15.1)—(15.5). Все конк­ретные пояснения будут даны на примере следующей задачи.

Задача 15.6. Распределить посевы кормовых культур по 4 учас­ткам земли различного плодородия таким образом, чтобы сбор кормов (в кормовых единицах) был максимальным. Исходные данные приведены в таблице 95.

95. Исходные данные к задаче 15.6

Урожайности культур по участкам,

5850^\

Задачу необходимо решить с дополнительными ограничения­ми:

1) не менее половины площади посева однолетних трав долж­но быть размещено на 3-м участке;

2) посевы вико-овсяной смеси на 4-м участке должны состав-и ять точно 300 га;

3) весь картофель следует разместить на 4-м участке;

4) посевы кукурузы на 2-м участке должны занимать не более 100 га.

Введение дополнительных ограничений связано с тем, что в процессе практического применения распределительного метода

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

Несбалансированные задачи.

Условие сбалансированности (15.4) транспортных задач явля­ется очень важным с точки зрения применимости рассмотрен­ных выше быстродействующих алгоритмов их решения. В дей­ствительности исходные данные задачи могут быть и несбалан­сированными. Например, в задаче 15.6 сумма площадей всех уча­стков составляет 5850 га, а. сумма площадей посева всех культур — 4300 га, то есть модель распределительной задачи яв­ляется открытой:

Т п

14< 1^Вг (15.14)

/' = 1 У'=1

Для приведения задачи к закрытому (сбалансированному) виду в случае выполнения неравенства типа (15.14) вводится фиктивный, в данном случае 7-й, поставщик ресурсов, причем его мощность полагают равной разности

П т

Лфикт=Л7=Х5/ -Х4- (15.15)

Если же

П т

Х-В/< Х4> (15.16)

у'=1 /> 1

вводят фиктивного потребителя ресурса с объемом потребления

Т п

⁵фикт = X 4 - X В_]. (15.17)

/ = 1 у = 1 |

Для того чтобы значение целевой функции не изменилось, ^{^} стоимость транспортировки ресурса от фиктивного поставщика ко всем потребителям (в случае выполнения неравенства 15.14), а также стоимость транспортировки ресурса от всех поставщиков к фиктивному потребителю (в случае выполнения неравенства 15.16) необходимо приравнять к нулю. Отметим, что поскольку вся фиктивная строка (или фиктивный столбец) заполнена нуле- (выми стоимостями транспортировки ресурса, то даже в задачах; на минимизацию целевой функции алгоритм поиска оптималь- ] ного решения автоматически обеспечит наилучшее распределс- \

I 324

ние ресурса по значимым клеткам транспортной таблицы; ника­кая специальная корректировка алгоритма не требуется.

При постановке задачи 15.6 необходимо ввести 7-ю (фиктив­ную) культуру, положив ее урожайность на всех участках равной нулю: С₇₁ =...С₇₄ = 0. С учетом изложенных правил сбалансиро­ванная исходная транспортная таблица для задачи 15.6 без учета дополнительных условий примет вид, показанный в таблице 96.

Сбалансированная исходная транспортная таблица задачи 15.6

}

А:

40 21 13 30 18 19 0 1050

47 26 12 40 24 22 0 1000

550 1300 900 150 600 800 1550

Вопрос интерпретации полученных результатов с учетом включения в исходную матрицу фиктивных объектов рассматри­вается ниже.