Свойства задачи линейного программирования

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

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

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

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

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