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

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в т пунктах производства (хранения) в количествах a1, а2,…, аm единиц, необходимо распределить между п пунктами потребления, которым необходимо соответственно b1, b2,…, bn единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна Cij, и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Обозначим через xij количество груза, планируемого к перевозке от i-ro поставщика j-му потребителю. При наличии баланса производства и потребления
(32)
математическая модель транспортной задачи будет выглядеть так:найти план перевозок
Х = (xij), i = j =
минимизирующий общую стоимость всех перевозок
(33)
при условии, что из любого пункта производства вывозится весь продукт
, i= (34)
а любому потребителю доставляется необходимое количество груза
, j= (35)
причем по смыслу задачи
xi1>0,…., xmn>0. (36)
Для решения транспортной задачи чаще всего применяется метод потенциалов. Пусть исходные данные задачи имеют вид
A(a1. a2, а3) = (54; 60; 63); B(b1, b2, b3 ) =(41; 50; 44; 30); С=
Общий объем производства = 55+60+63 = 178 больше, требуется всем потребителям =42+50+44+30=166, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 178-166 = 12 единиц. Причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.
Первое базисное допустимое решение легко построить по правилу «северозападного угла». Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (34), (35), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является
ПотреблениеПроизводство
b1 =41
b2 =50
b3 =44
b4 =30
b5 =12
а1 =54
41
1
13
4
3
2
0
p1=0
a2 =60
3
37
6
23
2
5
0
p2=
аз =63
2
5
21
6
30
7
12
0
p3 =
q1=
q2=
q3=
q4=
q5=
базисной. Так как в системе (34), (35) ровно m + n – 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n – 1 занятых клеток.Обозначим через
μ (p1,,p2,…., pm ,q1,q2,…qn)
вектор симплексных множителей или потенциалов. Тогда
Δij = μAij – cij i=; j=
откуда следует
Δij = pi + qj – cij i=; j= (37)
Один из потенциалов можно выбрать произвольно, так как в системе (34), (35) одно уравнение линейно зависит от остальных. Положим, что pi = 0. Остальные потенциалы находим из условия, что для базисных клеток Δij = 0.В данном случае получаем
Δ11=0, p1+q1-c11=0, 0+q1- l=0, q1=l
Δ12=0, p1+q2-c12=0, 0+q2- 4=0, q2=4
Δ22=0, p2+q2-c22=0, p2+4- 6=0, p2=2
и т.д., получим: q3 = 0, р3=6, q4= I, q5= -6.
Затем по формуле (37) вычисляем оценки всех свободных клеток:
Δ21= p2+q5-c21=2+l-3=0
Δ31= p3+q1-c31=6+l-2=5
Δ 32=5; Δ 13=-3; Δ 14 =-1; Δ 24=-2; Δ15=-6; Δ25=-4.
Находим наибольшую положительную оценку
mах(Δij >0) =5 =Δ 31
Для найденной свободной клетки 31 строим цикл пересчета – замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные – в занятых клетках. Это будет 31-11-12-22-23-33. Производим перераспределение поставок вдоль цикла пересчета
41
13
41-p
13+p
20
34
37
23
37-p
23+p
16
44
21
p
21-p
21
Получаем второе базисное допустимое решение
bj
ai
b1 =41
b2 =50
b3 =44
b4 =30
b5 =12
а1 =54
20
1
34
4
3
*
2
0
p1=0
a2 =60
3
16
6
44
2
5
0
p2=2
аз =63
21
2
5
6
30
7
12
0
p3 =1
q1=1
q2=4
q3=0
q4=6
q5=-1
Находим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34 производим перераспределение
20
20-р
р
20
21
30
21+р
30-р
42
10
pvax =20и получаем третье базисное допустимое решение. Продолжаем процесс до тех пор пока не придем к таблице, для которой все
Δij≤ 0 i = j = .
Продолжая решение, получим
Х=
Для решения транспортной задачи по рассматриваемым исходным данным с помощью средства поиска решения MS Excel разместим в ячейках A1:D3 рабочего листа Excel стоимости перевозок, ячейки А7:D9 отведем под значения неизвестных (объемы перевозок). В ячейках F7:F9 необходимо ввести объемы производства, а в ячейках А11:D11 поместим объемы потребляемой продукции в пунктах назначения. В ячейку Е10 введем целевую функцию СУММПРОИЗВ(A1:D3;А7:D9), вычисляющую стоимость перевозок. Для решения этой задачи с помощью средства поиска решения отведем под неизвестные диапазон ячеек А7:Е11. В ячейках A10:D10 введем формулы в виде =СУММ(А7:А9)…=СУММ(D7:D9), определяющий объем продукции, ввозимый в пункты потребления. В ячейки E7:E9 введем формулы =СУММ(А7:D7)…=СУММ(А9:D9), вычисляющий объем произведенной продукции.
Затем выбираем команду Сервис, Поиск решения (Tools. Solver) и заполним открывающееся диалоговое окно Поиск решения (Solver) как показано на рис. 4.
Рис.4.
В диалоговом окне Параметры поиска решения (Solver Options) установим флажок Линейная модель (Assume Linear Model). После нажатия кнопки Выполнить (Solve) средство поиска решений находит оптимальный план поставок продукции и соответствующие ему расходы.

3.3.1.. Постановки задач
Постановка задачи А. Пусть на предприятии имеется n типов универсального оборудования и требуется изготовить n видов изделий. Известно время изготовления каждого изделия на всех видах оборудования. Требуется определить какое изделие, и на каком оборудовании необходимо изготовить, чтобы суммарное время изготовления всех изделий было минимально.

Оцените статью
Добавить комментарий