II. Решить ТРАНСПОРТНУЮ ЗАДАЧУ

Одесская государственная академия строительства и архитектуры

Кафедра процессов и аппаратов технологии строительных материалов

Расчетно графическая работа

По основам системного анализа

Выполнил(а) ст. гр. ПСК-357

Расчет проверил

Доцент каф. ПАТСМ

ОГАРКОВ Б.Л.

Одесса - 2012

I. Решение задачи линейного программирования

Задача ЛП в стандартной форме с т ограничениями и п пере­менными имеет следующий вид: максимизировать или минимизировать Z = c₁x₁ + с₂х₂+ -... + c_nx_n

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

Задачи ЛП в стандартной форме можно записать в компактных мат­ричных обозначениях следующим образом:

максимизировать или минимизировать Z = cx при ограничениях Ах = b, х>=0, b>=0,

где А — матрица размерности т Х п, х —вектор-столбец размер­ности их 1, b— вектор-столбец размерности т Х 1, с — вектор-строка размерности 1 Х п.

Обычно А называется матрицей коэффициентов, х — вектором переменных, b — вектором ресурсов, с — вектором оценок задачи ЛП.

Основные шаги вычислительного процесса симплекс-метода

Основными шагами процесса вычислений в соответствии с сим­плекс-методом в табличной форме применительно к задаче макси­мизации являются следующие:

Шаг 1. Записать задачу в стандартной форме.

Ш а г 2. Заполнить первоначальную таблицу с использованием начального допустимого базисного решения. (Процедура отыскания такого решения описываются ниже.)

Шаг 3. Вычислить вектор относительных оценок (строки с) при помощи правила скалярного произведения.

Ш а г 4. Если все оценки c _j неположительные, текущее допу­стимое базисное решение оптимальное. В противном случае не­обходимо ввести в базис небазисную переменную с наибольшим значением c _j.

Шаг 5. Определить при помощи правила минимального от­ношения переменную, выводимую из базиса.

Ш а г 6. Применить элементарное преобразование для получе­ния нового допустимого базисного решения и новой таблицы.

Шаг 7. Вычислить новые относительные оценки с использо­ванием элементарного преобразования или правила скалярного произведения. Перейти к шагу 4.

Итерацией симплекс-метода называется выполнение шагов 4—7 описанного процесса. На каждой итерации получаются новая таб­лица и улучшенное допустимое базисное решение. Число допусти­мых базисных решений, просматриваемых при использовании сим­плекс-метода, представляет собой важную характеристику эффек­тивности этого метода.

 

Условия задачи

Fmax=7x1-1x2

1x1+1x2>=3

5x1+1x2>=5

1x1+5x2>=5

1x1<=4

1x2<=4

 

II. Решить ТРАНСПОРТНУЮ ЗАДАЧУ

Транспортная задача (ТЗ) формулируется следующим образом. В m пунктах отправления А ₁... A _m сосредоточен однородный груз в количествах соответственно а ₁... а _m единиц. Имеющийся груз необходимо доставить потребителям В ₁... В _n, спрос которых выражается величинами b ₁... b _п единиц. Известна стоимость с _ij перевозки единицы груза из i -го пункта отправления в j -й пункт назначения. Требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.

Для наглядности условия ТЗ можно представить таблицей (табл. 1.), которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ.

Цель ТЗ — минимизировать общие затраты на реализацию плана перевозок.

Итерационный процесс по отысканию оптимального плана транспортной задачи начинают с опорного плана, который находят методом северо-западного угла.

Решение задачи осуществить методом потенциалов с помощью программы Optimal.

 

Представление транспортной задачи в матричной форме

Поставщик	Потребитель	Запас груза а i
B 1	B 2	...	B n
Затраты на перевозку 1ед. груза
A 1	C 11 X 11	С 12 X 12	...	C in X in	а 1
A 2	C 21 X 21	С 22 X 22	...	С 2п Х 2п	a 2
...	...	...	...	...	...
A m	С m1 X m1	C m2 X m2	...	C mn Х тп	a m
Потребность в грузе b j	b 1	b 2	...	b п

 

 

Исходная таблица:

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1
A2
A3
A4
Потребность

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.
Находим опорный план по правилу северо-западного угла:
Введем некоторые обозначения:
A_i^* - излишек нераспределенного груза от поставщика A_i
B_j^* - недостача в поставке груза потребителю B_j

