Методические указания для студентов механико-математического факультета (стр. 4 )

5£y0,2£10

1£y1,2£4

4£y1,3£8

6£y2,3£8.

Сформулированная задача имеет слишком большую для ручного счета размерность (число ограничений m=16, число переменных n=8, а после приведения задачи к каноническому виду возрастет до n=29). Поэтому для решения задачи рекомендуем воспользоваться программой SIMPLEX, разработанной на кафедре исследования операций и предназначенной для решения задач линейного программирования. Описание программы SIMPLEX и пример ее использования смотрите в приложении 1. ·

До сих пор мы рассматривали оптимизационные модели, в которых ограничивающим фактором являлась продолжительность проекта T0. В тех случаях, когда таким фактором является стоимость выполнения проекта C0, можно сформулировать следующую оптимизационную задачу :

Tкр=tn-t0 ® min

ti, yij

ti - tj +yij£0 для всех (i, j)ÎS,

(8)

S (bij-aijyij) £ C0

(i, j)ÎS

Lij £ yij £ Uij для всех (i, j)ÎS.

Данная модель позволяет найти оптимальные значения продолжительностей работ yij, минимизирующие время выполнения проекта при заданных ограничениях на его стоимость, отношениях предшествования, верхних и нижних пределах изменения продолжительности каждой работы.

Утверждение 5. Пусть Сн – затраты на выполнение проекта при yij=Uij. Задача (8) разрешима тогда и только тогда, когда С 0³Cн. ·

Задача (8) эквивалентна задаче линейного программирования (9):

Tкр=tn-t0 ® min

ti, yij

ti +yij £tj для всех (i, j)ÎS,

(9)

S aijyij ³ D0, где D0= S bij - C0,

(i, j)ÎS (i, j)ÎS

Lij £ yij £ Uij для всех (i, j)ÎS.

Задачу (9) как и задачу (4) можно решить симплекс-методом. Для этого можно воспользоваться программой SIMPLEX.

Пример 6.

Для сетевого графика изображенного на рис. 2 найти оптимальные значения продолжительностей работ yij, минимизирующих время выполнения проекта в целом при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и D0 =201.

Задача (9) для данного примера при t0=0 имеет вид:

t3® min

y0,1-t1 £0

y0,2-t2 £0

y1,2+t1-t2£0

y1,3+t1-t3£0 (10)

y2,3+t1-t3£0

y0,1+8y0,2+6y1,2+7y1,3+5y2,3³201

2£y0,1£8

5£y0,2£10

1£y1,2£4

4£y1,3£8

6£y2,3£8.

Входной файл для программы SIMPLEX с информацией о данной задаче проведен в приложении 2. В результате работы программы было получено следующее оптимальное решение y0,1=6, y0,2=10, y1,2=4, y1,3=8, y2,3=7, t 1=6, t2=10, Tкр=t 3=17.

Индивидуальные задания

В соответствии с номером индивидуального задания (см. таблицу 9) решить задачу А:

S aijyij® max

(i, j)ÎS ti, yij

ti - tj+yij £ 0 для всех (i, j)ÎS,

- t0+tn £T0,

Lij £ yij £ Uij для всех (i, j)ÎS,

или задачу Б:

Tкр=tn-t0 ® min

ti, yij

ti +yij - tj £0 для всех (i, j)ÎS,

S aijyij ³ D0

(i ,j)ÎS

Lij£yij£Uij для всех (i, j)ÎS.

Необходимые исходные данные взять из таблиц 10-12. Для оптимальных продолжительностей работ yij, найденных в результате решения задачи, определить Ткр, ljр, liп, rijп, rijс, rijн, используя метод критического пути.

Таблица 9.

Номерзада- ния	Номертаб- лицы	Номервари- анта	Зада -ча	Номерзада- ния	Номертаб- лицы	Номервари- анта	Зада -ча
1	10	1	А	13	11	1	Б
2	10	2	А	14	11	2	Б
3	10	3	А	15	11	3	Б
4	10	4	А	16	11	4	Б
5	10	1	Б	17	12	1	А
6	10	2	Б	18	12	2	А
7	10	3	Б	19	12	3	А
8	10	4	Б	20	12	4	А
9	11	1	А	21	12	1	Б
10	11	2	А	22	12	2	Б
11	11	3	А	23	12	3	Б
12	11	4	А	24	12	4	Б

Таблица 10.

Ра- бо- та	Вариант 1	Вариант 2	Вариант 3	Вариант 4
aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij
0,1	5	5	13	4	4	14	3	6	15	5	8	10
0,2	3	3	14	2	6	15	8	9	14	1	7	18
1,2	2	5	7	3	8	10	9	2	6	9	3	6
1,3	4	1	12	6	6	15	6	7	19	2	7	13
2,3	8	1	3	5	11	12	7	3	7	6	3	12
2,4	7	6	10	8	5	16	7	11	17	4	5	10
3,5	8	9	12	7	9	17	4	13	20	7	9	16
4,5	9	4	13	9	6	10	5	12	15	5	7	14
T0	33	40	40	41
D0	392	573	530	416

Таблица 11.

Ра- бо- та	Вариант 1	Вариант 2	Вариант 3	Вариант 4
aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij
0,1	18	14	20	7	8	16	4	7	15	5	4	7
0,2	27	15	18	6	3	19	8	9	13	4	2	12
1,3	16	10	23	3	8	20	5	5	13	7	3	8
2,3	8	5	15	2	4	7	9	3	12	6	2	6
2,4	9	12	16	5	5	22	9	7	12	2	4	11
3,4	12	5	12	7	2	4	2	3	6	9	4	8
3,5	18	7	29	9	9	19	7	7	18	1	2	9
4,5	14	10	15	8	4	20	6	8	10	5	6	11
T0	50	51	35	23
D0	2158	666	590	321

Таблица 12.

Ра- бо- та	Вариант 1	Вариант 2	Вариант 3	Вариант 4
aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij	aij	Lij	Uij
0,1	9	9	18	9	8	19	8	2	15	5	3	11
0,2	8	4	17	5	6	19	6	9	17	3	5	7
1,3	6	3	17	2	6	18	3	6	14	1	4	8
1,4	5	1	11	8	4	16	4	6	17	9	2	4
2,3	3	2	13	3	7	12	2	7	11	6	8	13
2,4	1	1	6	2	3	13	3	5	12	4	4	8
3,5	8	3	12	4	9	11	8	2	9	2	8	11
4,5	6	7	10	7	6	18	5	6	15	5	9	14
T0	35	45	30	23
D0	610	457	467	318

Приложение 1

При формировании файла входных данных для программы SIMPLEX необходимо придерживаться следующих правил:

-  первые две строки должны содержать данные о размерности задачи n и m ,

-  третья строка должна содержать коэффициенты целевой функции и вид оптимизации,

-  следующие m строк должны содержать данные об ограничениях задачи,

-  порядок следования строк нарушать нельзя,

-  числовые данные разделяются одним или несколькими пробелами,

-  символьные данные отделяются от числовых данных ровно одним пробелом.

Рассмотрим использование программы SIMPLEX на примере решения задачи (7). Так как в этой задаче вектор переменных x = (y0,1, y0,2, y1,2, y1,3, y2,3, t1, t2, t3), то входной файл с информацией о решаемой задаче содержит следующие данные:

n= 8

m= 16

1 8 6 7 5 0 0 0 max

1 0 0 0 0 -1 0 0 < 0

0 1 0 0 0 0 -1 0 < 0

0 0 1 0 0 1 -1 0 < 0

0 0 0 1 0 1 0 -1 < 0

0 0 0 0 1 0 1 -1 < 0

0 0 0 0 0 0 0 1 < 15

1 0 0 0 0 0 0 0 < 8

0 1 0 0 0 0 0 0 < 10

0 0 1 0 0 0 0 0 < 4

0 0 0 1 0 0 0 0 < 8

0 0 0 0 1 0 0 0 < 8

1 0 0 0 0 0 0 0 > 2

0 1 0 0 0 0 0 0 > 5

0 0 1 0 0 0 0 0 > 1

0 0 0 1 0 0 0 0 > 4

0 0 0 0 1 0 0 0 > 6

После решения задачи выходной файл программы SIMPLEX будет содержать вектор x=(5, 9, 4, 8, 6, 5, 9, 15). Учитывая структуру вектора x, получим

y0,1=5, y0,2=9, y1,2=4, y1,3=8, y2,3=6 , t1=5, t2=9, t3=15.

Приложение 2

Входной файл для программы SIMPLEX с информацией о задаче (10), в которой вектор переменных x=( y0,1,y0,2,y1,2,y1,3,y2,3 ,t1,t2,t3), содержит следующие данные:

n=8

m=16

0 0 0 0 0 0 0 1 min

1 0 0 0 0 -1 0 0 < 0

0 1 0 0 0 0 -1 0 < 0

0 0 1 0 0 1 -1 0 < 0

0 0 0 1 0 1 0 -1 < 0

0 0 0 0 1 0 1 -1 < 0

1 8 6 7 5 0 0 0 > 201

1 0 0 0 0 0 0 0 < 8

0 1 0 0 0 0 0 0 < 10

0 0 1 0 0 0 0 0 < 4

0 0 0 1 0 0 0 0 < 8

0 0 0 0 1 0 0 0 < 8

1 0 0 0 0 0 0 0 > 2

0 1 0 0 0 0 0 0 > 5

0 0 1 0 0 0 0 0 > 1

0 0 0 1 0 0 0 0 > 4

0 0 0 0 1 0 0 0 > 6

После решения задачи выходной файл программы SIMPLEX будет содержать вектор x=(6,10,4,8,7,6,10,17). Учитывая структуру вектора x, получим y0,1=6, y0,2=10, y1,2=4, y1,3=8, y2,3=7, t 1=6, t2=10, t 3=17.

Литература

1.  Вентцель операций.- М.: Советское радио, 1972.

2.  Основы исследования операций: Т. 1. Пер. с англ.- М.: Мир, 1972.

3.  Алгоритмы оптимизации на сетях и графах.- М.: Мир, 1981.

4.  Гарсиа- Методы анализа сетей: Пер. с англ.-М.:Мир, 1984.

5.  Введение в исследование операций: Кн.2. Пер. с англ.- М.: Мир, 1985.