Сферы применения, использования.

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

 

40. Правило построения сетевых моделей.

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

Правила построения сетевой модели:

1.Должно быть только 1 исходное и 1 завершающее событие.

2.В сети не должно быть висячих событий, кроме исходного события.

3.Нумерация событий слева на право.

4.Между двумя соседними событиями может быть только 1 работа.

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

6.Сетевая модель должна иметь максимально простую форму.

7.Сетевая модель должна строго соответствовать технологическому процессу

8.Каждая работа маркеруется 2-мя цифрами. Первая – номер события начала работы. Вторая – номер события окончания работы.

 

 

42. Сетевая модель. Расчет временных параметров.

Главной характеристикой сетевого графика является длина критического пути. Расчет критического пути выполняют в два этапа (от начала к концу сетевого графика). На первом этапе определяют ранние сроки наступления событий, а на втором – поздние сроки наступления событий.

1.Вычисление ранних сроков наступления событий:

- ранний срок начала всех работ, выходящих из события i.

-ранний срок начала всех работ, входящих в событие j.

- время выполнения работ.

= max( + ).

2.Вычисление поздних сроков наступления событий.

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

= min ( + ).

 

44. Дискретное программирование. Задача целочисленного программирования.

ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ- область математики, занимающаяся исследованием и решением экстремальных задач на конечных множествах.

Методы решения целочисленных ЗЛП:

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

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

Целочисленные задачи математического программирования могут возникать различными путями.

1. Существуют ЗЛП, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач – транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).

2. Толчком к изучению целочисленных задач в собственном смысле слова явилось рассмотрение ЗЛП, в которых переменные представляли физически неделимые величины. Они были названы задачами с неделимостью. Таковы, например, задачи об оптимизации комплекса средств доставки грузов, о нахождении минимального порожнего пробега автомобилей при выполнении заданного плана перевозок.

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

 

50. Динамическое программирование. Принцип оптимальности Беллмона.

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

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

Принцип решения ДП:

1.Выбрать параметры, характеризующие состояние системы S, перед каждым шагом.

2.Расчленить операцию на этапы (шаги)

3.Выяснить набор шаговых управлений x1 для каждого шага и налагаемые на них ограничения.

4.Определить какой

выигрыш приносит на i-шаге управление x_i, записать функцию выигрыша.

5.Определить, как изменяется состояние под влиянием управления x_i, на i-шаге.

6.Записать основное рекуррентное уравнение ДП, выражающее условный оптимальный выигрыш (начиная с i-шага и до конца)

7.Произвести условнуюоптимизацию последнего m-шага.

8.Произвести условную оптимизацию m-1, m-2 шагов, для каждого указать условное оптимальное управление

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