Текст книги "Менеджмент"

8.5. Целочисленное программирование

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

Аналитическая задача целочисленного программирования формулируется:

где x_j= 0, 1, 2… целые (j = 1…., n1 ≤ n).

Если n₁ = n, то задачу называют полностью целочисленной; если n₁ < n, то частично-целочисленной (ЧЦП).

Предположим, что задача имеет многогранник решений (рис. 8.3). Если наложить требование целочисленности, то допустимое множество решений выразится в системе точек и уже не будет являться выпуклым.

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

Рис. 8.3

1. Новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка – целая.

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

Решение задач целочисленного программирования трудоемко, поэтому по возможности лучше не накладывать ограничений целочисленности переменных.

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

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

x₁, x₂:0 < x₁ ≤ 4; 0 < x_j ≤ 5 число возможных решений – 20. Следовательно, допустим полный перебор возможных сочетаний целочисленных x₁, x₂ и выбор наилучшего в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, поэтому в реальных задачах применяют методы, в которых не рассматривают все возможные альтернативы. Распространены методы отсечений и методы возврата, среди которых наиболее известен метод ветвей и границ.

8.6. Метод ветвей и границ

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

х_j ≤ [х_j*] и х_j ≥ [х_j*] + 1,

где [х_j*] – целая часть нецелочисленного значения переменной х_j* в оптимальном решении. Затем решаются еще две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных.

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

Если одно из решений удовлетворяет требованию целочисленности, значение целевой функции принимается за граничное L. При этом рассмотрение других задач продолжается до тех пор, пока не будет получено:

• на одной из ветвей – недопустимое решение;

• на одной из ветвей – целочисленное решение. Тогда значение целевой функции сравнивается с L (верхним – при пих, нижним – при min); если полученное значение хуже, оно отбрасывается, если лучше, то принимается за граничное;

• на одной из ветвей – нецелочисленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается.

На первом цикле расчета

Пример. Определить значение переменных для следующей оптимизационной задачи:

maх L = 7х₁ + 3х₂; 5х₁ + 2х₂ ≤ 20; 8х₁ + 4х₂ ≤ 38; х₁, х₂ ≥ 0 – целые.

Решение. В результате решения задачи симплекс-методом найдем оптимальное решение:

x₁^1* = 1; x₂^1* = 7,5, L₁ = 29,5,

где верхний индекс переменных – номер задачи (рис. 8.4).

В полученном решении х₂ = 7,5 – нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.

Рис. 8.4

Результаты решения симплекс-методом задачи 2:x₁^2* = 1,2; x₂^2* = 7; L₂ = 29,4.

Результаты решения симплекс-методом задачи 3: x₁^3* = 0,75; x₂^3* = 8; L₃ = 29,25.

В задаче 1 переменная х₁¹ = 1 – целочисленная, а при целочисленности х 2 в последующих задачах х 1 перестала быть целочисленной. Затем следует накладывать ограничения целочисленности на х 1 и т. д.

В качестве оптимального принимается решение задачи 5, которое дает наибольшее из целочисленных решений значение целевой функции.

Из примера видно, что метод ветвей и границ достаточно трудоемкий. При этом оптимальное решение может быть получено в результате сравнения всех допустимых целочисленных решений.

8.7. Задачи с булевыми переменными

В частном случае искомая переменная х_j в результате решения может принимать не любое целое значение, а только одно из двух: 0 либо 1. Чтобы такие переменные отличать от обычных, будем их вместо х_j обозначать δ_j.

И это уже будет означать, что в результате решения задачи cj может быть равным или 0, или 1, т. е. всегда δ_j[0; 1]. Такие переменные обычно называют булевыми в честь предложившего их английского математика Джорджа Буля (1815–1864).

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

Пример. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: материальные и трудовые (табл. 8.7).

Таблица 8.7

Задача выбора вариантов

Возможны четыре варианта расхода ресурсов и получения прибыли. Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех, т. е. k ≤ 3.

Решение. Для составления модели примем, что j – му варианту будет соответствовать δ_j (j = 1… 4). При этом

Тогда математическая модель задачи запишется в виде:

maх L = 65δ₁ + 80δ₂ + 90δ₃ + 210δ₄;

200δ₁ + 180δ₂ + 240δ₃ + 250δ₄ ≤ 800;

10δ₁ + 15δ₂ + 22δ₃ + 28δ₄ ≤ 50;

δ₁ + δ₂ + δ₃ + δ₄ ≤ 3.

Последняя строка системы обеспечивает выполнение условия, чтобы общее число принятых вариантов не превышало трех (табл. 8.8).

Таблица 8.8

Из вариантов решения задачи видно, что наибольшая прибыль (maх L = 300) достигается, если будут приняты третий и четвертый варианты.

С помощью булевых переменных можно накладывать дополнительные логические связи между вариантами. Например, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй, а если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так: δ₂ = δ₄ или в форме записи ограничений δ₂ – δ₄ = 0.

Может быть сформулирован и другой вариант дополнительных условий: например, требуется, чтобы был принят либо третий вариант, либо четвертый, т. е. δ₃ + δ₄ = 1 (результат решения в третьем столбце).

Сравнивая значение прибыли в оптимальном решении (maх L = 300) с прибылью при выполнении дополнительных условий, можно сделать вывод, что они приводят к снижению прибыли.

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

где последнее ограничение (*) может учитывать самые разнообразные условия:

• если накладывается требование «должен», то в ограничении (*) ставится знак равенства;

• если требование «может», то знак неравенства, в частности: если накладывается требование «И», то условие (*):

например принятие и первого и третьего вариантов запишется: д 1 + д 3› 1; если для вариантов накладывается требование «ИЛИ», то условие (*) запишется:

8.8. Дискретное программирование

В этих задачах результатом решения должны быть целые, но не любые целые.

Пример. Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить спинок диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов, чтобы доход был максимальным.

Причем выпуск спинок дивана может принимать любое значение, подлокотники изготавливаются парами, т. е. они должны быть кратны двум, а ножки стульев – четырем (табл. 8.9).

Таблица 8.9

Решение. Математическая модель задачи запишется в виде:

mах L = 20 х₁ + 6 х₂ + 8 х₃;

10 х₁ + 5 х₂ + 4 х₃ ≤ 206;

2 х₁ + 7 х₂ + 4 х₃ ≤ 100;

0 ≤ х₁ ≤ 10;

0 ≤ х₂ ≤ 8;

0 ≤ х₃ ≤ 12;

х₂ = 2δ₂₁ + 4δ₂₂ + 6δ₂₃ + 8δ₂₄;

х₃ = 4δ₃₁ + 8δ₃₂ + 12δ₃₃;

δ₂₁ + δ₂₂ + δ₂₃ + δ₂₄ = 1;

δ₃₁ + δ₃₂ + δ₃₃ = 1,

где δ_2k, δ_3k – варианты количеств подлокотников и ножек (k = 1_ k_i).

Введение булевых переменных дает возможность обеспечить выпуск изделий в кратном заданном количестве. Так, для подлокотников х₂ может принимать следующие значения: если в результате решения будет получено δ₂₁ = 1, а остальные δ₂₂ = δ₂₃ = δ₂₄ = 0, то х₂ = 2; если δ₂₂ = 1, а остальные δ₂₁ = δ₂₃ = δ₂₄ = 0, то х₂ = 4 и т. д.

Для решения задачи с учетом дополнительных условий мы ввели еще семь переменных и четыре ограничения. Если бы требовалось определить выпуск спинок, подлокотников и ножек для одного изделия (комплекта), то можно было бы записать х₂ = 2х₁, х₃ = 4х₁ и не вводить дополнительные ограничения и булевы переменные.

В результате решения задачи получены следующие значения:

max L = 320; х₁⁰ = 10; х₂⁰ = 4; х₃⁰ = 12;

δ⁰₂₂ = δ⁰₃₃ = 1; δ⁰₂₁ = δ⁰₂₃ = δ⁰₂₄ = δ⁰₃₁ = δ⁰₃₂ = 0

