Заменить текущую cij-матрицу на вновь полученную и перейти к шагу 1.

⇐ ПредыдущаяСтр 7 из 7

Операция (а) дает возможность использовать остатки пропускных способностей дуг выбранной цепи в направлении s®t. Операция (б) восстанавливает исходные пропускные способности сети, поскольку уменьшение пропускной способности дуги в одном направлении можно рассматривать как увеличение ее пропускной способности в противоположном направлении.

Шаг 3. Найти максимальный поток в сети. Пусть C = ç ç cijç ç - исходная матрица пропускных способностей, и пусть C* = ç ç cijç ç - последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2). Оптимальный поток X = ç ç xijç ç в дугах задается как

Максимальный поток из s в t равен

При этом z есть сумма всех положительных q, определенных на шаге 2. Таким образом, можно объяснить, почему используются положительные элементы матрицы C – C* для определения результирующего потока в направлении s® t.

Литература

1. Протосеня А.Г., Кулиш С.А., Азбель Е.И. и др. Математические методы планировании и управлении горным производством. Учебное пособие для вузов. - М.: Наука, 1985.

2. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. -М.: Мир, 1984.

3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985.

4. Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991.

5. Попов Ю.Д. Линейное и нелинейное программирование. Учебное пособие. - Киев, 1988.

6. Зайченко Ю.П. Исследование операций. Учебное пособие для студентов вузов. - Киев: Вища школа. Головное издательство, 1979

7. Таха Х.. Введение в исследование операций: в 2-х книгах. - М.: Мир, 1985.

8. Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1997.

9. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

10. Данко. Высшая математика в примерах и задачах.

Контрольная работа.

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

Задание 1

Для изготовления трех видов продукции Р1, Р2 и Р3 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, количество каждого ресурса, затрачиваемое на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице.

Вид ресурса

Запас ресурса

Число единиц ресурса, затрачиваемых на изготовление единицы продукции

Р1

Р2

Р3

A11

A12

A13

A21

A22

A23

A31

A32

A33

A41

A42

A43

Прибыль, получаемая от единицы продукции

Требуется:

a) составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной;

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

1) Построить математическую модель, с подробным описанием переменных, ограничений и целевой функции.

2) Привести задачу к стандартному виду.

3) Определить начальный допустимый план.

4) Заполнить начальную симплекс-таблицу.

5) Найти оптимальный план производства симплекс-методом. (Допускается использование ПЭВМ). Решение оформить в виде симплекс-таблиц.

6) По оптимальной симплекс-таблице определить: ограничено ли пространство допустимых решений; единственно ли оптимальное решение задачи; есть ли у задачи вырожденные решения. Все ответы объяснить и обосновать.

7) Определить, какие из ресурсов являются дефицитными. Почему?

8) Определить на сколько можно увеличить запас дефицитных ресурсов, для улучшения полученного оптимального значения целевой функции.

9) Определить, на сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции.

10) Определить увеличение запаса какого из ресурсов наиболее выгодно.

11) Определить, в каких пределах допустимо изменение коэффициентов целевой функции.

Задание 2.

Для задачи, полученной в первом задании построить двойственную. Дать экономическую интерпретацию двойственной задачи. Решить двойственную задачу. Используя соотношения двойственности, получить оптимальное решение прямой задачи.

Задание 3.

К математической модели, полученной в задании 1 добавить условие целочисленности для всех переменных. Решить новую задачу методом отсечений.

Задание 4.

Решить транспортную задачу.

Задание 5.

Для каждой дуги (i, j) неориентированной сети указана ее длина. Построить минимальное дерево-остов.

Задание 6.

Для каждой дуги (i, j) неориентированной сети указана ее длина. Найти кратчайший маршрут из узла 1 в узел 13.

Задание 7.

Для каждой дуги (i, j) сети указана ее пропускная способность. Найти максимальный поток из источника s в сток t.

⇐ Предыдущая 1 2 3 4 5 67