Быстрый поиск

Реферат: Прикладная математика

(3)

причем по смыслу задачи

t1 0, t3 0. (4)

Переписав неравенства (2) и (3) в виде:

(6)

(5)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. 1. Программа ²расшивки² имеет вид

t1=, t2=0, t3=

18

и прирост прибыли составит 519.

Сводка результатов приведена в таблице

Таблица 1

сj	36	14	25	50	b	x4+i	yi	ti
	4	3	4	5	208	0	6	46 5/12
aij	2	5	0	2	107	13	0	0
	3	1	2	5	181	0	4	60 1/3
xj	27	0	0	20	1972			519 2/3
Dj	0	8	7	0

§7. Транспортная задача линейного программирования

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах а1, а2,..., аm единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1, b2,..., bn единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна сij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

(1)

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

найти план перевозок

Х = (хij), i = 1,m; j = 1,n

минимизирующий общую стоимость всех перевозок

(2)

при условии, что из любого пункта производства вывозится весь продукт

(3)

и любому потребителю доставляется необходимое количество груза

(4)

причем по смыслу задачи

х11 > 0 ,. . . ., xmn > 0. (5)

19

Для решения транспортной задачи чаще всего применяется метод потенциалов. Пусть исходные данные задачи имеют вид

А(а1, а2, а3) = (54; 60; 63); В(b1, b2, b3, b4) = (41; 50; 44; 30); С =

Общий объем производства åаi = 55+60+63 = 178 больше, требуется всем потребителям åbi = 42+50+44+30 = 166, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 178-166 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².