При этом не полностью использованы ресурсы: резерв первого равен 50, второго – 4 ед.

В общем виде задачу распределения ресурсов с учетом требования дискретности значений переменных можно записать:

где d_1j, d_2j, d_kj,… – дискретные значения, которые может принимать переменная х… Эта система отличается от обычной задачи распределения ресурсов появлением булевых переменных и увеличением числа ограничений:

8.9. Параметрическое программирование

Задача параметрического программирования имеет следующий вид:

при условиях

где c′_j, c′′_j, a_ij, b_i – заданные постоянные числа.

Может быть поставлена и обобщенная параметрическая задача, в которой от параметра t линейно зависят коэффициенты при неизвестных в целевой функции (цены изделий от спроса на них), в системе уравнений (нормы расхода ресурсов от применяемых технологий), свободные члены системы уравнений (наличие ресурсов от предложений поставщиков):

где a, β – промежуток изменения значений параметра t (—∞, +∞).

Решение задач (1)-(3), (4)-(7) можно найти методами линейного программирования.

Предположим, что в задаче (1)-(3) множество неотрицательных решений системы линейных уравнений (2) (многогранник решений) не пустое и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом параметре t ∈ [a, β] такой точки многогранника решений, в которой функция (1) принимает maх. Чтобы найти эту точку, будем считать t = t₀ и находим решение полученной задачи линейного программирования ЛП (1)-(3), т. е. определим вершину многогранника решений, в которой функция (1) имеет maх, либо устанавливаем, что при данном значении t₀ задача неразрешима.

После нахождения точки, в которой при t = t₀ функция (1) принимает maх, ищут множество значений t, для которых координаты этой точки определяют оптимальный план задачи (1)-(3). Найденные параметры t исключают из рассмотрения и берут некоторое новое значение t из промежутка [a, β].

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

Пример. Пусть предприятие изготавливает два вида продукции А, В, для которых использует три вида ресурсов. Известны нормы расхода и запасы каждого вида (табл. 8.10).

Из анализа спроса установлено, что цена единицы продукции для изделия А может изменяться от 2 до $12, а для изделия В – от 13 до $3, причем эти изменения определяются соотношениями

c₁ = 2 + t, c₂ = 13 – t, где 0 ≤ t ≤ 10. Требуется для

Таблица 8.10

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

Решение. Математически задача формулируется в виде:

Для решения задачи (8)-(10) строим многоугольник решений, определенный системой линейных неравенств (9) и условием неотрицательности переменных (рис. 8.5).

После этого, полагая t = 0, строим целевую функцию 2х₁ + 13х₂ = 26 (число 26 – произвольно) и вектор c = (2; 13). Передвигая эту прямую в направлении вектора c, можно установить последнюю ее точку с многоугольником решений OABCD, т. е. точку А(0; 11).

Рис. 8.5

Следовательно, задача, полученная из задачи (8)-(10) при t = 0, имеет оптимальный план x₀^* = (0; 11). Это означает, что если цена изделия А равна 2 + 0 = $2, а цена изделия В 13 – 0 = $13, то в оптимальном плане производство изделий А не предусматривается, а изделий В требуется изготовить в количестве 11 ед. и максимальная выручка составит maх F = $143.

Положим теперь t = 2 и построим прямую целевой функции (2 + 2) х₁ + (13 – 2) х₂ = = 4х₁ + 11х₂ = 44 (число 44 – произвольно) и вектор c 1 (4; 11). Передвигая эту прямую в направлении вектора c 1, устанавливаем последнюю точку многоугольника решений – ту же точку А (0; 11).

Следовательно, при t = 2 задача, полученная из задачи (8)-(10), имеет тот же оптимальный план x₀^* = (0; 11), означающий, что при цене изделия А $4, а изделия В – $11 требуется изготовить только 11 ед. изделия В, которые обеспечат максимум выручки maх F = 11 ч 11 = $121.

