Математические методы линейного программирования в сетевой системе

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

Для применения аппарата линейного программирования при оптимизации сетевых графиков необходимо выполнение следующих условий:

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

Ck = ak + bk tk.

где Ck — затраты на выполнение к-й работы;

tk — время выполнения к-й работы;

ak, bk — константы линейной функции.

2. Продолжительность выполнения каждой работы ограничена.

dk tk Dk.

гдеdk, Dk — экстремальные значения tk.

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

dk >0; Dk <

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

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

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

Tmin T Tmax.

где Tmax — продолжительность выполнения комплекса работ при условии tk=Dk;

Tmin — продолжительность выполнения комплекса работ при условии tk=dk (равна величине критического пути сетевого графика).

Затраты на выполнение комплекса работ также ограничены.

Smin S Smax.

где Smaxзатраты на выполнение комплекса работ при условии tk=dk, т. е.

Smax =.

Smin — затраты на выполнение комплекса работ при условии tk=Dk, т. е.

Smin =.

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

• а) минимизацию затрат на выполнение комплекса работпри заданном времени;
• б) минимизацию времени выполнения комплекса работ при заданных затратах;
• в) минимизацию суммарных затрат по комплексу работ и объекту.

Рассмотрим три части курсового проекта:

Минимизация затрат на выполнение комплекса работ при заданном времени

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

Формализованная структура задачи следующая:

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

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

Целевую функцию можно свести к следующему виду:

Система ограничений состоит из следующих подсистем:

• а) tk dk
• б) tk Dk

Число выражений в каждой из этих подсистем совпадает с числом действительных работ Nраб.

в).

где — булева переменная;

• 1, если k-я работа входит в 1-й полный путь
• 0,если k-я работа не входит в 1-й полный путь

Каждое выражение данной подсистемы ограничений определяет максимальную продолжительность каждого полного пути сетевого графика. Число выражений совпадает с числом полных путей.

В связи с тем, что одним из общих ограничений задач линейного программирования является X 0, в рассмотренной задаче необходимо ввести новые переменные, отвечающие этому требованию, т. е.

С учетом введения новых переменных система ограничений примет вид:

а).

б).

в) 1=1,.

В связи с введением новых переменных целевая функция примет вид:

Преобразуем полученную целевую функцию:

Но вторая часть функции константа, т. е.

Тогда целевая функция примет вид:

Для дальнейших расчетов в качестве целевой функции будет использоваться выражение:

где.

Если рассмотреть структуру полученной задачи линейного программирования, то выяснится, что это вторая частная параметрическая задача. В системе ограничения в составе свободного члена используется параметр T, предел изменения которого определен выражением (4).

Преобразуем задачу таким образом, чтобы параметр T был в целевой функции, т. е. перейдем к первой частной параметрической задаче. Для этого используем принцип двойственности. Целевая функция примет вид:

Система ограничений:

гдебулева переменная:

1, если входит в к-е ограничение, если не входит в к-е ограничение Справедливо соотношение (для оптимальных планов прямой и двойственной задачи):

Двойственно-сопряженная задача на максимум. Перейдем от задачи на минимум к задаче на максимум. Для этого умножим целевую функцию (24) на -1.

Получим:

для которой.

Решение двойственной задачи позволяет установить:

a) деление исходного интервала изменения T (4) на частные интервалы, в пределах которых оптимальное значение будет постоянным;

b) значениедля каждого частного интервала;

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

где Ai, Bi — коэффициент линейной функции для i-го частного интервала.

Используя выражение (28), можно определить значение минимальных затрат, соответствующих Tд.

Для этого достаточно:

а) определить частный интервал изменения T, в который попадает Tд,.

где , — границы i-го частного интервала.

Это, в свою очередь, позволяет определить значения Ai и Bi.

б) подставить значения Tд в выражение (28), т. е.

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

Для решения данной задачи можно использовать алгоритм решения параметрической задачи «Минимизация затрат на выполнение комплекса работ при заданном времени выполнения». Схема выполнения данной задачи следующая:

• а) решается задача минимизации затрат на выполнение комплекса работ, в результате чего устанавливают:
  • — частный интервал времени T;
  • — значение неизвестных для каждого частного интервала;
  • — вид целевой функции от T.
• б) определяются граничные значения затрат для каждого частного интервала, т. е.:

где Ai, Bi — показатели целевой функции основной задачи,.

• в) определяется частный интервал, в который попадет заданное значение;
• г) определяется минимальное время выполнения комплекса работ:

Минимизация суммарных затрат по комплексу работ и объекту

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

Пример: комплекс работ — подразделение системы комплексного обслуживания, объект — судно.

Для решения данной задачи можно использовать алгоритм решения параметрической задачи «Минимизация затрат на выполнение комплекса работ при заданном времени».

Схема решения задачи минимизации суммарных затрат по комплексу работ и объекту следующая:

• а) решается параметрическая задача минимизации затрат по комплексу работ при заданном времени, в результате чего устанавливаются:
  • — частные интервалы изменения T;
  • — значения неизвестных для каждого частного интервала;
  • — вид целевой функции минимизации затрат на выполнение комплекса работ от T;
• б) формируется вид целевой функции минимизации затрат на выполнение комплекса работ и по объекту.

Zсум=Zком + Zоб, где Zсум — значение целевой функции минимизации суммарных затрат;

Zком — значение целевой функции минимизации затрат по комплексу работ;

Zоб — значение затрат по объекту за время выполнения комплекса.

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

• а) частного интервала, в пределах которого Zсум принимает минимальное значение.
• б) значения T, при котором Zсум принимает минимальное значение.