|
Курсовая: Динамическое и линейное программирование |
Курсовая: Динамическое и линейное программирование
Государственный университет управления
Институт заочного обучения
Специальность – менеджмент
Кафедра прикладной математики
КУРСОВОЙ ПРОЕКТ
по дисциплине: «Прикладная математика»
Выполнил студент 1-го курса
Группа № УП4-1-98/2
Студенческий билет №
Москва, 1999 г.
Содержание
1. Линейная производственная задача____________________________________________3
2. Двойственная задача_________________________________________________________7
3. Задача о «Расшивке узких мест производства»_________________________________9
4. Транспортная задача________________________________________________________12
5. Распределение капитальных вложений_________________________________________17
6. Динамическая задача управления запасами____________________________________21
7. Анализ доходности и риска финансовых операций______________________________26
8. Оптимальный портфель ценных бумаг__________________________________________28
1. Линейная производственная задача
Линейная производственная задача – это задача о рациональном использовании
имеющихся ресурсов, для решения которой применяют методы линейного
программирования. В общем виде задача может быть сформулирована следующим
образом:
Предположим, предприятие или цех может выпускать
видов продукции, используя
видов ресурсов. При этом известно количество каждого вида ресурса, расход
каждого вида ресурса на выпуск каждого вида продукции, прибыль, получаемая с
единицы выпущенной продукции. Требуется составить такой план производства
продукции, при котором прибыль, получаемая предприятием, была бы наибольшей.
Примем следующие обозначения:
| Номер ресурса (i=1,2,.,m) | | Номер продукции (j=1,2,.,n) | | Расход i-го ресурса на единицу j-ой продукции | | Имеющееся количество i-го ресурса | | Прибыль на единицу j-ой продукции | | Планируемое количество единиц j-ой продукции | | Искомый план производства | | | |
Таким образом, математическая модель задачи состоит в том, чтобы найти
производственную программу
максимизирующую прибыль:
При этом, какова бы ни была производственная программа
, ее компоненты должны удовлетворять условию, что суммарное использование
данного вида ресурса, при производстве всех видов продукции не должно превышать
имеющееся количество данного вида ресурса, т.е.
, где
А так как компоненты программы – количество изделий, то они не могут быть
выражены отрицательными числами, следовательно добавляется еще одно условие:
, где
Предположим, что предприятие может выпускать четыре вида продукции (
), используя для этого три вида ресурсов (
). Известна технологическая матрица
затрат любого ресурса на единицу каждой продукции, вектор
объемов ресурсов и вектор
удельной прибыли:
Тогда математическая модель задачи будет иметь вид:
Найти производственную программу максимизирующую прибыль:
| (1.1) |
при ограничениях по ресурсам:
| (1.2) |
где по смыслу задачи: , , ,
Таким образом, получили задачу на нахождение условного экстремума. Для ее
решения введем дополнительные неотрицательные неизвестные:
Тогда вместо системы неравенств (1.2), получим систему линейных
алгебраических уравнений:
| (1.3) |
где среди всех решений, удовлетворяющих условию неотрицательности:
, , , , , ,
надо найти решение, при котором функция (1.1) примет наибольшее значение. Эту
задачу будем решать методом последовательного улучшения плана – симплексным
методом.
Воспользуемся тем, что правые части всех уравнений системы (1.3) неотрицательны,
а сама система имеет предпочитаемый вид – дополнительные переменные являются
базисными. Приравняв к нулю свободные переменные x1, x2,
x3, x4, получаем базисное неотрицательное решение:
, , , , , ,
первые четыре компоненты которого представляют производственную программу
, по которой пока ничего не производится.
Из выражения (1.1) видно, что наиболее выгодно начинать производить продукцию
третьего вида, т.к. прибыль на единицу выпущенной продукции здесь наибольшая,
поэтому в системе (1.3) принимаем переменную x3 за разрешающую и
преобразуем эту систему к другому предпочитаемому виду. Для чего составляем
отношения правых частей уравнений к соответствующим положительным коэффициентам
при выбранной неизвестной и находим наибольшее значение x3, которое
она может принять при нулевых значениях других свободных неизвестных, сохранив
правые части уравнений неотрицательными, т.е.
Оно соответствует первому уравнению в системе (1.3), и показывает какое
количество изделий третьего вида предприятие может изготовить с учетом объемов
сырья первого вида. Следовательно, в базис вводим неизвестную x3, а
исключаем от туда неизвестную x5. Тогда принимаем первое уравнение в
системе (1.3) за разрешающее, а разрешающим элементом будет a13=6.
Применив формулы исключения, переходим к новому предпочитаемому виду системы
с соответствующим базисным допустимым решением.
Полный процесс решения приведен в таблице 1, где в последней строке третьей
таблицы нет ни одного отрицательного относительного оценочного коэффициента
, где , где ,
т.е. выполняется критерий оптимальности для максимизируемой функции (1.1).
Таблица 1 | | | C | Базис | H | 30 | 11 | 45 | 6 | 0 | 0 | 0 | Пояснения | | | | | | | | | | 0 | | 150 | 3 | 2 | 6 | 0 | 1 | 0 | 0 | x3 – разрешающая переменная x3 ® в базис. первая строка – разрешающая x5 ® из базиса. разрешающий элемент = 6 | | 0 | | 130 | 4 | 2 | 3 | 5 | 0 | 1 | 0 | | 0 | | 124 | 4 | 3 | 2 | 4 | 0 | 0 | 1 | | | 0 | | -30 | -11 | -45 | -6 | 0 | 0 | 0 | | 45 | | 25 | | | 1 | 0 | | 0 | 0 | x1 – разрешающая переменная вторая строка – разрешающая разрешающий элемент = | | 0 | | 55 | | 1 | 0 | 5 | | 1 | 0 | | 0 | | 74 | 3 | | 0 | 4 | | 0 | 1 | | | 1125 | | | 4 | 0 | -6 | | 0 | 0 | | 45 | | 14 | 0 | | 1 | -1 | | | 0 | Все | | 30 | | 22 | 1 | | 0 | 2 | | | 0 | | 0 | | 8 | 0 | | 0 | -2 | | | 1 | | | 1290 | | 0 | 7 | 0 | 9 | 6 | 3 | 0 | | | | | | | | | | | | | |
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|