Методы исследования операций (стр. 5 из 5)

Максимальный поток из 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
S1	B1	A11	A12	A13
S2	B2	A21	A22	A23
S3	B3	A31	A32	A33
S4	B4	A41	A42	A43
Прибыль, получаемая от единицы продукции		C1	C2	C3

Требуется:

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.