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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 11.05.2012. Сдан: 2011. Страниц: 11. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Министерство  образования и науки РФ
ФГОУ  СПО «КАМСКИЙ ГОСУДАРСТВЕННЫЙ АВТОМЕХАНИЧЕСКИЙ ТЕХНИКУМ» 
 
 

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

 Шифр:   РК.230115.4464.00.00.00                          
 
 

КУРСОВАЯ  РАБОТА
по дисциплине «Математические методы» 

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

Руководитель        ____________   Ганиева Ч.К.                                 
Студент гр.412К  ____________  Линёва И.И. 
 

                       
                     
                     
                     


2011
 

 
СОДЕРЖАНИЕ

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ


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

    1. Описание метода линейного программирования;
    2. Оптимизация прибыли с применением метода линейного программирования;
    3. Постановка задачи и формирование экономико-математической модели;
    4. Расчет и анализ результатов оптимизации прибыли.

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


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

    Линейное  программирование представляет собой  наиболее часто используемый метод  оптимизации. К числу задач линейного  программирования можно отнести задачи:
    1.  рационального использования сырья  и материалов;
    2.  задачи оптимального раскроя;
    3.  оптимизации производственной программы  предприятий;
    4.  оптимального размещения и концентрации  производства;
    5.  составления оптимального плана перевозок, работы транспорта (транспортные задачи);
    6.  управления производственными запасами;
    7.  и многие другие, принадлежащие  сфере оптимального планирования.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 
   Раздел  математических методов, в котором  рассматриваются способы решения  задач на нахождение экстремума функции  цели при ограничении области допустимых значений в форме уравнений или неравенств, называется математическим программированием. Другими словами, математическое (оптимальное) программирование рассматривает задачи планирования, распределения ограниченных ресурсов наилучшим образом, для достижения поставленных целей.
   Общая задача математического программирования имеет вид
   Определить  экстремум функции     f(x) ® extremum (max, min)
   при выполнении условий
   gi(x) = (?, ?)bi, (i = ),
   x = (x1, x2,… xj …xn), xj ? 0, (j = ),
   где f(x) – целевая функция;
   gi(x) - функция ограничения;
   bi - действительное число, константа ограничения.
   Если  функции f(x) и gi(x) представлены в виде линейных функций, то оптимизационная задача называется задачей линейного программирования.
   Таким образом, линейное программирование –  это область математического программирования, посвященная  теории и  методам решения  задач нахождения условного экстремума и характеризующаяся линейной зависимостью между переменными.

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

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

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

         
 
 
 
 
 
 

   Цех    Затраты времени на единицу продукции, ч Общий фонд    времени,ч/мес
   a    b    g    d
   Узловой сборки    15    12    4,8    3    480
   Сборочный    8,4    4,8    1,8    1,2    252
   Испытательный    2,4    1,2    0,12    0,06    90
   Доход, ден.ед.    6,5    6    1,5    0,75    __
         Определить, сколько  изделий и какого вида следует изготовить фирме, чтобы доход за месяц был бы максимальным. Построить экономико-математическую модель задачи.
   
   Решение. Обозначим через Х1 – количество изделий вида a, которое
       должна выпустить фирма; 
          Х2 – количество изделий вида b;
          Х3 – количество изделий вида g;
          Х4 – количество изделий вида d.
   Найдем  затраты времени на производственный процесс в цехах (они не должны превышать располагаемый фонд времени)
                       15x1 + 12x2 + 4,8x3 + 3x4 ? 480, 
                                 8,4x1 + 4,8x2 + 1,8x3 + 1,2x4 ? 252,                                    (1)
                               2,4x1 + 1,2x2 + 0,12x3 + 0,06x4 ? 90.
   Доход за месяц должен быть максимизирован:
      f(x) = 6,5x1 + 6x2 + 1,5x3 + 0,75x4 ® max                            (2)
   Выпускается только выгодная продукция (в этом случае Хi > 0), а невыгодная не производится (тогда Хi = 0). Отсюда условие неотрицательности переменных
   x1 ? 0, x2 ? 0, x3 ? 0, x4 ? 0.     (3)

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

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

   Общей задачей линейного программирования называется задача, которая состоит в определении таких значений неизвестных переменных x1, x2, …, xn, для которых функция цели  f(x) = C? x1 + C2  ? x2 + …+ Cn  ? xn ® extremum
   принимает экстремальное значение и которые  удовлетворяют ограничениям 

                      а11  ? x1 + а12  ? x2 +…+ а1n  ? xn ? b1,
                      а21  ? x1 + а22  ? x2 + … + а2n  ? xn ? b2,             
                     …………………………………….
                     аk? x1 + аk2  ? x2 + … + аkn  ? xn ? bk,
                       аk+1,1  ? x1 + аk+1,2  ? x2 + … + аk+1,n  ? xn = bk+1,
                     ……………………………………..
                     аm? x1 + аm2  ? x2 + … + аmn  ? xmn = bm, 

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

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

   Стандартной задачей линейного программирования называют задачу, в которой требуется найти такие значения Х1, Х2, …, Хn, при которых функция цели принимает максимальное значение
   
   f(x) = ® max            (4)
   и которые удовлетворяют ограничениям 

     ? bi; (i = ),            (5)
   Хj ? 0; (j = ).                (6)

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

   Канонической  задачей называется задача, в которой требуется найти такой набор переменных Х1, Х2, …, Хn, который позволяет максимизировать функцию цели
   f(x) = ® max            (7)
   и удовлетворяет системе ограничений
   
     = bi; (i = ),            (8)
   Хj ? 0; (j = ).                (9)

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

   Пусть требуется найти неотрицательные значения переменных Х1, Х2, …, Хn, для которых функция цели принимает максимальное значение
   f(x) = C1 Х1 + C2Х2 + …+ CnХn ® max
   при ограничениях
   
                         
 

   Хj ? 0, (j =
).
 
 

   Поскольку в ограничениях левая часть меньше, чем правая (или равна ей), чтобы перейти к строгому равенству, необходимо к левой части каждого неравенства добавить соответствующую переменную.
   Найти максимум функции цели
   f(x) = C1 Х1 + C2Х2 + …+ CnХn + …+ 0?Хn+1 + …+ 0?Хn+m ® max
   при ограничениях
     
 

   Хj ? 0, (j =
).

   Пример. Записать следующую задачу в канонической форме:
               f(x) = -X1 + 2X2 - X3 + X4® min,
                             3X1 - X2 + 2X3 + 2X4 ? 10,
                            X1 + 2X2 + X3 - X4 ? 8,
                            2X1 - X2 - X3 + X4 ? 6,
                            
                            -X1 + 3X2 + 5X3 - 3X4 = 15,
   Xj ? 0, (j = 1 ? 4).
   Для записи задачи в канонической форме  поменяем знаки у всех коэффициентов  функции цели на противоположные. Тогда  задача будет заключаться в нахождении максимума целевой функции. Для  приведения ограничений – неравенств к системе уравнений необходимо приравнять левые и правые части ограничений путем введения дополнительных переменных. Если левая часть ограничения меньше, чем правая, необходимо добавить дополнительную переменную, если же левая часть ограничения больше, из нее следует вычесть некоторое, пока неизвестное, значение.
    f(x) = Х1 - 2Х2 + Х3 - Х4 + 0?Х5 + 0?Х6 + 0?Х7 ® max,
                      3X1 - X2 + 2X3 + 2X4 + X5 = 10,
                      X1 + 2X2 + X3 - X - X6       = 8,
                      2X1 - X2 - X3 + X4   + X= 6,
                    -X1 + 3X2 + 5X3 - 3X4    = 15,    Xj ? 0.

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

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

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


   Если  условия задачи линейного программирования не противоречивы, то область ее допустимых решений образует выпуклый многогранник в n-мерном пространстве (многоугольник для двух переменных). При этом оптимальное решение, если оно существует, обязательно достигается в некоторой вершине многогранника (возможно, и более чем в одной).
   Таким образом, чтобы найти решение  задачи линейного программирования, достаточно перебрать лишь планы, соответствующие вершинам многогранника допустимых решений. Такие планы называют опорными. Однако в сложных задачах и число вершин может оказаться чрезмерно большим, вследствие чего нахождение всех опорных планов потребует огромного объема вычислений.
   Симплекс-метод  позволяет осуществить упорядоченный, направленный перебор вершин многогранника. После определения одной из вершин этот метод помогает установить, является ли найденный план оптимальным, то есть достигнут ли в этой вершине максимум целевой функции. Если план неоптимален, то производится переход к такой соседней вершине многогранника, которая обеспечивает большее (или в крайнем случае равное предыдущему) значение целевой функции.
     Симплекс-метод называют еще методом последовательного улучшения плана. Повторное применение указанной процедуры приводит за конечное число шагов к вершине, соответствующей оптимальному плану.
   Симплекс-метод  применяется к задаче, записанной в канонической форме (используем одну из двойственных задач линейного программирования):
   f(x) = 10Х1 + 14Х2 + 12Х3 + 0?Х4 + 0?Х5 + 0?Х6 ® max,
    4X1 + 2X2 + X3 + X4          = 180,
   3X1 + X2 + 3X + X5         = 210,
   X1 + 2X2 + 5X3        + X6 = 244.
   Для решения  задачи линейного программирования составим симплексную таблицу.
   
     Базис Б
      План Х    Коэффициенты  функции цели Сi    q = (Хi /
)min
   Х1    Х2    Х3    Х4    Х5    Х6
   
   Х2
