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