Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

(5)

Для решения транспортной задачи чаще всего применяется метод потенциалов.
Пусть исходные данные задачи имеют вид
А(а1, а2, а3) = (54; 60; 63); В(b1, b2, b3, b4) = (41; 50; 44; 30);
С = [pic] [pic] [pic][pic][pic]
Общий объем производства (аi = 55+60+63 = 178 больше, требуется всем потребителям (bi = 42+50+44+30 = 166, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 178-166 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.
Первое базисное допустимое решение легко построить по правилу (северо- западного угла(.

| |b1 =41 |b2 |b3 =44|b4 |b5 | |
|Потребление | |=50 | |=30 |=12 | |
|Производство | | | | | | |
| а1 =54 | 41 |13 | | | |p1 =0 |
| a2 =60 | |37 |23 | | | p2 =|
| a3 =63 | * | |21 |30 |12 | p3 =|
| |q1 = |q2 = |q3 = |q4 = |q5 = | |

Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений
(3), (4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.
Обозначим через

([pic]) вектор симплексных множителей или потенциалов. Тогда

(ij = (Aij - сij i = 1,m; j = 1,n откуда следует

(ij = pi + qj - cij i = 1,m; j = 1,n

(6)
Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток [pic]. В данном случае получаем

(11 = 0, p1 + q1 - c11 = 0, 0+q1 -1 = 0, q1 = 1

(12 = 0, p1 + q2 - c12 = 0, 0+q2 -4 = 0, q2 = 4

(22 = 0, p2 + q2 - c22 = 0, р2 +4-6 = 0, р2 = 2

и т.д., получим: q3=0, p3=6, q4= 1, q5= -6.
Затем по формуле (6) вычисляем оценки всех свободных клеток:

(21 = p2 + q5 - c21 = 2+1-3 = 0

(31 = p3 + q1 - c31 = 6+1-2 = 5

(32 = 5; (13 = -3; (14 = -1; (24 = -2; (15 = -6; (25 = -4.
Находим наибольшую положительную оценку max ([pic]) = 5 = [pic]
Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-
22-23-33. Производим перераспределение поставок вдоль цикла пересчета

|41 |13 | | |41-( |13+( | | |20 |34 | |
| |37 |23 | | |37-( |23+( | | |16 |44 |
| | |21 | |( | |21-( | |21 | | |

[pic]= 21
Получаем второе базисное допустимое решение:

| |b1 =41 | b2 |b3 =44|b4 | | |
|bj | |=50 | |=30 |b5=12 | |
| ai | | | | | | |
| а1 =54 | 20 |34 | | * | |p1 =0 |
| a2 =60 | |16 |44 | | | |
| | | | | | |p2 =2 |
| a3 =63 | 21 | | |30 |12 | 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 |

(max = 20 и получаем третье базисное допустимое решение. Продолжаем процесс до те пор, пока не придем к таблице, для которой все

(ij ( 0 i = 1,m; j = 1,n

Читателю не составит труда проверить, что будет оптимальным базисное допустимое решение

[pic] [pic] [pic] [pic]

(8. Динамическое программирование.

Рекомендуем скачать другие рефераты по теме: гигиена реферат, информация реферат.





Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата