II. Решить ТРАНСПОРТНУЮ ЗАДАЧУ
Одесская государственная академия строительства и архитектуры
Кафедра процессов и аппаратов технологии строительных материалов
Расчетно графическая работа
По основам системного анализа
Выполнил(а) ст. гр. ПСК-357
Расчет проверил
Доцент каф. ПАТСМ
ОГАРКОВ Б.Л.
Одесса - 2012
I. Решение задачи линейного программирования
Задача ЛП в стандартной форме с т ограничениями и п переменными имеет следующий вид: максимизировать или минимизировать Z = c1x1 + с2х2+-... + cnxn
при ограничениях
Задачи ЛП в стандартной форме можно записать в компактных матричных обозначениях следующим образом:
максимизировать или минимизировать Z = cx при ограничениях Ах = b, х>=0, b>=0,
где А — матрица размерности т Х п, х—вектор-столбец размерности их 1, b— вектор-столбец размерности т Х 1, с — вектор-строка размерности 1 Х п.
Обычно А называется матрицей коэффициентов, х — вектором переменных, b — вектором ресурсов, с — вектором оценок задачи ЛП.
Основные шаги вычислительного процесса симплекс-метода
Основными шагами процесса вычислений в соответствии с симплекс-методом в табличной форме применительно к задаче максимизации являются следующие:
Шаг 1. Записать задачу в стандартной форме.
Ш а г 2. Заполнить первоначальную таблицу с использованием начального допустимого базисного решения. (Процедура отыскания такого решения описываются ниже.)
Шаг 3. Вычислить вектор относительных оценок (строки с) при помощи правила скалярного произведения.
Ш а г 4. Если все оценки cj неположительные, текущее допустимое базисное решение оптимальное. В противном случае необходимо ввести в базис небазисную переменную с наибольшим значением cj.
Шаг 5. Определить при помощи правила минимального отношения переменную, выводимую из базиса.
Ш а г 6. Применить элементарное преобразование для получения нового допустимого базисного решения и новой таблицы.
Шаг 7. Вычислить новые относительные оценки с использованием элементарного преобразования или правила скалярного произведения. Перейти к шагу 4.
Итерацией симплекс-метода называется выполнение шагов 4—7 описанного процесса. На каждой итерации получаются новая таблица и улучшенное допустимое базисное решение. Число допустимых базисных решений, просматриваемых при использовании симплекс-метода, представляет собой важную характеристику эффективности этого метода.
Условия задачи
Fmax=2x1+2x2
3x1-2x2>=-6
1x1+1x2>=3
1x1<=3
1x2<=5
II. Решить ТРАНСПОРТНУЮ ЗАДАЧУ
Транспортная задача (ТЗ) формулируется следующим образом. В m пунктах отправления А 1 ... A m сосредоточен однородный груз в количествах соответственно а 1 ... а m единиц. Имеющийся груз необходимо доставить потребителям В 1 ... В n , спрос которых выражается величинами b 1 ... 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