Линейное программирование

Математические методы в экономике ...

1. Линейное программирование

Еще в 1938 г. Л.В. Канторович разработал метод распределения ресурсов, (известный сегодня как метод линейного программирования Канторовича), произвел максимизацию линейной функции, с учетом большого количества ограничений. Он знал, что максимизация при многочисленных ограничениях – это одна из основных экономических проблем и что его метод может быть использован во многих производствах, например, определение оптимального использования посевных площадей, наиболее эффективного распределения потоков транспорта и т. д.

6
21401
 группа
9
6
7
8
39203
Нижняя граница
(Nj)
-
100
-
-
Верхняя граница
(Nj)
5000
-
-
500
-
Прибыль
(на
единицу продукции и общая)
160
120
180
200
 500 000
В данной таблице видим, что предприятие обладает ресурсами, которые обозначим (i); выпускает продукцию, обозначим ее (j); которая подразделяется на четыре вида изделия А; В; С; D, которые мы обозначим (х1; х2; х3; х4). Запас ресурса обозначим (b i), удельный расход ресурса обозначим (a i.). Ограничим объем выпуска предельными значениями: (Nj) – минимальное; (Nj) – максимальное.
(Nj)  xj  (Nj), где
xj (j  1: n) – это количество выпускаемого j-го вида продукции
1.2. Оптимизация плана производства с учетом ограничений и граничных условий.
С учетом ограничений требуемый ресурс (нормы работыоборудования) не может превышать располагаемый, значит, система ограничений будет выглядеть так:
(1)
Если добавить предельно-допустимое значения выпуска каждого вида продукции, то получим систему:
(2)
В этой системе неравенства, устанавливающие зависимости для ресурсов – ограничения, а предельно-допустимые значения переменных – граничные условия. В ограничениях левые части неравенства – потребляемые ресурсы, а правые – располагаемые.
Прежде, чем решать задачу, необходимо исходные неравенства преобразить в уравнения. Для этого добавим к левой части каждого ограничения (потребляемым ресурсам) дополнительные переменные: y1  0; y2  0; y3  0 и получим три уравнения исходных данных задачи:
(3)

По экономическому содержанию дополнительные переменные обозначают резервы каждого вида ресурсов , то есть не используемое в плане время работы оборудования соответствующей группы.
В задаче суммарное количество основных переменных (xj ) и дополнительных переменных (yi) больше числа уравнений, поэтому система (3) имеет бесчисленное множество решений. Чтобы выбрать единственно правильное решение, необходимо сформулировать задачу оптимизации.
Цель решения задачи распределения ресурсов задается в двух взаимоисключающих постановках:
1) при заданных ресурсах максимизировать полученный результат;
2) при заданном результате минимизировать потребляемые ресурсы.
Задачи оптимизации выглядят так:
а) для первой постановки:
(4)
(5)

(6)
где Сj - величина показывающая какой вклад в результат дает единица продукции j-го вида