Министерство  образования и науки РФ

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

Специальность: Программирование в компьютерных системах 

 Шифр:   РК.230115.4464.00.00.00                          
 
 

КУРСОВАЯ  РАБОТА

по дисциплине «Математические методы» 

   на  тему «Модели линейного программирования. Задача планирования производства» 
 
 
 
 
 
 
 

Руководитель        ____________   Ганиева Ч.К.                                 

Студент гр.412К  ____________  Линёва И.И. 
 

   
 
 
 

2011

 

 
СОДЕРЖАНИЕ

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

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

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

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

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

    1. Описание метода линейного программирования;

    2. Оптимизация прибыли с применением метода линейного программирования;

    3. Постановка задачи и формирование экономико-математической модели;

    4. Расчет и анализ результатов оптимизации прибыли.

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

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

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

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

    допустимых  значений. Отсюда — необходимость  разработки новых методов.  

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

    1.  рационального использования сырья  и материалов;

    2.  задачи оптимального раскроя;

    3.  оптимизации производственной программы  предприятий;

    4.  оптимального размещения и концентрации  производства;

    5.  составления оптимального плана перевозок, работы транспорта (транспортные задачи);

    6.  управления производственными запасами;

    7.  и многие другие, принадлежащие  сфере оптимального планирования.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 

1 МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

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

   Общая задача математического программирования имеет вид

   Определить  экстремум функции     f(x) ® extremum (max, min)

   при выполнении условий

   g_i(x) = (³, £)b_i, (i = ),

   x = (x₁, x₂,… x_j …x_n), x_j ³ 0, (j = ),

   где f(x) – целевая функция;

   g_i(x) - функция ограничения;

   b_i - действительное число, константа ограничения.

   Если  функции f(x) и g_i(x) представлены в виде линейных функций, то оптимизационная задача называется задачей линейного программирования.

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

1.1 Примеры задач линейного программирования

