Как линейная оптимизационная модель

Вариант – 1

Выполнили:

Студенты группы ДПМ-81 Барсуков Р. В.

Глебова О. В.

Логинов С.

 

Проверил: Попович В. С.

 

Барнаул

1 Исходные данные

Транспортная модель соответствует типовой задаче строительной индустрии: товарный продукт от m бетоносмесительных заводов определенной производительности нужно перевозить к n строительным объектам; для каждого объекта требуется определенное количество продукта; расстояние между заводами и объектами известно; необходимо определить, сколько бетона с каждого завода и на какой объект надо перевезти, чтобы грузоперевозки (тонно-километры и т. п.) были минимальными.

Вводятся обозначения: i — заводы ; j — строящиеся объекты ; a_i — количество продукта, производимое i -м заводом, т; b_j — потребность в продукте j -ro объекта, т; р_ij — расстояние от i -ro завода до j -ro объекта строительства, км; Х_ij — количество бетона, перевозимое с i -ro завода на j -и объект, т.

Задача, транспортного типа, оптимизации плана перевозок, формулируется как минимизация грузооборота.

 

Таблица 1 – Расстояния между заводами и потребителями бетона

Номер бетоносмесительного завода	Объекты строительства

 

Мощность бетоносмесительных заводов: 50, 15, 100 (м³). Потребности строительных объектов: 65, 45, 30, 25 (м³/ч).

Поскольку суммарный объем производства товарного бетона (50 + 15 + 100) м /ч больше суммарного спроса (65 + 45 + 30 + 25) м³/ч, данная задача является замкнутой. Целевая функция:

(1)

при условиях:

или50+15+100 = 65 + 45+30 + 25; (2)

(3)

Модель задачи содержит избыточное ограничение (2): если любые m+n–1 ограничений задачи удовлетворяются, то автоматически удовлетворяется и оставшееся ограничение. Таким образом, любое из уравнений спроса и поставок можно опустить. Сле­довательно, транспортная модель содержит m + n–1 независимых ограничений, вследствие чего в любое допустимое базисное решение входит также m +n – 1 базисных переменных.

Исходную модель и процесс численного решения транспортной задачи можно представить в компактном виде при помощи транспортной таблицы (таблицы 2). Она имеет вид матрицы, i -я строка которой соответствует i -му пункту производства, а j -й столбец — j -му пункту спроса; ij -й элемент матрицы представляется прямоугольным «окошком», которое называется ячейкой таблицы.

Расстояния между заводами и объектами р_ij даются в правом верхнем углу ij -ячейки. Левый верхний угол заполняется оценками оптимальности d_ij, смысл и назначение которых поясняются ниже. Наконец, в большом треугольнике в центре ячейки находится значение искомого объема перевозок — переменной Х_ij (если оно нулевое, то его можно опустить).

 

Таблица 2 - Общий вид транспортной таблицы

 

 

Заводы	Объекты строительства	Объем производства, м3/ч
	d11 p11 x11	d12 p12 x12	d13 p13 x13	d14 p14 x14	c1
	d21 p21 x21	d22 p22 x22	d23 p23 x23	d24 p24 x24	c2
	d31 p31 x31	d32 p32 x32	d33 p33 x33	d34 p34 x34	c3
Спрос	b1	b2	b3	b4	-

Численное решение задачи, или определение оптимального плана перевозок, согласно сформулированному выше критерию оптимальности можно производить симплекс-методом.Однако такие особенности транспортной модели, как избыточность ограничений и равенство единице всех коэффициентов в уравнениях-ограничениях (3), позволяют упростить процедуры поиска включаемой в базис и выводимой из него переменных. При этом вместо проверки условия оптимальности по симплекс-критерию I (минимизация целевой функции) используется определение потенциалов, а построение замкнутого цикла заменяет процедуру применения симплекс-критерия II (условия допустимости). Для этого варианта симплекс-метода иногда используется название «метод потенциалов».