Определение опорного решения задачи методом минимального элемента

Формализация исходных данных задачи:

Введем следующие обозначения:

- количество севооборотов (пунктов отправления);

- количество ферм (пунктов назначения);

- номер севооборота:

- номер фермы:

, – индексы строк; , – индексы столбцов;

стоимость перевозки единицы объема продукции с –го севооборота на -ую ферму, руб/т;

объем перевозимой продукции с –го севооборота на –ую ферму, т;

- объем продукции, производимой на –ом севообороте и предназначенной для транспортировки на фермы, т;

-потребность –ой фермы в кормах, т;

Количество маршрутов равно mxn

- целевая функция (критерий оптимизации).

Исходная информация обычно заносится в матрицу специального вида (табл.2)

Таблица 2

Табличная форма записи

транспортной задачи

Пункты назначения   Пункты отправ- ления	Характеристика оценки	Объемы производства продукции
				n
	с11 х11	с12 х12	с13 х13	с1j х1j	с1n х1n
	с12 х21	с22 х22	с23 х23	с2j х2j	с2n х2n
	сi1 хi1	сi2 хi2	сi3 хi3	сij хij	сin хin
m	сm1 хm1	сm2 хm2	сm3 хm3	сmj хmj	сmn хmn
Максимальные объемы переработки продукции

Запись задачи транспортного типа в структурной форме:

Найти такие объемы () транспортировки кормов с севооборотных массивов на фермы, при которых целевая функция примет минимальное значение:

Ограничения по строкам:

Сумма перевозимых кормов с –го севооборотного массива на –у ферму должна быть равна запасу кормов данного севооборота:

.

Ограничения по столбцам:

Сумма объемов продукции, доставляемых на –ую ферму со всех севооборотных массивов, должна быть равна потребности в кормах на данной ферме:

.

Балансовое условие:

Сумма объемов продукции, производимой на всех севооборотных массивах, должна быть равна общей потребности ферм в кормах.

.

Условие не отрицательности переменных:

.

Матричная запись исходных данных задачи после учета требований сбалансированности представлена в табл.3.

Таблица 3

Табличное представление исходных данных задачи

Поиск по сайту: