1.2.2. Математическая формулировка задачи

Каждой работе ставится в соответствие переменная X_i,

i =1..13, принимающая два значения: 1 или 0.

Значение X_i, равное 1, означает, что соответствующая ей

i-тая работа выполняется, а равное 0 – не выполняется.

Целевая функция имеет вид:

Z =,

где D_i – продолжительность i-той работы, i = 1..13.

Для решения поставленной задачи требуется найти минимум

(максимум) целевой функции Z: Z  min или Z  mах,

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

1. Налагаемых на значения X_i : X_i = 1 или 0, i = 1..13.

2. Налагаемых на вершины сетевого графика:

а) сумма X_i работ, исходящих из начальной вершины сети А₀,

Таблица 1.4
Вершины	Ограничения
А1	X1-X5-X6= 0
А2	X3-X7-X8= 0
А3	X2+X6-X9= 0
А4	X4+X8-X10= 0
А5	X7+X9-X11-X12= 0
А6	X5+X11-X13= 0

равна 1: X₁+X₂+X₃+X₄=1;

б) сумма X_i работ, входящих в

конечную вершину сети А₇,

равна 1: X₁₀+X₁₂+X₁₃=1;

в) суммы X_i работ, входящих и исходящих из каждой промежу-точной вершины сети А₁, А₂.. А₆ , равны 0.

В таблице 1.4 приведены ограни-

чения для промежуточных вершин сети.

1.2.3. Решение задачи средствами ms Excel

На рис. 1.2 показан расчётный бланк решения задачи.

Исходные данные:

● наименования работ введены в ячейки С5:О5;

● продолжительности работ D_i , i = 1..13 – в ячейки С6:О6.

Результаты расчёта:

● значения X_i (i =1..13) выводятся в ячейки С8:О8;

● значение целевой функции Z – в С9.

Расчётные формулы:

● целевая функция: С9=СУММПРОИЗВ(C6:O6; C8:O8);

● формулы для расчёта левых частей ограничений (в соот-

ветствии с а), б), в), стр. 7-8):

C14=C8+D8+E8+F8	C15=L8+N8+O8
C16=C8-G8-H8	C17=E8-I8-J8
C18=D8+H8-K8	C19=F8+J8-L8
C20=I8+K8-M8-N8	C21=G8+M8-O8

● ячейки D14:D21(знаки ограничений) и E14:E21(правые час-

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

Рис. 1.2. Расчётный бланк решения задачи.

Запуск на выполнение: Сервис | Поиск решения.

Сначала настраиваем окно “Поиск решения” (рис. 1.3).

В поле “Установить целевую ячейку” вводим С9, задаём оп- цию “максимальному значению” или “минимальному значе-нию” в зависимости от того ищется максимум или минимум целевой функции.

В качестве примера зададим опцию “максимальному значе-нию” и, следовательно, будем искать максимум целевой фун-кции.

В поле “Изменяя ячейки” указываем ячейки С8:О8, в них в

результате расчёта будут выведены значения переменных X_i

Рис. 1.3. Диалоговое окно надстройки “Поиск решения”

Ограничение на значения X_i вводятся в окне “Добавление ог- раничения” как “двоич” (рис. 1.4). Остальные ограничения вводятся с помощью окна “Добавление ограничения” так,

как пoказано на панели “Ограничения” окна “Поиск реше-

ния”.

Рис.1.4. Ввод ограничения “двоич” для значений X_i.

В завершении щёлкаем левой клавишей мыши по кнопке “Выполнить”.

В окне “Результаты поиска решения” щёлкаем по OK.

В результате выполнения (рис. 1.5) имеем: значения пере-

менных X₁, X₆, X₉, X₁₁ и X₁₃ (ячейки С8, Н8, K8, M8 и О8) равны

1 и, следовательно, соответствующие им работы 1, 6, 9, 11 и 13 образуют максимальную по продолжительности последо-вательность. Суммарная продолжительность этих работ (це-левая функция Z) равна 25.

Рис. 1.5. Фрагмент бланка с результатами расчета.

Графическая интерпретация результатов:

двойными линиями на сетевом графике выделяем рёбра, со-ответствующие работам 1, 6, 9, 11, 13 (рис. 1.6). Эти рёбра образуют максимальный по продолжительности путь в сети.

Рис. 1.6. Максимальный по продолжительности путь в сети