Данный план производства будет оставаться оптимальным для всякого значения t, пока прямая целевой функции (2 + t)х₁ + (13 – t) х₂ = L не станет параллельной прямой 2х₁ + 2х₂ = 22. Это произойдет, когда

т. е. при t = 5,5 координаты любой точки отрезка АВ дают оптимальный план задачи (8)-(10).

Таким образом, для всякого 0 ≤ t ≤ 5,5 задача (8)-(10) имеет оптимальный план x₀^* = (0; 11), при котором значение целевой функции maх F = (2 + t) х₁ + (13-t)х₂ = (2 + t) × 0 + (13– t) × 11 = 143-11t.

При значениях параметра t, больших 5,5, например t = 6, прямая целевой функции: 8х₁ + 7х₂ = 56 (56 – произвольно), которой соответствует вектор c₂(8; 7); в направлении движения по этому вектору последняя точка В (1;10), т. е. при цене А2 + 6 = $8, при цене В13 – 6 = $7 x₁⁰ = 1; x₂⁰ = 10; maх F = $78.

План x^*₁= (1; 10) будет оптимальным для задачи (8)-(10) для всякого t > 5,5, пока прямая целевой функции ЦФ не станет параллельной прямой 6х₁ + 3х₂ = 36. Это произойдет, когда

т. е. при t = 8, при котором координаты любой точки отрезка ВС дают оптимальный план задачи (8)-(10).

Таким образом, для всякого 5,5 ≤ t ≤ 8 задача (8)-(10) имеет оптимальный план x₁^* = (1; 10), при котором значение целевой функции maх F = (2 + t) × 1 + (13 – t) × 10 = 132 – 9 t.

Аналогично рассуждая, получим, что для всякого 8 ≤ t ≤ 10 оптимальным планом задачи (8)-(10) будет x₂^* = (2; 8), т. е. если цена изделия А заключена между (или равна) 10 и $12, а изделия В – между 3 и $5, то x₁⁰ = 2 ед., x₂⁰ = 8 ед., которые обеспечат максимальную выручку maх F = 108 – 6 t.

Окончательно:

8.10. Дробно-линейное программирование

Общая задача дробно-линейного программирования формулируется в виде:

где d₁х₁ + d₂х₂ > 0.

Задача решается в следующей последовательности:

1. В ограничивающих уравнениях заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые.

2. Находят полуплоскости, определяемые каждым из неравенств системы ограничений задачи.

3. Находят область (многоугольник) допустимых решений задачи.

4. Строят прямую

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

5. Определяют точку максимума или устанавливают неразрешимость задачи.

6. Находят значение целевой функции в точке максимума.

Пример. Пусть для производства двух видов изделий а и в используются три типа технологического оборудования. Известны затраты времени и других ресурсов на производство единицы изделия каждого вида (табл. 8.11).

Таблица 8.11

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

Решение.

Решение задачи определяется из области допустимых вариантов (рис. 8.6).

Область допустимых вариантов решения представляется треугольником bcd. Значит, целевая функция принимает значение в одной из точек: b, c или D. Чтобы определить, в какой именно из этих точек, положим значение функции l равным некоторому числу, например 11/4:

Рис. 8.6

Это уравнение определяет прямую, проходящую через начало координат. Координаты точек этой прямой, принадлежащие и многоугольнику решений, являются планами задачи, при которых значение целевой функции равно 11/4. В данном случае к указанным точкам относится только одна точка B (1; 3).

Теперь положим, что

Это уравнение определяет прямую, проходящую через начало координат. Ее можно рассматривать как прямую, полученную в результате вращения прямой (8) по часовой стрелке вокруг начала координат. Следовательно, если положить значение целевой функции равным некоторому числу L₀

а прямую (10), проходящую через начало координат, вращать в направлении часовой стрелки вокруг начала координат, то получим прямые

Последней общей точкой вращаемой прямой с областью допустимых вариантов решения будет точка D (3; 1), в которой достигается минимум целевой функции. Таким образом, оптимальный план заключается в производстве трех изделий А и одного изделия В, обеспечивающем минимальную себестоимость одного изделия, равного.

