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=2x1+2x2

3x1-2x2>=-6

1x1+1x2>=3

1x1<=3

1x2<=5

 

 

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 п

 

 

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

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.

Находим опорный план по правилу северо-западного угла:

Введем некоторые обозначения:

Ai* - излишек нераспределенного груза от поставщика Ai

Bj* - недостача в поставке груза потребителю Bj

 

Помещаем в клетку (1,1) меньшее из чисел A1*=30 и B1*=35

Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимается

Помещаем в клетку (2,1) меньшее из чисел A2*=20 и B1*=5

Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимается

Помещаем в клетку (2,2) меньшее из чисел A2*=15 и B2*=20

Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимается

Помещаем в клетку (3,2) меньшее из чисел A3*=40 и B2*=5

Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимается

Помещаем в клетку (3,3) меньшее из чисел A3*=35 и B3*=55

Так как запасы поставщика A3 исчерпаны, то строка 3 в дальнейшем в расчет не принимается

Помещаем в клетку (4,3) меньшее из чисел A4*=50 и B3*=20

Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшем в расчет не принимается

Помещаем в клетку (4,4) меньшее из чисел A4*=30 и B4*=30

 

 

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

 

 

Решаем задачу методом потенциалов:

Примем некоторые обозначения:

i - индекс строки;

j - индекс столбца;

m - количество поставщиков;

n - количество потребителей.

 

Этап 1

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V1=C1,1-U1= 2

U2=C2,1-V1=3

V2=C2,2-U2= 3

U3=C3,2-V2=4

V3=C3,3-U3= 5

U4=C4,3-V3=-3

V4=C4,4-U4= 10

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,2 = c1,2 - (u1 + v2) = 1.

S1,3 = c1,3 - (u1 + v3) = -4.

S1,4 = c1,4 - (u1 + v4) = -7.

S2,3 = c2,3 - (u2 + v3) = -3.

S2,4 = c2,4 - (u2 + v4) = -9.

S3,1 = c3,1 - (u3 + v1) = -3.

S3,4 = c3,4 - (u3 + v4) = -9.

S4,1 = c4,1 - (u4 + v1) = 2.

S4,2 = c4,2 - (u4 + v2) = 2.

 

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

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

 

 

 

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

В результате перемещения по циклу получим новый план:

 

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

 

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

 

Этап 2

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V1=C1,1-U1= 2

U2=C2,1-V1=3

V4=C2,4-U2= 1

U4=C4,4-V4=6

V3=C4,3-U4= -4

U3=C3,3-V3=13

V2=C3,2-U3= -6

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,2 = c1,2 - (u1 + v2) = 10.

S1,3 = c1,3 - (u1 + v3) = 5.

S1,4 = c1,4 - (u1 + v4) = 2.

S2,2 = c2,2 - (u2 + v2) = 9.

S2,3 = c2,3 - (u2 + v3) = 6.

S3,1 = c3,1 - (u3 + v1) = -12.

S3,4 = c3,4 - (u3 + v4) = -9.

S4,1 = c4,1 - (u4 + v1) = -7.

S4,2 = c4,2 - (u4 + v2) = 2.

 

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

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

 

 

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

В результате перемещения по циклу получим новый план:

 

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

 

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

 

Этап 3

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V1=C1,1-U1= 2

U3=C3,1-V1=1

V2=C3,2-U3= 6

V3=C3,3-U3= 8

U4=C4,3-V3=-6

V4=C4,4-U4= 13

U2=C2,4-V4=-9

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,2 = c1,2 - (u1 + v2) = -2.

S1,3 = c1,3 - (u1 + v3) = -7.

S1,4 = c1,4 - (u1 + v4) = -10.

S2,1 = c2,1 - (u2 + v1) = 12.

S2,2 = c2,2 - (u2 + v2) = 9.

S2,3 = c2,3 - (u2 + v3) = 6.

S3,4 = c3,4 - (u3 + v4) = -9.

S4,1 = c4,1 - (u4 + v1) = 5.

S4,2 = c4,2 - (u4 + v2) = 2.

 

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

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

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

В результате перемещения по циклу получим новый план:

 

 

 

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

 

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

 

Этап 4

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V1=C1,1-U1= 2

V4=C1,4-U1= 3

U2=C2,4-V4=1

U3=C3,1-V1=1

V2=C3,2-U3= 6

V3=C3,3-U3= 8

