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

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

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

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

C_k = a_{k +} b_k t_k (1)

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

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

a_k, b_k – константы линейной функции.

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

d_k t_k D_k (2)

где d_k, D_k – экстремальные значения t_k.

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

d_k >0; D_k < (3)

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

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

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

T_min T T_max (4)

где T_max – продолжительность выполнения комплекса работ при условии t_k=D_k;

T_min – продолжительность выполнения комплекса работ при условии t_k=d_k (равна величине критического пути сетевого графика).

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

S_min S S_max (5)

где S_max– затраты на выполнение комплекса работ при условии t_k=d_k, т. е.

S_max = (6)

S_min – затраты на выполнение комплекса работ при условии t_k=D_k, т. е.

S_min = (7)

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

а) минимизацию затрат на выполнение комплекса работ при заданном времени;

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

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

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

Дата добавления: 2015-10-28