ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ МАКСИМИЗАЦИИ ПОТОКА.

Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть ХKM — объем перевозок из пункта К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных ХKM , а именно, Х01 , Х02 , Х03 , Х12 , Х13 , Х14 , Х23 , Х24 , Х34. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F > max ,

Х01 + Х02 + Х03 = F (0)

— Х01 + Х12 + Х13 + Х14 = 0 (1)

— Х02 — Х12 + Х23 + Х24 = 0 (2)

— Х03 — Х13 — Х23 + Х34 = 0 (3)

— Х14 — Х24 — Х34 = — F (4)

Х01 ? 2

Х02 ? 3

Х03 ? 1

Х12 ? 4

Х13 ? 1

Х14 ? 3

Х23 ? 1

Х24 ? 2

Х34 ? 2

ХКМ ? 0 , К, М = 0, 1, 2, 3, F ? 0.

Здесь F — целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) — (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) — это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем в системе ограничений задачи линейного программирования указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию — через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).

Январь 24, 2019 Психология труда, инженерная психология, эргономика
Еще по теме
Методы решения задач линейного программирования.
3.2.1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ КАК НАУЧНО-ПРАКТИЧЕСКАЯ ДИСЦИПЛИНА.
ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ.
ВОСПРИЯТИЕ НЕПРЕРЫВНОСТИ СВЕТОВОГО ПОТОКА ПРИ ПРЕРЫВИСТОМ ОСВЕЩЕНИИ: КЧМ
ИСПОЛЬЗОВАНИЕ МЕТОДА ПРОЕКТОВ В ОРГАНИЗАЦИИ ИССЛЕДОВАТЕЛЬСКОЙ ДЕЯТЕЛЬНОСТИ УЧАЩИХСЯ ПРИ ИЗУЧЕНИИ ПРОГРАММИРОВАНИЯ В КУРСЕ ИНФОРМАТИКИ И ИКТ
5.3.1. СТИЛЬ ПРОГРАММИРОВАНИЯ СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
3.2. ЗАДАЧИ ОПТИМИЗАЦИИ ПРИ ПРИНЯТИИ РЕШЕНИЙ
ЦЕЛЕВАЯ ПРОГРАММА АЛЯ МАКСИМИЗАЦИИ ПРОДУКТИВНОСТИ И КАЧЕСТВА РАБОТЫ
ИМПУЛЬСИВНОСТЬ ПРИ РЕШЕНИИ ИНТЕЛЛЕКТУАЛЬ-НЫХ ЗАДАЧ
Задачи педагога при работе с умственно отсталыми детьми
ОСОБЕННОСТИ АКТИВАЦИИ СЕМАНТИЧЕСКОЙ СЕТИ ПРИ РЕШЕНИИ ТВОРЧЕСКИХ ЗАДАЧ
Чеботарева С.В. ЗАДАЧИ психолога при подготовке девятиклассников к выбору профиля обучения
Иванов А. А. Гришакова Е. М. ИЗУЧЕНИЕ СТРАТЕГИЙ КОГНИТИВНОЙ ДЕЯТЕЛЬНОСТИ ПРИ РЕШЕНИИ СЕНСОМОТОРНЫХ ЗАДАЧ
Добавить комментарий