U4=C4,3-V3=-6

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,2 = c1,2 - (u1 + v2) = -2.

S1,3 = c1,3 - (u1 + v3) = -7.

S2,1 = c2,1 - (u2 + v1) = 2.

S2,2 = c2,2 - (u2 + v2) = -1.

S2,3 = c2,3 - (u2 + v3) = -4.

S3,4 = c3,4 - (u3 + v4) = 1.

S4,1 = c4,1 - (u4 + v1) = 5.

S4,2 = c4,2 - (u4 + v2) = 2.

S4,4 = c4,4 - (u4 + v4) = 10.

 

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

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

 

 

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

В результате перемещения по циклу получим новый план:

 

 

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

 

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

 

Этап 5

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V1=C1,1-U1= 2

V3=C1,3-U1= 1

V4=C1,4-U1= 3

U2=C2,4-V4=1

U3=C3,1-V1=1

V2=C3,2-U3= 6

U4=C4,3-V3=1

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,2 = c1,2 - (u1 + v2) = -2.

S2,1 = c2,1 - (u2 + v1) = 2.

S2,2 = c2,2 - (u2 + v2) = -1.

S2,3 = c2,3 - (u2 + v3) = 3.

S3,3 = c3,3 - (u3 + v3) = 7.

S3,4 = c3,4 - (u3 + v4) = 1.

S4,1 = c4,1 - (u4 + v1) = -2.

S4,2 = c4,2 - (u4 + v2) = -5.

S4,4 = c4,4 - (u4 + v4) = 3.

 

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

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

 

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

В результате перемещения по циклу получим новый план:

 

 

 

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

 

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

 

Этап 6

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V3=C1,3-U1= 1

V4=C1,4-U1= 3

U2=C2,4-V4=1

U4=C4,3-V3=1

V2=C4,2-U4= 1

U3=C3,2-V2=6

V1=C3,1-U3= -3

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,1 = c1,1 - (u1 + v1) = 5.

S1,2 = c1,2 - (u1 + v2) = 3.

S2,1 = c2,1 - (u2 + v1) = 7.

S2,2 = c2,2 - (u2 + v2) = 4.

S2,3 = c2,3 - (u2 + v3) = 3.

S3,3 = c3,3 - (u3 + v3) = 2.

S3,4 = c3,4 - (u3 + v4) = -4.

S4,1 = c4,1 - (u4 + v1) = 3.

S4,4 = c4,4 - (u4 + v4) = 3.

 

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

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

 

 

 

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

В результате перемещения по циклу получим новый план:

 

 

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

 

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

 

Этап 7

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V3=C1,3-U1= 1

V4=C1,4-U1= 3

U2=C2,4-V4=1

U3=C3,4-V4=2

U4=C4,3-V3=1

V1=C3,1-U3= 1

V2=C4,2-U4= 1

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,1 = c1,1 - (u1 + v1) = 1.

S1,2 = c1,2 - (u1 + v2) = 3.

S2,1 = c2,1 - (u2 + v1) = 3.

S2,2 = c2,2 - (u2 + v2) = 4.

S2,3 = c2,3 - (u2 + v3) = 3.

S3,2 = c3,2 - (u3 + v2) = 4.

S3,3 = c3,3 - (u3 + v3) = 6.

S4,1 = c4,1 - (u4 + v1) = -1.

S4,4 = c4,4 - (u4 + v4) = 3.

 

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

Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

 

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

В результате перемещения по циклу получим новый план:

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

 

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

 

Этап 8

 

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui:

U1=0

V3=C1,3-U1= 1

U4=C4,3-V3=1

V1=C4,1-U4= 0

V2=C4,2-U4= 1

U3=C3,1-V1=3

V4=C3,4-U3= 2

U2=C2,4-V4=2

 

Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:

S1,1 = c1,1 - (u1 + v1) = 2.

S1,2 = c1,2 - (u1 + v2) = 3.

S1,4 = c1,4 - (u1 + v4) = 1.

S2,1 = c2,1 - (u2 + v1) = 3.

S2,2 = c2,2 - (u2 + v2) = 3.

S2,3 = c2,3 - (u2 + v3) = 2.

S3,2 = c3,2 - (u3 + v2) = 3.

S3,3 = c3,3 - (u3 + v3) = 5.

S4,4 = c4,4 - (u4 + v4) = 4.

 

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

Транспортная задача решена.

 

 

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