25. Сетевые модели: задача о кратчайшем пути (задача о замене персонала)

П усть имеется сеть с источником s и стоком t. Известно расстояние между i-м и j-м узлами. Необходимо найти кратчайший путь от начального узла до конечного узла. Обозначим через xij булеву переменную, которая равна 1, если узел принадлежит кратчайшему пути, и 0 – в противном случае.

Экономико – математическая модель задачи:

Первое ограничение означает, что единица потока вытекает из источника s; второе ограничение – что единица потока втекает в сток r; третье ограничение гарантирует сохранение потока при протекании по сети.

26. Задача оптимизации и поиск решения

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

• Переменные - неизвестные величины, которые нужно найти при решении задачи.

• Целевая функция - величина, которая зависит от переменных и является целью, ключевым показателем эффективности или оптимальности модели.

• Ограничения - условия, которым должны удовлетворять переменные.

Проблемы оптимизации присутствуют в самых различных процессах производства:

• поставка сырья;

• оптимальный выпуск продукции;

• оптимальное управление запасами ;

• оптимальное распределение ресурсов;

• планирования инвестиций;

• оптимальный рацион (смесь, сплав);

• назначение на должность;

• оптимальная замена оборудования и т. д

27. Транспортная задача

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

Цель транспортной деятельности считается достигнутой при выполнении шести условий:

1. нужный товар;

2. необходимого качества;

3. в необходимом количестве доставлен;

4. в нужное время;

5. в нужное место;

6. с минимальными затратами.

Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.

Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k С i j.

Далее, где ai есть количество продукции, находящееся на складе i , и bj - потребность потребителя j.

Ограничения транспортной задачи:

4. Все ресурсы поставщиков должны быть вывезены полностью

5. Все потребности должны быть удовлетворены

6. Объем перевозки не может быть отрицательным

X_ij ≥ 0

Решение транспортной задачи методом потенциалов, Метод юго-западного угла,