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

Министерство  образования и науки Республики Казахстан

Экономико-технический  образовательный комплекс

Гуманитарно-технический  колледж. 
 
 
 
 
 
 
 
 
 

Курсовой  проект  

Тема: “Симплекс метод в линейном программировании” 

По  предмету: “Математическое моделирование ” 

Специальность: № 3706002 . 
 
 
 
 

Группа  № 412. 

Выполнил:_________ Велекотрав В.В.

                                      Руководитель:________ Сухоруков В.И. 
 
 
 
 
 
 
 

   

Петропавловск 2006

Содержание

1. Введение.

2. Общая задача линейного  программирования.

2.1 Формулировка задачи

2.2 Геометрическая интерпретация задачи линейного программирования.

3. Симплексный метод  линейного программирования.

3.1 Общий вид задачи, решаемой симплекс – методом

3.2 Основная идея симплекс – метода

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

4.1.Алгоритм  решения задачи  симплекс методом

4.2.Задача.

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

4.4.Оптимальный  план решения данной  задачи.

5. Заключение

6.Список литературы 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.Введение

     Использование математических методов и современных электронно-вычислительных машин в значительной мере ускорят и повышают точность экономических расчетов.

     Огромный  эффект дают электронные вычислительные машины при решение многовариантных  задач.

     Внедрение математических методов в экономические  исследования и расчеты являются первостепенной задачей. Роль этих методов особенно возрастает в связи с необходимостью практической реализации проблемы оптимального планирования.

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

     Эффективно  использование метода моделирования при изучении экономических процессов, которые недоступны прямому наблюдению.

     Моделирование – это один из методов исследования, но подчиненный строго определенным логическим требованиям. Модель должна отображать лишь существенные черты  объекта в более простом, схематизированном виде.

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

     Чтобы оптимизировать процесс управления, необходимо определить, по какому признаку будет оцениваться работа системы  управления. Такой признак называется критерием оптимальности.

2. Общая задача линейного программирования.

 

 

2.1            Формулировка задачи.  

    Дана  линейная функция 

                               Z = С₁х₁+С₂х₂+... +С_Nx_N                                                                        (1.1)  

и система  линейных ограничений 

      a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

                      a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

                      . . . . . . . . . . . . . . .

                           a_i1x₁ + a_i2x₂ + ... + a_iNХ_N = b_i                                          (1.2) 

                      . . . . . . . . . . . . . . .

      a_M1x₁ + a_M2x₂ + ... + a_MNХ_N = b_M

                        x_j   0 (j = 1, 2, ... ,n)                                                        (1.3)             

где а_ij, Ь_j и С_j - заданные постоянные величины.

    Найти такие неотрицательные значения х₁, х₂, ..., х_n, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1)минимальное значение.

    Общая задача имеет несколько форм записи.

    Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях

                         А₁х₁ + А₂x₂ + ... + А_Nx_N = А_о, X 0

    где С = (с₁, с₂, ..., с_N); Х = (х₁, х₂, ..., х_N); СХ - скалярное произведение; векторы

A₁ =   , A₂ =  ,..., A_N =  , A₀ =

состоят соответственно из коэффициентов при  неизвестных и свободных членах.

    Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀, Х 0, где С = (с₁, с₂, ..., с_N) - матрица-cтрока;

 

      А = (а_ij) - матрица системы;

Х =   - матрица-столбец, А₀ =   матрица-столбец

 

 

    Запись  с помощью знаков суммирования. Минимизировать линейную функцию Z =   С_jх_j при ограничениях   

    0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂, ..., х_N), удовлетворяющий условиям (1.2) и (1.3).               

    0пределение 2. План Х = (х₁, х₂, ..., х_N) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами  х , являются  линейно независимыми.

    Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

    0пределение 3. Опорный план называется невырожденным,  если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

    0пределение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

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

 

2.2           Геометрическая интерпретация задачи линейного программирования.

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

    Решением  графическим методом задачу линейного программирования с двумя переменными:

    f = x₁- 3x₂ ®min;  

     10x₁ + 3x₂ ≥ 30,

                                                              -x₁ + x₂ ≤ 3,

                                                               x₁ - x₂  ≤ 4,

    x₁ + x₂  ≤ 10,

                                                     x₁ ≥ 0, x₂  ≥ 0.                                         (1.4)  

    Начнем  решение задачи с построения области  ее допустимых решений. В первую очередь  отобразим в прямоугольной системе  координат условия не отрицательности переменных. В двумерном пространстве уравнению соответствует прямая, а неравенству – полуплоскость, лежащая по одну сторону от прямой. Построим прямые x₁=0; х₂=0, которые лежат на границах полуплоскостей и совпадают с осями координат. Полуплоскости х₁>0, x₂>0 лежат соответственно справа от оси Ох₂ и выше оси Ох₁. Множество точек, удовлетворяющих одновременно неравенствам х₁>=0 и x₂>=0 представляет собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадает с точками первой четверти.

    Теперь  рассмотрим ограничения задачи. Построим по порядку прямые:

       

 

                                                                                           (1.5)

                                                         х₁+х₂=10(IV)

и определим, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют соответственно строгим неравенствам:      
 
 
 
 

            

    Рис.1                                                       

    Сторона, в которой располагается полуплоскость  от прямой, указывается стрелками.

    Убедится  в том, с какой стороны от прямой лежит полуплоскость, точки которой  удовлетворяют заданному неравенству, можно путем подстановки координат  точек одной или другой полуплоскости  в неравенство. Когда прямая, ограничивающая полуплоскость, не проходит через начало координат, удобнее всего поставить точку с координатами (0,0). Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству будет соответствовать другая полуплоскость.

    Существует  и другой способ определения полуплоскости. Если коэффициент при х₂ в ограничении положительный, то неравенству «>» соответствует полуплоскость, лежащая выше граничной прямой, а неравенству «<» - полуплоскость, лежащая ниже граничной прямой. Если коэффициент при х₂ в ограничении отрицательный, то наоборот.

    Например, неравенству х₁-х₂<4 соответствует полуплоскость, лежащая выше прямой х₁-х₂=4, а неравенству х₁+х₂<10 соответствует полуплоскость,

 

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

    Следующим этапом присвоим целевой функции f значение нуль и построим прямую