Задачи линейного программирования

СОДЕРЖАНИЕ

Введение 3

1. Задачи линейного программирования 4

1.1. Однородная транспортная задача 5

2. Статическая транспортная задача 7

2.1. Введение элементов динамики в потоковые задачи 11

3. Динамическая транспортная задача с задержками 14

4. Сетевые постановки транспортных задач 17

5. Динамическая транспортная задача с управляемыми задержками 19

6. Метод динамического согласования производства и транспорта 22

7. Многопродуктовая динамическая транспортная задача 24

8. Метод оптимизации динамической управляемой структуры

транспортных систем 26

9. Вероятностные эффекты в потоковых динамических задачах 34

10. Оптимизация работы железнодорожного узла 38

11. Потоковые задачи управления обращением кольцевыми маршрутами 43

12. Динамические резервы 53

12.1. Управление однородными потоками 54

12.2. Управление разнородными потоками 56

12.3. Гибкое взаимодействие производства и транспорта 58

Заключение 67

Библиографический список 68

ВВЕДЕНИЕ

В настоящее время существенно изменился характер работы и основная задача железных дорог. Основной задачей транспорта является уже не «пропуск потоков», а «транспортное обслуживание». Задача «транспортное обслуживание» требует от дороги либо создания резервов путей, вагонов, локомотивов для надежного обеспечения работающего в разных ритмах производства, либо перехода на новую технологию управления грузопотоками и вагонопотоками. Эффективное управление замещает резервы. Новый вид управления требует включения в действующие автоматизированные системы управляющих блоков. Основу этих блоков должны стать методы оптимального управления грузопотоками и вагонопотоками. Эффективное транспортное обслуживание территориально-распределенного производства требует согласованного подвода различных грузов из разных пунктов к потребителю. Для этого нужно новое, системное управление грузопотоками и вагонопотоками на базе математических методов.

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

Задачи изучения курса:

– ознакомить студентов с различными постановками транспортных задач линейного программирования;

– сформировать у студентов знания и умения применять задачи транспортного типа для решения конкретных задач на транспорте;

– обучить студентов способам решения транспортных задач на ПЭВМ – формализации задачи, представлении данных в общепринятом формате задачи линейного программирования, вводу данных в ПЭВМ и решению с применением стандартных пакетов решения задач линейного программирования;

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

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

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

Задачи линейного программирования

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

(линейной функции элементов решения накладываемых на элементы решения)

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

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

Правило сокращенного суммирования.

Для обозначения суммы чисел

принята такая запись:

Это обозначение очень удобно:

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

1.1. Однородная транспортная задача

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

• минимизирующий суммарную стоимость транспортировки,

• не превышающий объем производства в каждом пункте поставки,

• полностью покрывающий потребности в каждом пункте потребления,

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

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

Имеется т пунктов поставки (поставщиков) и п пунктов потребления некого однородного продукта. Для каждого поставщика i =1…m задан объем производства , а для каждого потребителя j =1…n задан объем потребления и известна стоимость доставки единицы продукта из пункта производства iв пункт потребления j. Переменные характеризуют объем перевозки между каждым поставщиком i =1…mи потребителем j =1…n

В случае сбалансированного производства и потребления:

оптимальный план транспортировки соответствует минимизации линейной целевой функции:

при т линейных ограничениях по поставке:

и п линейных ограничениях по потреблению:

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

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