Помещаем в клетку (1,1) меньшее из чисел A₁^*=130 и B₁^*=110
Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается
Помещаем в клетку (1,2) меньшее из чисел A₁^*=20 и B₂^*=50
Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается
Помещаем в клетку (2,2) меньшее из чисел A₂^*=90 и B₂^*=30
Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается
Помещаем в клетку (2,3) меньшее из чисел A₂^*=60 и B₃^*=30
Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается
Помещаем в клетку (2,4) меньшее из чисел A₂^*=30 и B₄^*=80
Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается
Помещаем в клетку (3,4) меньшее из чисел A₃^*=100 и B₄^*=50
Так как спрос потребителя B₄ удовлетворен, то столбец 4 в дальнейшем в расчет не принимается
Помещаем в клетку (3,5) меньшее из чисел A₃^*=50 и B₅^*=100
Так как запасы поставщика A₃ исчерпаны, то строка 3 в дальнейшем в расчет не принимается
Помещаем в клетку (4,5) меньшее из чисел A₄^*=140 и B₅^*=50
Так как спрос потребителя B₅ удовлетворен, то столбец 5 в дальнейшем в расчет не принимается
Помещаем в клетку (4,6) меньшее из чисел A₄^*=90 и B₆^*=90

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1
A2
A3
A4
Потребность

Целевая функция F=1400

Решаем задачу методом потенциалов:
Примем некоторые обозначения:
i - индекс строки;
j - индекс столбца;
m - количество поставщиков;
n - количество потребителей.

Этап 1

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_1,1-U₁= 2
V₂=C_1,2-U₁= 3
U₂=C_2,2-V₂= -2
V₃=C_2,3-U₂= 4
V₄=C_2,4-U₂= 5
U₃=C_3,4-V₄= -4
V₅=C_3,5-U₃= 8
U₄=C_4,5-V₅= -5
V₆=C_4,6-U₄= 11

Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:
S_1,3 = c_1,3 - (u₁ + v₃) = 2.
S_1,4 = c_1,4 - (u₁ + v₄) = 3.
S_1,5 = c_1,5 - (u₁ + v₅) = -6.
S_1,6 = c_1,6 - (u₁ + v₆) = -1.
S_2,1 = c_2,1 - (u₂ + v₁) = 8.
S_2,5 = c_2,5 - (u₂ + v₅) = -1.
S_2,6 = c_2,6 - (u₂ + v₆) = -3.
S_3,1 = c_3,1 - (u₃ + v₁) = 9.
S_3,2 = c_3,2 - (u₃ + v₂) = 5.
S_3,3 = c_3,3 - (u₃ + v₃) = 4.
S_3,6 = c_3,6 - (u₃ + v₆) = 1.
S_4,1 = c_4,1 - (u₄ + v₁) = 5.
S_4,2 = c_4,2 - (u₄ + v₂) = 10.
S_4,3 = c_4,3 - (u₄ + v₃) = 6.
S_4,4 = c_4,4 - (u₄ + v₄) = 1.

Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,5). Для нее оценка равна -6.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1		-			+
A2		+		-
A3				+	-
A4
Потребность

Перемещаем по циклу груз величиной в 20 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1
A2
A3
A4
Потребность

Целевая функция F= 1280

Значение целевой функции изменилось на 120 единиц по сравнению с предыдущим этапом.

Этап 2

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_1,1-U₁= 2
V₅=C_1,5-U₁= 2
U₃=C_3,5-V₅= 2
U₄=C_4,5-V₅= 1
V₆=C_4,6-U₄= 5
V₄=C_3,4-U₃= -1
U₂=C_2,4-V₄= 4
V₂=C_2,2-U₂= -3
V₃=C_2,3-U₂= -2

Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:
S_1,2 = c_1,2 - (u₁ + v₂) = 6.
S_1,3 = c_1,3 - (u₁ + v₃) = 8.
S_1,4 = c_1,4 - (u₁ + v₄) = 9.
S_1,6 = c_1,6 - (u₁ + v₆) = 5.
S_2,1 = c_2,1 - (u₂ + v₁) = 2.
S_2,5 = c_2,5 - (u₂ + v₅) = -1.
S_2,6 = c_2,6 - (u₂ + v₆) = -3.
S_3,1 = c_3,1 - (u₃ + v₁) = 3.
S_3,2 = c_3,2 - (u₃ + v₂) = 5.
S_3,3 = c_3,3 - (u₃ + v₃) = 4.
S_3,6 = c_3,6 - (u₃ + v₆) = 1.
S_4,1 = c_4,1 - (u₄ + v₁) = -1.
S_4,2 = c_4,2 - (u₄ + v₂) = 10.
S_4,3 = c_4,3 - (u₄ + v₃) = 6.
S_4,4 = c_4,4 - (u₄ + v₄) = 1.

Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,6). Для нее оценка равна -3.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1
A2				-		+
A3				+	-
A4					+	-
Потребность

