Динамическое и линейное программирование

Государственный университет управления

                         Институт заочного обучения
                         Специальность – менеджмент

                        Кафедра прикладной математики



                               КУРСОВОЙ ПРОЕКТ

                   по дисциплине: «Прикладная математика»



Выполнил студент 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]   |Показывает, что добавление одной единицы первого ресурса  |