Московский государственный
Горный университет
Курсовой проект по исследованию операций.
Решение задачи методами линейного,
целочисленного, нелинейного и динамического
программирования.
Выполнил студент группы
ПМ 1 97 Солодовников Д. А.
Научный руководитель: Багрова Г.И.
Москва 1999 г.
Содержание:
Цель курсовой работы . 3
Линейное программирование . 4
Решение задачи методом линейного программирования .6
Целочисленное линейное программирование . 9
Решение задачи методом целочисленного линейного программирования . 10
Нелинейное программирование .15
Решение задачи нелинейного программирования 15
Динамическое программирования . 20
Решение задачи динамического программирования .21
Графическая интерпретация решений 25
Трудоемкость и эффективность решения модели различными методами .27
О проекте . 28
Цель курсовой работы.
Решить задачу методами линейного, целочисленного, нелинейного и динамического программирования. Сопоставить трудоемкость и эффективность решения модели различными методами.
Задание:
Определить плановые задания добывающим предприятиям, если в работе находится N = 12 составов.
Цена готовой продукции 50 у.е. за тонну.
Руда, поступающая на обогатительную фабрику должна иметь содержание 29,8 29,9%.
Наименование показателя
Единицы
Измерения
Предприятия
1
2
3
Max добыча
ПИ
тыс. тонн
740
680
600
Содержание полезного компонента
%
29,1
29,8
30,8
Извлечение
%
80
75
70
Затраты на добычу, транс-портировку и переработку
у.е. /т
6
7
8
Производительность
Состава
тыс. тонн
120
110
106
Коэффициент увеличения затрат при нагрузке:
До 30% -
31 50% -
51 70% -
71 100%-
максимальной
1,8
1,7
1,6
1,4
1
1,7
1,5
1,4
1,2
1
1,9
1,7
1,6
1,3
1
В курсовом проекте введены следующие условные обозначения:
ЛП линейное программирование;
ЦЛП целочисленное линейное программирование;
ДП - динамическое программирование.
Линейное программирование.
Основная задача линейного программирования:
Найти неотрицательное решение системы ограничений (1,2) обеспечивающее максимум (минимум) целевой функции.
1) Первый канонический вид:
a11x1+a12x2++a1jxj++a1nxnb1
a21x1+a22x2++a2jxj++a2nxnb2
ai1x1 +ai2x2++aijxj ++ ainxnbi
.
am1x1+am2x2++amjxj++amnxnbn
xj0; j=1,n; i=1,m;
Z=C1x1+C2x2++Cjxj++Cnxnmax (min);
2) Второй канонический вид:
a11x1+a12x2++a1jxj++a1nxn+y1=b1
a21x1+a22x2++a2jxj++a2nxn+y2=b2
ai1x1 +ai2x2++aijxj ++ ainxn+yi=bi
.
am1x1+am2x2++amjxj++amnxn+ym=bn
xj0; j=1,n; i=1,m;
Z=C1x1+C2x2++Cjxj++Cnxnmax (min);
Чтобы решить задачу линейного программирования необходимо привести ее к каноническому виду.
Теоремы линейного програмирования:
Теорема 1. Множество допустимых решений основной задачи линейного программирования выпукло.
Теорема 2. Линейная функция задачи линейного программирования достигает своего экстремального значения в крайней точке множества решений.
При решении системы ограничений могут возникнуть следующие случаи:
1) Система ограничений несовместна, поэтому отыскать оптимальное решение невозможно (рис. 1.1)