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

Особенностью  задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.

Формы записи задачи линейного программирования:

Общей задачей  линейного программирования называют задачу:

      max(min)Z =      (1)

при ограничениях: 

       (i=1,2….m)     (2)

        (i = m₁+1,..., m₁)  (3)

       (i = m₂+1,..., m₂)     (4)

        x_j ≤ 0          (j=1,2…..n₁)      (5)

        x_j -произвольные (j= n₁+1,…..n)    (6) 

где с_j,а_ij,b_i;- заданные действительные числа;

(1) - целевая  функция;

(2) - (6) -ограничения;

х = (х,;...;х_n) –план задачи. 

Свойства  решений.

Пусть ЗЛП представлена в следующей записи:

      mах Z = сх       (7)

      А₁х₁,+А₂х₂+... + А_nх_n=А₀                 (8)

      х₁ ≥ 0, х₂ ≥ 0,…….х_n ≥ 0                (9)

Чтобы задача (7) - (8) имела решение, системе  её ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при х_j ≥ 0 (j=1,...,n) оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n, в этом случае система векторов А₁,А₂,...,А_n содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, может быть несколько, но не более с . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n — r переменных будут свободными, их обозначают СП. Будем считать, что базис составляют первые m векторов А₁,А₂,...,А_m. Этому базису соответствуют базисные переменные х₁,х₂,...,х_m, а свободными будут переменные х_m+1,х_m+2,….х_n.

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

Задача 

Зависимость доходов фирмы  R и издержек  I в зависимости от объёма производства x задётся функциями следующего вида: R(x)=2/3x³ – 18x² – 17x ; C(x)=1/3x³ – 10x² +150. производственные мощности позволяют производить до 30 единиц продукции. При каком объёме производства прибыль максимальна? 

Решение 

R(x) = 2/3x³ – 18x² – 17x

C(x) = 1/3x³ – 10x² +150

P(x) = R(x) – C(x)

P(x) =2/3x³ – 18x² – 17x – 1/3x³ + 10x² –150

P(x) =1/3x³ – 8x² – 17x –150

Решая кубическое уравнение по теореме Кордано  получаем 3 значения х.

x₁=27

x₂= 3

x₃= – 5 (не имеет экономической силы) 

Ответ: 27 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Список  использованной литературы

1. Замков О.О., Толстопятенко А.В, Математические методы в 
   экономике, Дело и сервис, 2001

2. Коршунова Н.И., Плясунов В.С. Математическая экономика. М.: Вита- 
   Пресс, 1996

3. Пинегина М.В. Математические методы и модели в экономике. М.: 
   Издательство «Экзамен» 2002

4. Бережков Л.Н. Теория оптимального управления экономическими 
   системами. СПб.:«Знание», 2002