|
|
|
|
Математика>>Динамическое и линейное программирование 
Государственный университет управления
Институт заочного обучения
Специальность – менеджмент
Кафедра прикладной математики
КУРСОВОЙ ПРОЕКТ
по дисциплине: «Прикладная математика»
Выполнил студент 1-го курса
Группа № УП4-1-98/2
Студенческий билет №
Москва, 1999 г.
Содержание
1. Линейная производственная задача 3
2. Двойственная задача 7
3. Задача о «Расшивке узких мест производства» 9
4. Транспортная задача 12
5. Распределение капитальных вложений 17
6. Динамическая задача управления запасами 21
7. Анализ доходности и риска финансовых операций 26
8. Оптимальный портфель ценных бумаг 28
1. Линейная производственная задача
Линейная производственная задача – это задача о рациональном
использовании имеющихся ресурсов, для решения которой применяют методы
линейного программирования. В общем виде задача может быть сформулирована
следующим образом:
Предположим, предприятие или цех может выпускать [pic] видов продукции,
используя [pic] видов ресурсов. При этом известно количество каждого вида
ресурса, расход каждого вида ресурса на выпуск каждого вида продукции,
прибыль, получаемая с единицы выпущенной продукции. Требуется составить
такой план производства продукции, при котором прибыль, получаемая
предприятием, была бы наибольшей.
Примем следующие обозначения:
|[pic]|Номер ресурса (i=1,2,…,m) |
|[pic]|Номер продукции (j=1,2,…,n) |
|[pic]|Расход i-го ресурса на единицу j-ой продукции |
|[pic]|Имеющееся количество i-го ресурса |
|[pic]|Прибыль на единицу j-ой продукции |
|[pic]|Планируемое количество единиц j-ой продукции |
|[pic] |Искомый план производства |
Таким образом, математическая модель задачи состоит в том, чтобы найти
производственную программу [pic] максимизирующую прибыль:
[pic]
При этом, какова бы ни была производственная программа [pic], ее
компоненты должны удовлетворять условию, что суммарное использование
данного вида ресурса, при производстве всех видов продукции не должно
превышать имеющееся количество данного вида ресурса, т.е.
[pic], где [pic]
А так как компоненты программы – количество изделий, то они не могут
быть выражены отрицательными числами, следовательно добавляется еще одно
условие:
[pic], где [pic]
Предположим, что предприятие может выпускать четыре вида продукции
([pic]), используя для этого три вида ресурсов ([pic]). Известна
технологическая матрица [pic] затрат любого ресурса на единицу каждой
продукции, вектор [pic] объемов ресурсов и вектор [pic] удельной прибыли:
[pic] [pic] [pic]
Тогда математическая модель задачи будет иметь вид:
Найти производственную программу [pic] максимизирующую прибыль:
|[pic] |(1.1) |
при ограничениях по ресурсам:
|[pic] |(1.2) |
где по смыслу задачи: [pic], [pic], [pic], [pic]
Таким образом, получили задачу на нахождение условного экстремума. Для ее
решения введем дополнительные неотрицательные неизвестные:
|[pic], |остаток ресурса определенного вида |
|[pic], |(неиспользуемое количество каждого |
|[pic] |ресурса) |
Тогда вместо системы неравенств (1.2), получим систему линейных
алгебраических уравнений:
|[pic] |(1.3) |
где среди всех решений, удовлетворяющих условию неотрицательности:
[pic], [pic], [pic], [pic], [pic], [pic], [pic]
надо найти решение, при котором функция (1.1) примет наибольшее значение.
Эту задачу будем решать методом последовательного улучшения плана –
симплексным методом.
Воспользуемся тем, что правые части всех уравнений системы (1.3)
неотрицательны, а сама система имеет предпочитаемый вид – дополнительные
переменные являются базисными. Приравняв к нулю свободные переменные x1,
x2, x3, x4, получаем базисное неотрицательное решение:
[pic], [pic], [pic], [pic], [pic], [pic], [pic]
первые четыре компоненты которого представляют производственную программу
[pic], по которой пока ничего не производится.
Из выражения (1.1) видно, что наиболее выгодно начинать производить
продукцию третьего вида, т.к. прибыль на единицу выпущенной продукции здесь
наибольшая, поэтому в системе (1.3) принимаем переменную x3 за разрешающую
и преобразуем эту систему к другому предпочитаемому виду. Для чего
составляем отношения правых частей уравнений к соответствующим
положительным коэффициентам при выбранной неизвестной и находим наибольшее
значение x3, которое она может принять при нулевых значениях других
свободных неизвестных, сохранив правые части уравнений неотрицательными,
т.е.
[pic]
Оно соответствует первому уравнению в системе (1.3), и показывает какое
количество изделий третьего вида предприятие может изготовить с учетом
объемов сырья первого вида. Следовательно, в базис вводим неизвестную x3, а
исключаем от туда неизвестную x5. Тогда принимаем первое уравнение в
системе (1.3) за разрешающее, а разрешающим элементом будет a13=6.
Применив формулы исключения, переходим к новому предпочитаемому виду
системы с соответствующим базисным допустимым решением.
Полный процесс решения приведен в таблице 1, где в последней строке
третьей таблицы нет ни одного отрицательного относительного оценочного
коэффициента
[pic], где [pic], где [pic],
т.е. выполняется критерий оптимальности для максимизируемой функции (1.1).
|Таблица 1 |
|C |Бази|H |30 |11 |45 |6 |0 |0 |0 |Пояснения |
| |с | | | | | | | | | |
| | | |[pic| |[pic|[pic|[pic|[pic|[pic| |
| | | |] | |] |] |] |] |] | |
|0 |[pic|15|3 |2 |6 |0 |1 |0 |0 |[pic] |
| |] |0 | | | | | | | |x3 – разрешающая|
| | | | | | | | | | |переменная |
| | | | | | | | | | |x3 ( в базис. |
| | | | | | | | | | |[pic] |
| | | | | | | | | | |первая строка – |
| | | | | | | | | | |разрешающая |
| | | | | | | | | | |x5 ( из базиса. |
| | | | | | | | | | |разрешающий |
| | | | | | | | | | |элемент = 6 |
|0 |[pic|13|4 |2 |3 |5 |0 |1 |0 | |
| |] |0 | | | | | | | | |
|0 |[pic|12|4 |3 |2 |4 |0 |0 |1 | |
| |] |4 | | | | | | | | |
| |0 | |-30 |-11 |-45 |-6 |0 |0 |0 | |
|45|[pic|25|[pic|[pic|1 |0 |[pic|0 |0 |[pic] |
| |] | |] |] | | |] | | |x1 – разрешающая|
| | | | | | | | | | |переменная |
| | | | | | | | | | |[pic] |
| | | | | | | | | | |вторая строка – |
| | | | | | | | | | |разрешающая |
| | | | | | | | | | |разрешающий |
| | | | | | | | | | |элемент = [pic] |
|0 |[pic|55|[pic|1 |0 |5 |[pic|1 |0 | |
| |] | |] | | | |] | | | |
|0 |[pic|74|3 |[pic|0 |4 |[pic|0 |1 | |
| |] | | |] | | |] | | | |
| |1125| |[pic|4 |0 |-6 |[pic|0 |0 | |
| | | |] | | | |] | | | |
|45|[pic|14|0 |[pic|1 |-1 |[pic|[pic|0 |Все [pic] |
| |] | | |] | | |] |] | | |
|30|[pic|22|1 |[pic|0 |2 |[pic|[pic|0 | |
| |] | | |] | | |] |] | | |
|0 |[pic|8 |0 |[pic|0 |-2 |[pic|[pic|1 | |
| |] | | |] | | |] |] | | |
| |1290| |0 |7 |0 |9 |6 |3 |0 | |
При этом каждый элемент симплексной таблицы имеет определенный
экономический смысл. Например, во второй симплексной таблице:
|В столбце [pic]: |
|[pic] |Показывает, на сколько следует уменьшить |
| |изготовление изделия третьего вида, если |
| |запланирован выпуск одного изделия первого |
| |вида. |
|[pic]; 3 |Показывают, сколько потребуется сырья второго и|
| |третьего вида, при включении в план одного |
| |изделия первого вида. |
|Т.е. при включении в план одного изделия первого вида, потребуется |
|уменьшение выпуска продукции третьего вида на 0.5 единиц, а также |
|потребуются дополнительные затраты 2.5 единиц сырья второго вида и 3|
|единицы сырья третьего вида, что приведет к увеличению прибыли |
|предприятия на 7.5 денежных единиц. |
|В столбце [pic]: |
|[pic];[pic];[pic] |Показывают, что увеличение объема сырья первого |
| |вида на единицу позволило бы увеличить выпуск |
| |продукции третьего вида на[pic]. |
| |[pic] |
| |что одновременно потребовало бы [pic] единицы |
| |сырья второго вида и [pic] единицы сырья |
| |третьего вида. |
Т.к. в последней строке третьей таблицы 1 нет ни одного отрицательного
относительного оценочного коэффициента, то производственная программа, при
которой получаемая предприятием прибыль имеет наибольшее значение, найдена,
т.к., например, коэффициент [pic] при переменной [pic] показывает, что если
произвести одну единицу продукции второго вида, то прибыль уменьшится на
7 денежных единиц.
Таким образом, получили производственную программу:
[pic], [pic], [pic], [pic]
которая является оптимальной и обеспечивает предприятию наибольшую
возможную прибыль:
[pic]
При этом первый и второй ресурсы будут использованы полностью, т.е.
первый и второй ресурсы образуют «узкие места производства»:
[pic], [pic]
а третий ресурс будет иметь остаток:
[pic]
Помимо этого в третьей симплексной таблице получен обращенный базис,
отвечающий оптимальной производственной программе:
[pic]
тогда можно проверить выполнение соотношения [pic]:
[pic]
а т.к. из третьей симплексной таблицы:
[pic], следовательно, соотношение [pic] выполняется.
2. Двойственная задача
Задача, двойственная линейной производственной задаче, например, может
заключаться в оценке выгоды от продажи сырья, используемого в производстве,
на сторону.
Например, в предыдущем п.1. рассмотрена линейная производственная задача
по выпуску четырех видов продукции с использованием трех видов ресурсов по
заданным технологиям. Предположим, некий предприниматель, занимающийся
производством других видов продукции с использованием трех таких же видов
ресурсов, предлагает «уступить» ему все имеющиеся ресурсы и обещает платить
y1 денежных единиц за каждую единицу первого ресурса, y2 денежных единиц за
каждую единицу второго ресурса и y3 денежных единиц за каждую единицу
третьего ресурса. Возникает вопрос: при каких значениях y1, y2, y3 можно
согласиться с предложением этого предпринимателя.
Т.к. в предыдущей задаче технологическая матрица [pic] затрат любого
ресурса на единицу каждой продукции, вектор [pic] объемов ресурсов и вектор
[pic] удельной прибыли имели вид:
[pic] [pic] [pic]
значит, для производства, например, первого вида продукции, предприятие
должно затратить 3 единицы ресурса первого вида, 4 единицы ресурса второго
вида и 4 единицы ресурса третьего вида, за что оно получит прибыль
30 денежных единиц. Следовательно, согласиться с предложением
предпринимателя можно, если он заплатит не меньше, т.е. в ценах y1, y2, y3
это условие будет иметь вид:
[pic]
Аналогично и с продукцией второго, третьего и четвертого вида, при этом,
за все имеющиеся ресурсы, предприниматель должен заплатить не меньше:
[pic] денежных единиц.
Следовательно, предприниматель будет искать такие значения y1, y2, y3,
при которых эта сумма была бы как можно меньше. При этом речь идет о ценах,
которые зависят не от цен по которым эти ресурсы были когда-то приобретены,
а о ценах зависящих от применяемых в производстве технологий, объемов
ресурсов и прибыли, которую возможно получить за произведенную продукцию.
Таким образом, задача определения расчетных оценок ресурсов приводит к
задаче линейного программирования: найти вектор двойственных оценок
[pic]
минимизирующий общую оценку всех ресурсов
[pic]
при условии, что по каждому виду продукции суммарная оценка всех ресурсов,
затрачиваемых на производство единицы продукции, не меньше прибыли,
получаемой от реализации единицы этой продукции, т.е.:
[pic]
причем оценки ресурсов не могут быть отрицательными, т.е.: [pic], [pic],
[pic]
Решение полученной задачи можно найти с помощью второй теоремы
двойственности: дефицитный (избыточный) ресурс, полностью (неполностью)
используемый по оптимальному плану производства, имеет положительную
(нулевую) оценку, и технология, применяемая с ненулевой (нулевой)
интенсивностью, имеет нулевую (положительную) оценку.
Т.е. для оптимальных решений [pic] и [pic] пары двойственных задач
необходимо и достаточно выполнение условий:
[pic] [pic]
Ранее в п.1. было найдено, что [pic], [pic], а [pic] и [pic], тогда:
[pic]
Но т.к. третий ресурс был избыточным (см. п.1.), то по второй теореме
двойственности, его двойственная оценка равна нулю, т.е. [pic]. Тогда
переходим к новой системе уравнений:
[pic]
от куда получаем: [pic], [pic]
Таким образом, получили двойственные оценки ресурсов:
[pic], [pic], [pic]
тогда общая оценка всех ресурсов равна:
[pic]
То же самое решение значений двойственных оценок содержится в последней
строке симплексной таблицы 1 и имеет определенный экономический смысл:
|[pic] |Показывает, что добавление одной единицы первого ресурса |
|
|
