Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

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

едприятием прибыль имеет наибольшее значение,  найдена,
т.к., например, коэффициент [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]   |Показывает, что добавление одной единицы первого ресурса  |
|        |обеспечит прирост прибыли в 6 денежных единиц.            |
|[pic]   |Показывает, что добавление одной единицы второго ресурса  |
|        |обеспечит прирост прибыли в 3 денежные единицы.           |


Одновременно технологические оценки из той же строки симплексной таблицы:
|[pic]   |Показывает, что если произвести одну единицу продукции    |
|        |второго вида (не входящую в оптимальную производственную  |
|        |программу), то это уменьшит прибыль на 7 денежных единиц  |
|[pic]   |Показывает, что если увеличить выпуск продукции четвертого|
|        |вида на одну единицу, то это уменьшит прибыль на          |
|        |9 денежных единиц                                         |


3. Задача о «Расшивке узких мест производства»

  Задача о «расшивке узких  мест  производства»  заключается  в  том,  что,
например, когда в процессе производства происходит изменение объема  какого-
либо ресурса, используемого в производстве,  то,  соответственно  изменяется
план производства и прибыль предприятия, получаемая  от  реализации  готовой
продукции. Это может происходить по различным причинам,  например:  сломался
станок, поставщик предлагает сырье в большем количестве и т.п.
  Поэтому, когда какой-либо ресурс используется  полностью,  то  уменьшение
объема этого ресурса, может повлиять на всю структуру плана  производства  и
прибыль предприятия. Следовательно, такой ресурс,  образующий  «узкие  места
производства»,  желательно  иметь  с  некоторым  запасом,  т.е.   заказывать
дополнительно, чтобы  сохранить  структуру  плана  производства  и  получить
возможность увеличить прибыль предприятия.
  Для примера возьмем данные и результаты вычислений из п.1.  и  п.2.,  где
определено,  что  первый  и  второй  ресурс   используются   полностью,   и,
соответственно,  именно  их  нужно  заказывать  дополнительно.  Но  в  таких
объемах, чтобы сохранить структуру ранее найденной  программы  производства,
и с условием, что от поставщика можно получить дополнительно не более  одной
трети первоначально выделенного объема ресурса любого  вида.  Следовательно,
задача сводиться к нахождению объемов приобретения дополнительных  ресурсов,
удовлетворяющих указанным условиям, и  вычислению  дополнительной  возможной
прибыли.

  Тогда, пусть [pic] – вектор дополнительных объемов ресурсов:
                                    [pic]
при  этом,  для  сохранения  структуры  производственной  программы,  должно
выполняться условие устойчивости двойственных оценок:
                                    [pic]

  Т.к. [pic], то задача состоит в том, чтобы найти вектор:
                                    [pic]
максимизирующий суммарный прирост прибыли:
|[pic]                                  |(3.1)                      |


при условии сохранения структуры производственной программы:
|[pic]                                           |(3.2)             |
предполагая, что можно  надеяться  получить  дополнительно  не  более  одной
трети первоначального объема ресурса каждого вида, т.е.:
|[pic]                                   |(3.3)                     |


причем дополнительные объемы ресурсов,  по  смыслу  задачи,  не  могут  быть
отрицательными, т.е.:
|[pic], [pic]                           |(3.4)                      |


  Т.к. неравенства (3.2) и (3.3) должны  выполняться  одновременно,  то  их
можно переписать в виде одной системы неравенств:

|(                      |[pic]                |(3.5)                |
|(                      |                     |                     |
|(                      |                     |                     |
|(                      |                     |                     |
|(                      |                     |                     |


  Таким   образом,    получена    задача    линейного    программирования:
максимизировать функцию (3.1) при условиях (3.4) и (3.5).
  Эту задачу с двумя переменными можно решить графически:
                                                                   График 1.
  На графике видно, что система линейных неравенств (3.4), (3.5),  образует
область допустимых решений, ограниченную прямыми:
                         [pic], [pic], [pic], [pic]

при этом линии уровня функции (3.1) перпендикулярны вектору-градиенту  [pic]
и образуют семейство параллельных  прямых  (градиент  указывает  направление
возрастания функции). Наибольшего значения функция (3.1) достигает  в  точке
[pic]пересечения прямых:
                                [pic] и [pic]
  Координаты  этой  точки  и  определяют  искомые   объемы   дополнительных
ресурсов. Следовательно, программа «расшивки узких мест  производства  имеет
вид:
                             [pic], [pic],
12345След.
скачать работу

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

 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