Задача дробно-линейного программирования при n› 2 может быть решена сведением ее к задаче линейного программирования. Для этого следует обозначить через

и ввести новые переменные у_j = у₀х_j, (j = 1… n).

Тогда исходная задача (1)-(3) сведется к следующей:

Задача (11)-(14) – это задача линейного программирования, и, следовательно, ее решение можно найти известными методами.

Пример. Определить решение следующей оптимизационной задачи:

Здесь х₃, х₄, х₅ – фиктивные переменные, преобразующие неравенства в равенства.

Решение. Обозначим у₀ = (х₁ + х₂)^-1 и вводим новые переменные у₀ = (х₁ + х₂)^-1. Получим задачу линейного программирования:

Ее оптимальный план:

у₁⁰ = 0,9; у₃⁰ = 0,1;

у₃⁰= у₄⁰ = 0;

у₅⁰ = 1,5; у₀⁰= 0,1.

Так как у_j = у₀х_j, то оптимальный план исходной задачи:

8.11. Блочное программирование

В решении экономических задач часто появляются математические модели, в которых отдельные ограничивающие условия содержат все переменные (ограничения, образующие блок-связку), а другие – только часть переменных (ограничения, образующие блоки). Математическая формулировка может содержать значительное число блоков (рис. 8.7).

Такой задаче соответствует особая структура исходных данных (табл. 8.12).

Таблица 8.12

Применительно к матрице блочной структуры математическую постановку задачи можно переписать иначе, вводя двухиндексное обозначение переменной х_рj, указывающей на принадлежность переменной х_j к p – му локальному блоку:

где P – общее число локальных блоков; n_p – число переменных, входящих в р-й локальный блок; m_p – число ограничений в р-м локальном блоке.

Постановка задач данного класса относится к производственным комплексам, холдингам, финансово-промышленным группам, корпорациям и т. п. В свою очередь, они имеют в своем составе нескольких других предприятий, отличающихся индивидуальными локальными характеристиками (ресурсы, показатели), но в то же время объединенных совокупностью ограничений (общих для всей системы) и единой целевой функцией.

Особенность таких задач – большая размерность.

Современные программные средства в большинстве используют специальные методы решения с разложением (декомпозицией) задачи на Р подзадач, например метод декомпозиции Данцига-Вульфа. По этому методу каждый блок матрицы формируется и отлаживается автономно как отдельная подзадача с последующим объединением блоков общими ограничениями на этапе окончательного составления задачи. Такие задачи экономически интерпретируются как задачи многоуровневой иерархической структуры.

8.12. Теория графов

Наглядность геометрии широко используют при анализе больших технических и организационных систем.

Граф – универсальное средство наглядного представления достаточно разнообразных задач в виде совокупности вершин и ребер. Варианты сочетаний различных ребер и вершин представляют многообразие возможных графов и способов их применения.

Сетями представляют различные задачи, в которых исследуют перемещение или выполнение работ во времени. Характеристиками сети являются ее структура и параметры дуг. Структура (топология) сети демонстрирует взаимосвязь различных вершин и направление связывающих их дуг.

Каждую вершину сети нумеруют порядковым номером. Начальную вершину в описании движения потоков называют источником, конечную – стоком.

Рис. 8.8. Двойная индексация дуги сети

Дугу сети обозначают двойной индексацией 1–2; 3–4 (рис. 8.8) и т. д. (по номерам вершин, на которые дуга опирается). В общем случае дугу обозначают «i – j», где i – номер вершины, из которой исходит дуга; j – номер вершины, в которую входит дуга. Каждая дуга имеет свои характеристики (рис. 8.9); t ij – продолжительность движения по дуге i – j; c ij – стоимость перемещения; d ij – пропускная способность дуги и т. д.

Зная топологию сети и ее параметры, можно решать разнообразные задачи оптимизации.

Рис. 8.9. Характеристики дуги сети