Перемещаем по циклу груз величиной в 10 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1
A2
A3
A4
Потребность

Целевая функция F= 1250

Значение целевой функции изменилось на 30 единиц по сравнению с предыдущим этапом.

Этап 3

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_1,1-U₁= 2
V₅=C_1,5-U₁= 2
U₃=C_3,5-V₅= 2
U₄=C_4,5-V₅= 1
V₆=C_4,6-U₄= 5
U₂=C_2,6-V₆= 1
V₄=C_3,4-U₃= -1
V₂=C_2,2-U₂= 0
V₃=C_2,3-U₂= 1

Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:
S_1,2 = c_1,2 - (u₁ + v₂) = 3.
S_1,3 = c_1,3 - (u₁ + v₃) = 5.
S_1,4 = c_1,4 - (u₁ + v₄) = 9.
S_1,6 = c_1,6 - (u₁ + v₆) = 5.
S_2,1 = c_2,1 - (u₂ + v₁) = 5.
S_2,4 = c_2,4 - (u₂ + v₄) = 3.
S_2,5 = c_2,5 - (u₂ + v₅) = 2.
S_3,1 = c_3,1 - (u₃ + v₁) = 3.
S_3,2 = c_3,2 - (u₃ + v₂) = 2.
S_3,3 = c_3,3 - (u₃ + v₃) = 1.
S_3,6 = c_3,6 - (u₃ + v₆) = 1.
S_4,1 = c_4,1 - (u₄ + v₁) = -1.
S_4,2 = c_4,2 - (u₄ + v₂) = 7.
S_4,3 = c_4,3 - (u₄ + v₃) = 3.
S_4,4 = c_4,4 - (u₄ + v₄) = 1.

Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (4,1). Для нее оценка равна -1.
Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1	-				+
A2
A3
A4	+				-
Потребность

Перемещаем по циклу груз величиной в 60 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1
A2
A3
A4
Потребность

Целевая функция F= 1190

Значение целевой функции изменилось на 60 единиц по сравнению с предыдущим этапом.

Этап 4

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки.
Потенциалы U_i:
U₁=0
V₁=C_1,1-U₁= 2
V₅=C_1,5-U₁= 2
U₃=C_3,5-V₅= 2
U₄=C_4,1-V₁= 0
V₆=C_4,6-U₄= 6
U₂=C_2,6-V₆= 0
V₄=C_3,4-U₃= -1
V₂=C_2,2-U₂= 1
V₃=C_2,3-U₂= 2

Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:
S_1,2 = c_1,2 - (u₁ + v₂) = 2.
S_1,3 = c_1,3 - (u₁ + v₃) = 4.
S_1,4 = c_1,4 - (u₁ + v₄) = 9.
S_1,6 = c_1,6 - (u₁ + v₆) = 4.
S_2,1 = c_2,1 - (u₂ + v₁) = 6.
S_2,4 = c_2,4 - (u₂ + v₄) = 4.
S_2,5 = c_2,5 - (u₂ + v₅) = 3.
S_3,1 = c_3,1 - (u₃ + v₁) = 3.
S_3,2 = c_3,2 - (u₃ + v₂) = 1.
S_3,3 = c_3,3 - (u₃ + v₃) = 0.
S_3,6 = c_3,6 - (u₃ + v₆) = 0.
S_4,2 = c_4,2 - (u₄ + v₂) = 7.
S_4,3 = c_4,3 - (u₄ + v₃) = 3.
S_4,4 = c_4,4 - (u₄ + v₄) = 2.
S_4,5 = c_4,5 - (u₄ + v₅) = 1.

Так как все оценки S_i,j >=0, то полученный план является оптимальным.
Транспортная задача решена.

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4	B5	B6
A1
A2
A3
A4
Потребность

Целевая функция F= 1190