®Х4
   180    4    2    1    1    0    0    180/2 = 90 min
   
Х5
   210    3    1    3    0    1    0    210/1 =210
   Х6    244    1    2    5    0    0    1    244/2 =122
        -10    -14    -12    0    0    0       ключевая строка
   В первом столбце вписаны базисные неизвестные, второй содержит коэффициенты при базисных неизвестных в целевой  функции, в третьем – правые части  уравнений системы ограничений. Далее записана матрица из коэффициентов левой части системы ограничений ( ). В верхней строке над неизвестными записаны соответствующие им коэффициенты в целевой функции. В последней строке записывается значение целевой функции при данном опорном плане, которое вычисляется по формуле f(x) = , и далее – оценки неизвестных, найденные по формуле Dj = - Cj. Если среди оценок Dj есть отрицательные, то опорный план не является оптимальным и значение целевой функции можно улучшить.  

   Для этого нужно пересчитать  симплексную  таблицу, выбрав соответствующим образом ключевой элемент, стоящий на пересечении ключевой строки и ключевого столбца, причем берется столбец с наибольшей по абсолютной величине отрицательной
оценкой.
   Для определения ключевой строки находим отношения правых частей уравнений к положительным элементам ключевого столбца. Полученные значения q записываются в последний столбец симплексной таблицы. Из них выбирается наименьшая величина, которая указывает на ключевую строку.
   Пересчет  таблицы производится по следующему правилу: элементы ключевой строки делятся  на ключевой элемент. Далее, с помощью  метода Жордана Гаусса проводят пересчет таблицы таким образом, чтобы  элементы ключевого столбца имели единицу на месте ключевого элемента и нули на месте всех остальных элементов. Для этого вычтем из элементов третьей строки соответствующие элементы первой строки, а из элементов второй строки – элементы первой строки, поделенные на два (на ключевой элемент).
   
   Переменная, соответствующая ключевой строке, выводится из базиса, а переменная, соответствующая ключевому столбцу, вводится вместо нее в  базис.
   Для каждого шага итерации строится своя симплексная таблица:
   Б    Х    10    14    12    0    0    0    q
   Х1    Х2    Х3    Х4    Х5    Х6
   
Х2
   90    2    1    1/2    1/2    0    0     90 : 1/2 = 180
   
Х5
   120    1    0    5/2    -1/2    1    0    1   20 : 5/2 = 48
   
Х3
®Х6
   64    -3    0    4    -1    0    1    64 : 4 = 16 min
   f(x) = 1260    18    0    -5    7    0    0     
               Отрицательная оценка     
   Поскольку среди оценок неизвестных есть отрицательная, необходимо продолжить расчеты и составить новую таблицу. Для этого элементы третьей (ключевой) строки разделим на ключевой элемент.
     Умножив новые элементы третьей  строки на 1/2, вычтем их из соответствующих элементов первой строки предыдущей таблицы. Затем, умножив новые элементы третьей строки на 5/2, вычтем их из соответствующих элементов второй строки предыдущей таблицы.  

Третья  симплексная таблица имеет вид
   Б    Сi    Х    10    14    12    0    0    0    q
   Х1    Х2    Х3    Х4    Х5    Х6
   Х2    14    82
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.