Сетевой график (сеть) состоит из дуг и узлов (вершин). Дуге соответствует выполняемая работа (обозначается стрелкой); вершине – событие, т. е. состояние перед работой (обозначается кружком).

Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает последовательность работ и продолжительность выполнения каждой работы (табл. 8.13).

Таблица 8.13 Исходные данные для составления сетевого графика

Два события отметим особо: начальное – состояние, с которого начинается весь комплекс работ; конечное – состояние, которым завершается комплекс работ.

По исходным данным строится сетевой график (рис. 8.10).

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

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

Если руководитель следит за выполнением всех работ в срок, то он должен четко знать и особо контролировать работы критического пути.

Перейдем к формализации. В нашем примере время наступления каждого события может быть найдено по зависимостям

Рис. 8.10. Сетевой график

Так как третье событие может наступить после выполнения работ 2–3 и 1–3, запишем:

Аналогично найдем время наступления последнего события:

Окончательно время наступления событий будет равно:

Т₁ = 0; Т₂ = 1; Т₃ = 5; Т₄ = 11

Резерв работы 1–3 будем обозначать Δ₁₃ = 5–2 = 3. Значит, работа 1–3 может быть начата не в начальный момент времени, а спустя 3 ед. времени или продолжаться на 3 ед. больше, чем первоначально предполагалось, т. е. может длиться 2 + 3 = 5 ед. без увеличения момента наступления конечного события 4 (рис. 8.11).

Рис. 8.11. Временной резерв работы

1–3 Аналогично Δ₂₄ = Т₄ – (Т₂ + t₂₄) = 11 – (1 + 3) = 7, т. е. продолжительность работы 2–4 может быть увеличена на 7 ед. Очевидно, что для работ критического пути резерв времени равен 0, т. е. Δ₁₂ = Δ₂₃ = Δ₃₄ = 0.

Для третьего события можно записать Т₃ = Т₁ + t₁₃ + Δ₁₃.

Отсюда (Т₃ – Т₁) – Δ₁₃ = t₁₃. Выражение (Т₃ – Т₁) записано в скобках, чтобы было наглядно видно, что это интервал времени между двумя последовательными событиями. И этот интервал за вычетом резерва Δ₁₃ равен продолжительности работы 1–3. В этой зависимости нам задана продолжительность работы t₁₃ = 2 (правая часть уравнения), остальные величины – искомые переменные. Если их обозначить Т₃ =x₃; Δ₁₃ =x₁₃; Т₁ =x₁; t₁₃ =b₁₃, то можно записать (x₃ – x₁)-x₁₃ = b₁₃ и получить линейное уравнение с тремя неизвестными.

Если записать аналогичные зависимости для всех событий и работ, входящих в нашу сеть, то получим систему:

Эта система описывает топологию (структуру) нашей сети.

Если вместо t_ij подставить их известные (заданные) значения, получим:

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

При этом возможны две постановки задач оптимизации.

Первая постановка: задаемся временем начала работ, т. е. значением Т₁, например Т₁ = 0, и стремимся закончить комплекс работ как можно раньше:

Вторая постановка: задан срок завершения всех работ, например Т₄ = 15, и мы заинтересованы в как можно более позднем начале работы, но с соблюдением намеченного срока:

В общем виде топология сети запишется:

(T_j – T_i) – Δ_ij… = t_ij (для всех i,j). (*)

Если обозначить S – число событий, R – число работ, то, как видно из (*), система, описывающая сеть, будет включать n переменных, где n = S + R, так как каждому i – му событию соответствует неизвестная T_i, а каждой i, j – й работе – неизвестная Δ_ij А число ограничений m = R, т. е. каждой работе соответствует ограничение.

Поэтому в начальных сетях одна строка (*) превращается в систему линейных уравнений, содержащую сотни, а может быть и тысячи неизвестных и ограничений. Тогда общие постановки запишутся:

где T_1пл, T_nпл – заданные плановые сроки начала и окончания работ сети.

Например, для графика из 11 событий и 20 работ (рис. 8.12) первая постановка при Т₁ = 0 будет иметь вид:

Рис. 8.12. График 11 событий и 20 работ