1. Задача  планирования производства

   Фирма выпускает  четыре вида персональных компьютеров

   

     
 
 
 
 
 
 

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

   

   Решение. Обозначим через Х₁ – количество изделий вида a, которое

       должна выпустить фирма; 

          Х₂ – количество изделий вида b;

          Х₃ – количество изделий вида g;

          Х₄ – количество изделий вида d.

   Найдем  затраты времени на производственный процесс в цехах (они не должны превышать располагаемый фонд времени)

                       15x₁ + 12x₂ + 4,8x₃ + 3x₄ £ 480, 

                                 8,4x₁ + 4,8x₂ + 1,8x₃ + 1,2x₄ £ 252,                                    (1)

                               2,4x₁ + 1,2x₂ + 0,12x₃ + 0,06x₄ £ 90.

   Доход за месяц должен быть максимизирован:

      f(x) = 6,5x₁ + 6x₂ + 1,5x₃ + 0,75x₄ ® max                            (2)

   Выпускается только выгодная продукция (в этом случае Х_i > 0), а невыгодная не производится (тогда Х_i = 0). Отсюда условие неотрицательности переменных

   x₁ ³ 0, x₂ ³ 0, x₃ ³ 0, x₄ ³ 0.     (3)

   Выражения (1), (2) и (3) составляют экономико-математическую модель

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

   Общей задачей линейного программирования называется задача, которая состоит в определении таких значений неизвестных переменных x₁, x₂, …, x_n, для которых функция цели  f(x) = C₁  × x₁ + C₂  × x₂ + …+ C_n  × x_n ® extremum

   принимает экстремальное значение и которые  удовлетворяют ограничениям 

                      а₁₁  × x₁ + а₁₂  × x₂ +…+ а_1n  × x_n £ b₁,

                      а₂₁  × x₁ + а₂₂  × x₂ + … + а_2n  × x_n £ b₂,             

                     …………………………………….

                     а_k1  × x₁ + а_k2  × x₂ + … + а_kn  × x_n £ b_k,

                       а_k+1,1  × x₁ + а_k+1,2  × x₂ + … + а_k+1,n  × x_n = b_k+1,

                     ……………………………………..

                     а_m1  × x₁ + а_m2  × x₂ + … + а_mn  × x_mn = b_m, 

   Функция называется  целевой функцией задачи, а условия – ограничениями данной задачи.

   Совокупность значений переменных Х₁, Х₂, …, Х_n, удовлетворяющих условиям задачи, называется допустимым решением, или планом. План X* = ( , , … ), при котором целевая функция задачи принимает экстремальное значение, называется оптимальным.

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

   Стандартной задачей линейного программирования называют задачу, в которой требуется найти такие значения Х₁, Х₂, …, Х_n, при которых функция цели принимает максимальное значение

   

   f(x) = ® max            (4)

   и которые удовлетворяют ограничениям 

     £ b_i; (i = ),            (5)

   Х_j ³ 0; (j = ).                (6)

   1.4 Каноническая (основная) задача линейного программирования

   Канонической  задачей называется задача, в которой требуется найти такой набор переменных Х₁, Х₂, …, Х_n, который позволяет максимизировать функцию цели

   f(x) = ® max            (7)

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

   

     = b_i; (i = ),            (8)

   Х_j ³ 0; (j = ).                (9)

   1.5 Представление задачи линейного программирования в канонической форме

   Пусть требуется найти неотрицательные значения переменных Х₁, Х₂, …, Х_n, для которых функция цели принимает максимальное значение

   f(x) = C₁ Х₁ + C₂Х₂ + …+ C_nХ_n ® max

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

   

                         
 

   Х_j ³ 0, (j =

). 
 

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

   Найти максимум функции цели

   f(x) = C₁ Х₁ + C₂Х₂ + …+ C_nХ_n + …+ 0×Х_n+1 + …+ 0×Х_n+m ® max

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

     
 

   Х_j ³ 0, (j =

).

   Пример. Записать следующую задачу в канонической форме:

               f(x) = -X₁ + 2X₂ - X₃ + X₄® min,

                             3X₁ - X₂ + 2X₃ + 2X₄ £ 10,

                            X₁ + 2X₂ + X₃ - X₄ ³ 8,

                            2X₁ - X₂ - X₃ + X₄ £ 6,

                            

                            -X₁ + 3X₂ + 5X₃ - 3X₄ = 15,

   X_j ³ 0, (j = 1 ¸ 4).

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

    f(x) = Х₁ - 2Х₂ + Х₃ - Х₄ + 0×Х₅ + 0×Х₆ + 0×Х₇ ® max,

                      3X₁ - X₂ + 2X₃ + 2X₄ + X₅ = 10,

                      X₁ + 2X₂ + X₃ - X₄  - X₆       = 8,

                      2X₁ - X₂ - X₃ + X₄   + X₇  = 6,

                    -X₁ + 3X₂ + 5X₃ - 3X₄    = 15,    X_j ³ 0.

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

         1. Множество планов  задачи линейного программирования, если оно не пусто, образует  выпуклый многогранник. Любая точка  внутри области, ограниченной  этим многогранником, является допустимым  решением задачи.

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

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

   1.7 Решение задач линейного программирования симплекс-методом

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

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

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

     Симплекс-метод называют еще методом последовательного улучшения плана. Повторное применение указанной процедуры приводит за конечное число шагов к вершине, соответствующей оптимальному плану.

   Симплекс-метод  применяется к задаче, записанной в канонической форме (используем одну из двойственных задач линейного программирования):

   f(x) = 10Х₁ + 14Х₂ + 12Х₃ + 0×Х₄ + 0×Х₅ + 0×Х₆ ® max,

    4X₁ + 2X₂ + X₃ + X₄          = 180,

   3X₁ + X₂ + 3X₃  + X₅         = 210,

   X₁ + 2X₂ + 5X₃        + X₆ = 244.

   Для решения  задачи линейного программирования составим симплексную таблицу.

   В первом столбце вписаны базисные неизвестные, второй содержит коэффициенты при базисных неизвестных в целевой  функции, в третьем – правые части  уравнений системы ограничений. Далее записана матрица из коэффициентов левой части системы ограничений ( ). В верхней строке над неизвестными записаны соответствующие им коэффициенты в целевой функции. В последней строке записывается значение целевой функции при данном опорном плане, которое вычисляется по формуле f(x) = , и далее – оценки неизвестных, найденные по формуле D_j = - C_j. Если среди оценок D_j есть отрицательные, то опорный план не является оптимальным и значение целевой функции можно улучшить.  

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

оценкой.

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

   Пересчет  таблицы производится по следующему правилу: элементы ключевой строки делятся  на ключевой элемент. Далее, с помощью  метода Жордана Гаусса проводят пересчет таблицы таким образом, чтобы  элементы ключевого столбца имели единицу на месте ключевого элемента и нули на месте всех остальных элементов. Для этого вычтем из элементов третьей строки соответствующие элементы первой строки, а из элементов второй строки – элементы первой строки, поделенные на два (на ключевой элемент).

   

   Переменная, соответствующая ключевой строке, выводится из базиса, а переменная, соответствующая ключевому столбцу, вводится вместо нее в  базис.

   Для каждого шага итерации строится своя симплексная таблица: