Контрольная работа: Линейная алгебра и математическое программирование

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

40.

Решение:

Вычислим y = = 350 + 400 + 250 = 1000,

к = = 175 + 225 + 240 + 160 + 200 = 1000, так как к = y , то решаемая транспортная задача является закрытой.

Обозначим через количество груза, перевозимого из пункта в пункт .

Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.

Математическая модель закрытой транспортной задачи имеет вид

при ограничениях ,

,

X ij ≥ 0 , i = j = , m = 5.

Оптимальным решением задачи является матрица Xopt = ( Xij )3x5, удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

Условия задачи и ее исходное решение будем записывать в распределительную таблицу. Клетки, в которые поместим грузы, называются занятыми, остальные клетки – незанятыми, или пустыми. В верхнем правом углу каждой клетки будем записывать тарифы. Существует несколько способов нахождения исходного решения.

Рассмотрим один из них – метод минимального тарифа (элемента). Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок Cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей.

Процесс распределения продолжается до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m + n -1 = 5 + 3 – 1 = .

В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

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

Найдем исходное решение по методу минимального тарифа. Для этого составим следующую распределительную таблицу:

bi ai		1	2	3	4	5
		175	225	240	160	200
1	350	5 175	15 175	18	16	8
2	400	6	« 1 2 3 4 5 6 7 8 9 10 » К-во Просмотров: 304 Бесплатно скачать Контрольная работа: Линейная алгебра и математическое программирование >>> Скачать <<< Меню Поиск