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

СОДЕРЖАНИЕ 
 

       1. Введение

2. Постановка задачи

3  Математическая модель

4. Графическое решение задачи

5. Исследование на чувствительность

6. Решение задачи Симплекс  методом

7. Исследование на чувствительность Симплекс метода

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. ВВЕДЕНИЕ

 

     1.1 Что же такое линейное программирование? Это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. 
       Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

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

     Линейное  программирование представляет собой  наиболее часто используемый метод  оптимизации. К числу задач линейного программирования можно отнести задачи:

• рационального использования сырья и материалов; задачи оптимизации раскроя;
• оптимизации производственной программы предприятий;
• оптимального размещения и концентрации производства;
• составления оптимального плана перевозок, работы транспорта;
• управления производственными запасами;
• и многие другие, принадлежащие сфере оптимального планирования.

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

     Первые  постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

     В настоящее время линейное программирование является одним из наиболее употребительных  аппаратов математической теории оптимального принятия решения.

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

      Цель  расчетного задания – на практическом примере продемонстрировать решение задачи  линейного программирования. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2 ПОСТАНОВКА ЗАДАЧИ 

      Цель  расчетного задания – на практическом примере продемонстрировать решение задачи  линейного программирования. 

     Холдинг «ВанХельсингСтрой» производит два вида продукции: чесночную настойку  и ладан. Для изготовления 1 л ладана требуется 1.5 л спирта и 2 л масла. Для изготовления 1 л настойки требуется 3 л спирта или 3.5 л масла. Максимальные суточные поступления товара на склады холдинга – 200 л спирта и 300 л масла. Суточный спрос (можно продать не более) на ладан- 80 л, на чесночную настойку- 60 л при оптовых ценах за 1 л настойки 2000 руб., за 1 л ладана- 3000 руб. Определить оптимальные объёмы выпуска чесночной настойки и ладана. 

   Все данные нашей задачи оформим в виде таблицы:  
 
 
 
 
 
 
 
 
 
 
 
 

Таблица 1- условие задачи 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ 

      Пусть есть p видов ресурсов и q видов товаров.

       -количество k-вещества, которое содержится в двух видах продукции: чесночной настойки и ладане, где и    . Составим матрицу: 
   

                                                   

                                                

       оптовая цена суточного спроса за один литр i-компонента

           величина, указывающая максимальное поступление k – вещества на на склад холдинга

   количество i-компонента

         Составим нашу целевую функцию: 

           

        Составим ограничения:  , где

       1.

       2.

       3.

       4.

       5.   

       6.  

       

 
 
 
 
 
 
 
 
 
 
 
 
 
 

5. РЕШЕНИЕ  СИМПЛЕКС-ТАБЛИЦЫ