Задачи линейного программирования и методы их решения

    Федеральное государственное бюджетное 

    образовательное учреждение высшего профессионального  образования

    «НОВОСИБИРСКИЙ  ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» 
 
 

Кафедра экономической теории 
 
 
 
 
 
 

 
 

Расчетно-графическая  работа по стратегическому

планированию  на тему «Задачи линейного программирования и методы их решения» 
 
 
 

Факультет: Бизнеса

Группа: ФБЭ-84, курс 4

Выполнила: Орлова Т.В. 
 
 
 
 
 

Новосибирск

2012 г. 

Задачи  линейного программирования  и методы их решения.

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

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

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

Общей задачей  линейного программирования называют задачу 
               при ограничениях 
                       
                           
                            
                                   
      - произвольные                    
     где   - заданные действительные числа; Z – целевая функция  - план задачи.

       Пусть задача линейного программирования представлена в виде следующей записи: 

                                                          
                                         
                                             
     Чтобы задача имела решение, системе её ограничений должна быть совместной. Это возможно, если  r этой системы не больше числа неизвестных n. Случай r>n  невозможен. При r=n система имеет единственное решение, которое будет при  оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов  содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более  . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базиснымии обозначают БП. Остальные n – r переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов  . Этому базису соответствуют базисные переменные  , а свободными будут переменные  .

       Если  свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы называют опорным решением (планом).

       Теорема. Если система векторов   содержит m линейно независимых векторов  , то допустимый план  
       

является крайней  точкой многогранника планов.

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

       Методы  решения задач линейного программирования

       Графический способ решения ЗЛП

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

       Симплексный метод решение  ЗЛП    

         Общая идея симплексного метода (метода последовательного улучшения  плана) для решения задач линейного программирования:

1. умение находить начальный опорный план;
2. наличие признака оптимальности опорного плана;
3. умение переходить к наилучшему опорному плану.

 

Решение задач линейного планирования

  Задача 2. Для изготовления двух видов продукции «А» и «Б» предприятие расходует ограниченные ресурсы в количествах, приведенных в следующей таблице.

Вид ресурса	Норма расхода  на одно изделие		Объем ресурса
	«А»	«Б»
Сырье, кг	5	4	178
Оборудование,  ст/ч	4	9	299
Трудоресурсы, чел/ч	9	9	379
Цена, руб.	61	101

 

  Решение задачи.

  Целевая  функция:  Q(x) = 61x₁ + 101x₂ →max

   Составим систему ограничений:

  5x₁ + 4x₂ ≤ 178                                           

  4x₁ + 9x₂ ≤ 299                                          

  9x₁ + 9x₂ ≤ 379                                            

  При этом выполняется условие: x₁ ≥ 0, x₂ ≥ 0

  Решим задачу с помощью программы ПЭР.

  Введем  данные задачи:

  

  Получим следующий результат:

  

  

  

  x = (14,27);  Q (14,27) = 3581 – оптимум целевой функции

  Ответ: оптимальное решение задачи –  производство 14 единиц изделия «А»  и 27 единиц изделия «Б», при этом выручка предприятия составит 3581 руб. 

  Задача 4. Для изготовления двух видов продукции «А» и «Б» предприятие расходует ограниченные ресурсы в количествах, приведенных в следующей таблице. 

Вид ресурса	Норма расхода  на одно изделие		Объем ресурса
	«А»	«Б»
Сырье, кг	5	4	150
Оборудование, ст/ч	4	2	96
Трудоресурсы, чел/ч	2	9	218
Цена, руб.	33	24

 

  Решение задачи.

  Целевая  функция:  Q(x) = 33x₁ + 24x₂ →max

   Составим систему ограничений:

  5x₁ + 4x₂ ≤ 150                                           

  4x₁ + 2x₂ ≤ 96                                          

  2x₁ + 9x₂ ≤ 218                                            

  При этом выполняется условие: x₁ ≥ 0, x₂ ≥ 0

  Решим задачу с помощью программы ПЭР.

  Введем  данные задачи: 
 
 

  Получим следующий результат:

  x = (14,20);  Q (14,20) = 942 – оптимум целевой функции

  Ответ: оптимальное решение задачи –  производство 14 единиц изделия «А»  и 20 единиц изделия «Б», при этом выручка предприятия составит 942 руб. 
 

 

  Список  используемых источников

1.Лопатников, Л.И. Словарь современной экономической науки / Л.И. Лопатников // Экономико-математический словарь. - М.: Финансы и статистика, 2009. – С. 43

2.Карманов, В.Г. Математическое программирование: Учебник для вузов. - М.: Наука, 2007. - С.16-18.

3.Красс, М.С. Математика для экономистов: Учебник для экономических вузов. - Санкт-Петербург: Питер, 2006. - С.289.

4.Холод, Н.И. Математические методы анализа и планирования: Учебник для вузов. - М: МЭТ, 2009. - С.97.

5.Холод, Н.И. Пособие по решению задач по линейной алгебре и линейному программированию: Пособие для вузов. - М: МЭТ, 2007. - С.159.