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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


курсовая работа Построение экономической модели с использованием симплекс-метода

Информация:

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

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


 Министерство образования и науки РФ
Федеральное агентство по образованию
Южно-Уральский  государственный университет 
Кафедра «Градостроительство» 
 
 
 
 
 
 
 
 
 
 

    Курсовая  работа по дисциплине
    «Экономико-математические методы и модели»
    Тема: «Построение экономической модели с использованием
    симплекс-метода» 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнил: студент гр. АС-330
Ивахин  И.О.
Проверил: преподаватель
Малев И.В. 
 

Челябинск
2011 

Оглавление
ВВЕДЕНИЕ 3
1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ 4
1.1. Понятие симплекс-метода 4
1.2. Алгоритм симплексного  – метода в  случае положительных  свободных членов 6
1.3. Двойственные задачи  линейного программирования 8
1.3.1. Построение двойственной  задачи 8
1.3.2. Двойственный симплексный  метод 11
2. ПРАКТИЧЕСКИЙ РАЗДЕЛ 12
2.1. Описание производственной  ситуации 12
2.2. Математическое описание  ситуации 13
2.3. Решение задачи 14
ЗАКЛЮЧЕНИЕ 20
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 22 
 
 
 
 
 
 
 
 
 
 
 
 
 

 


ВВЕДЕНИЕ

 
     В настоящее время каждое предприятие отвечает за свою работу само и само принимает решения о дальнейшем развитии. Современные условия рынка предъявляют к методам прогнозирования очень высокие требования, ввиду все возрастающей важности правильного прогноза для дальнейшего развития предприятия.
     Например, предприятие по производству пластиковых окон, имея 3 функционально разных цеха, производственные возможности которых ограничены, изготавливает четыре типа окон и получает от их реализации разную прибыль. Руководство ставит перед собой задачу максимизировать общую прибыль от реализации продукции. Эта проблема актуальна, т.к.           во-первых: из-за неправильного прогнозирования ситуации предприятие может работать себе в убыток, а во-вторых: рынок окон на сегодняшний день очень обширен, разнообразен и постоянно развивается, и предприятию необходимо достичь получения максимальной прибыли для того, чтобы оно смогло выдержать конкуренцию и закрепиться на рынке.
     Цель  данного курсового проекта – составить такой план производства окон, который будет обеспечивать максимальную прибыль от их реализации, свести данную задачу к задаче линейного программирования, решить её симплекс-методом. Также необходимо оценить производственные возможности каждого из цехов, используемых для производства. Для достижения цели необходимо решить следующие задачи:
      изучить симплекс-метод и двойственный симплекс-метод,
      рассмотреть реализацию симплекс-метода с помощью симплекс-таблиц,
      описать производственную ситуацию и установить оптимальный производственный план, закрепив на практике симплекс-метод.
     Объектом  исследования данной курсовой работы является только что появившееся  на рынке пластиковых окон предприятие, имеющее ограниченные производственные возможности, а предметом исследования – производственная модель данного предприятия.

1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1.1. Понятие симплекс-метода

    Для решения задач линейного программирования предложено немало различных алгоритмов. Наиболее эффективным среди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.
    Впервые симплексный метод был предложен  американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.
    Симплексный метод – это итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения. [1]
    Симплексный метод применим к решению любой  задачи линейного программирования. Из геометрического смысла задачи линейного  программирования следует, что для  ее решения необходимо вычислить  координаты всех вершин многогранника  ограничений и значения линейной формы в них. Решить задачи линейного  программирования можно методом  перебора. Действительно, перебором  всех вершин можно найти такую  вершину, где функция L приобретает экстремальное значение. При этом возможны две трудности: 

    1) так как при n > m система ограничений линейно зависима, то для построения многоугольника решений необходимо выделение всех линейно независимых систем уравнений и их решение;
    2) число вершин многогранника резко  возрастает с увеличением n > m, и такой метод перебора всех вершин может оказаться слишком трудоемким (n – число неизвестных, m – число ограничений).
    Симплексный метод обеспечивает более рациональное решение задачи, чем метод перебора. Его существо состоит в том, что, отправляясь из некоторой произвольной вершины многогранника ограничений, переходят к вычислению только такой  вершины, в которой значение линейной формы будет больше, чем в предыдущей. Остальные варианты не вычисляются. Тогда при конечном сравнительно малом числе шагов может быть найден оптимальный план. Таким образом, производится упорядоченный перебор вершин, при котором происходит постоянное увеличение линейной формы. Поэтому симплексный метод называется также методом последовательного улучшения плана.
    В тех случаях, когда модель содержит т уравнений, для построения опорных решений используются т переменных, принимающих некоторые положительные значения при нулевых значениях остальных свободных переменных. Вычислительная процедура может быть представлена в виде следующей последовательности.
    Итеративный переход от одного допустимого базисного  решения проводится направленно от одной вершины области допустимых решении к другой, заключающегося в обмене базисных и свободных переменных: базисная переменная приравнивается к нулю и переходит в свободную, а соответственно свободная переменная переводится на место базисной. Если в столбце свободных членов все элементы положительны, то решение является допустимым. Если в строке целевой функции все элементы неотрицательные, то решение является оптимальным при решении задачи на максимум.
    В соответствии с симплексным методом на первом шаге находят начальное опорное решение – допустимый вариант, удовлетворяющий всем ограничениям. Затем последовательно за определенное число итераций направленно осуществляется переход от одного опорного решения к другому вплоть до оптимального. Следует заметить, что на первом шаге в качестве базисных переменных следует выбрать такие т переменные, каждая из которых входит только один раз в одно из т уравнений системы, при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. При этом если выбранные переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях, то полученное базисное решение будет допустимым. В процессе решения системы линейных уравнений необходимо ориентироваться на сохранение не отрицательности всех переменных, поскольку это определяет допустимость решения.
    Для использования рассмотренного алгоритма симплексного метода к минимизации линейной формы связи F(X) следует искать максимум функции F1(X) = – F(X), а затем полученное решение взять с обратным знаком.
    Предложенный  алгоритм приводит к оптимальному решению для любой модели линейного программирования за конечное число итераций, если система линейных уравнений задачи совместна.
    Симплексный метод основан на последовательном переходе от одного базисного решения (опорного плана) задачи линейного программирования к другому опорному плану, при этом значение целевой функции изменяется в лучшую сторону.

1.2. Алгоритм симплексного  – метода в случае положительных свободных членов

 
    I. После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой. Для определенности записи считается, что в качестве базисных переменных можно взять переменные x1, x2, ..., xr и что при этом b'1, b'2,..., b'r ? 0 (соответствующее базисное решение является опорным). Предполагаем, что все добавочные переменные имеют тот же знак что и свободные члены; в противном случае используем так называемый М-метод.
f = ?0+ ?r+1 xr+1+…+ ?n xn > max, min                           (1)
 
 
 

    II. Исходную расширенную систему заносим в первую симплексную таблицу (таблица 1). Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком: bt = - q. В левом столбце таблицы записываем основные переменные (базис), в первой строке таблицы – все переменные (отмечая при этом основные), во втором столбце – свободные члены расширенной системы b1, b2 ..., br. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца второй строки) занесены коэффициенты аij при переменных из расширенной системы. Далее таблица преобразуется по определенным правилам.
Таблица 1
    Первая  симплексная таблица
    
Базисные  переменные
Свободные члены
x1 х2 xr xr+1 xr+2 xn
x1 b1 1 0 0 -a1,r+1 -a1,r+1 -a1n
х2 b2 0 1 0 2,r+1 2,r+1 2n
xr br 0 0 1 -ar,r+1 -ar,r+2 -arn
f ?0 0 0 0 -?r+1 -?r+2 -?n
 
    III. Проверяем выполнение критерия оптимальности при решении задачи на максимум – наличие в последней строке отрицательных коэффициентов F<0 . Если таких нет, то решение оптимально, достигнут max F, основные переменные принимают значения аi0 (второй столбец), основные переменные равны 0, т.е. получаем оптимальное базисное решение.
    IV. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент F < 0 в последней строке определяет разрешающий столбец s.
    Составляем  оценочные ограничения каждой строки по следующим правилам:
    бесконечность, если bi и ais имеют разные знаки;
    бесконечность, если bi =0 и ais <0;
    бесконечность, если ais =0;
    0, если bi =0 и ais >0;
    , если ai0 и ais имеют одинаковые знаки;
 
Определяем  минимум   Если конечного минимума нет, то задача не имеет конечного оптимума (Fmax =бесконечности). Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент аqs.
    V.  Переходим к следующей таблице по правилам:
а) в левом столбце записываем новый базис: вместо основной переменной хq – переменную xs;
б) в столбцах, соответствующих основным переменным, проставляем нули и единицы:
1 – против "своей" основной переменной, 0 – против "чужой" основной переменной,
0 – в последней строке для всех основных переменных;
в) новую строку с номером q получаем из старой делением на разрешающий элемент aqs
г) все остальные элементы вычисляем по правилу прямоугольника 

               (3)
В результате получают новую симплекс–таблицу, отвечающую новому базисному решению. Далее переходим к пункту III алгоритма.

1.3. Двойственные задачи  линейного программирования

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

1.3.1. Построение двойственной  задачи

 
    Двойственная  обратная задача – задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой, задачи[4]. В литературе по линейному программированию в большинстве случаев рассматриваются формулировки двойственной задачи, соответствующие различным формам прямой задачи, которые, в свою очередь,
определяются  типом ограничений, знаками переменных и направлением оптимизации (максимизация или минимизация). Опыт показывает, что на начальной стадии изучения теории линейного программирования детали различных формулировок двойственной задачи нередко затрудняют восприятие материала.
    Рассмотрим  обобщенную формулировку двойственной задачи линейного программирования, которая применима к любой  форме представления прямой задачи. В основу такой формулировки положен тот факт, что использование симплекс-метода требует приведения любой задачи линейного программирования к стандартной форме. Так как все методы вычислений, основанные на соотношениях двойственности, предполагают непосредственное использование симплекс-таблиц, формулировка двойственной задачи в соответствии со стандартной формой прямой задачи представляется достаточно логичной. Следует, однако, помнить, что приводимая ниже формулировка двойственной задачи является обобщенной в том смысле, что она применима ко всем формам прямой задачи.
    Прямая  задача линейного программирования в стандартной форме записывается следующим образом:
максимизировать
F(X) = ?cj xj                                                 (4)
при ограничениях:
    
      ?аij xj ? bi , i = 1,… m,                                          (5) 

xj ? 0,  j = 1,… n. 
 

    Чтобы сформулировать условия двойственной задачи, проведем симметричное структурное  преобразование условий прямой задачи в соответствии со следующими правилами:
    1) каждому ограничению прямой задачи  соответствует переменная двойственной  задачи;
    2) каждой переменной прямой задачи  соответствует ограничение двойственной  задачи;
    3) коэффициенты при некоторой переменной, фигурирующие в ограничениях  прямой задачи, становятся коэффициентами  левой части соответствующего  ограничения двойственной задачи, а коэффициент, фигурирующий при  той же переменной в выражении  для целевой функции прямой  задачи, становится постоянной правой  части этого же ограничения  двойственной задачи.
    На  примере задачи планирования товарооборота  двойственная задача формулируется  следующим образом:
    определить  оценку (неявную стоимость) единицы  каждого вида ресурсов yj (i = 1,… m), чтобы при заданных объемах ресурсов bi , прибыли Сj нормах расхода ресурсов aij минимизировать оценку всех ресурсов торгового предприятия, затраченных на организацию торгового процесса.
    Запишем математическую модель двойственной задачи. 
 

    Определить  вектор У = (y1, y2,..., уm), который удовлетворяет ограничениям 

ij xi ? cj , j = 1,… n,                                            (6) 

Xi ? 0,  i = 1,… m 
 

и обеспечивает минимальное значение целевой функции 

Z(Y)= ?bi yi >min.                                              (7) 

    Ограничения (6) показывают, что стоимость всех ресурсов, затраченных на продажу единицы j-группы товаров, должна быть не меньше дохода, получаемого при реализации единицы j-группы товаров, а общая стоимость всех ресурсов должна быть минимизирована.
    В целом двойственная задача по отношению  к исходной составляется согласно следующим правилам.
    1. Число переменных в двойственной  задаче равно числу ограничений  в прямой задаче.
    2. Матрица коэффициентов системы  ограничений двойственной задачи  получается из матрицы коэффициентов  системы ограничений прямой задачи  путем транспонирования.
    3. Система ограничений двойственной  задачи записывается в виде  неравенств противоположного смысла неравенствам системы ограничений прямой задачи.
    4. Свободными членами системы ограничений  двойственной задачи являются  коэффициенты функции цели прямой  задачи.
    5. Двойственная задача решается  на минимум, если целевая функция  прямой задачи задается на  максимум, и наоборот.
    6. Коэффициентами функции цели  двойственной задачи служат свободные  члены системы ограничений прямой  задачи.
    7. Если переменная прямой задачи  xj ? 0, то j-е условие системы ограничений двойственной задачи является неравенством, если xjлюбое число, то j-е условие двойственной задачи представляет собой уравнение.
    8. Если i-е соотношение прямой задачи является неравенством, то соответствующая оценка i-го ресурса – переменная уi ? 0, если i-е соотношение представляет собой уравнение, то переменная двойственной задачи уi– любое число.
    Решение прямой задачи дает оптимальные объемы в структуре товарооборота торгового  предприятия, а решение двойственной – оптимальную систему оценок ресурсов, используемых для реализации товаров. 

1.3.2. Двойственный симплексный  метод

 
    Двойственный  симплексный метод основан на теории двойственности и используется для решения задач линейного  программирования, свободные члены  которых bi(i = 1,… m) могут принимать любые значения, а система ограничений задана неравенствами смысла «?», «?» или равенством «=».
    В двойственном симплексном методе оптимальный  план получается в результате движения по псевдопланам.
    Псевдопланом называется план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных xi имеются отрицательные числа.[4]
    Алгоритм  двойственного симплексного метода включает следующие этапы.
    1. Составление псевдоплана. Систему ограничений исходной задачи требуется привести к системе неравенств смысла «?». Для этого обе части неравенств смысла «?» необходимо умножить на (-1). Затем от системы неравенств смысла «?» переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. Первый опорный план заносят в симплексную таблицу.
    2. Проверка плана  на оптимальность.  Если в полученном опорном плане не выполняется условие оптимальности, то решаем задачу симплексным методом. При этом столбец ?i имеет значения по тем строкам, в которых значения в базисных переменных и коэффициенты ведущего столбца содержат одинаковые знаки (положительные или отрицательные). В случае разноименных знаков bi и аik значения ?i не определяют.
    Если  в опорном плане условия оптимальности  удовлетворяются и все значения базисных переменных – положительные числа, то получен оптимальный план. Наличие отрицательных значений в столбце «Значения базисных переменных» свидетельствует о получении псевдоплана.
    3. Выбор ведущих  строки и столбца.  Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
    Симплексную таблицу дополняют строкой ?, в которую заносят взятые по абсолютной величине результаты деления коэффициентов  индексной строки на отрицательные коэффициенты ведущей строки. Минимальные значения ? определяют ведущий столбец и переменную, вводимую в базис. На пересечении ведущих строки и столбца находится разрешающий элемент.
    4. Расчет нового  опорного плана.  Новый план получаем в результате пересчета симплексной таблицы методом Жордана - Гаусса.
Далее переходим к этапу 2.

2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

2.1. Описание производственной  ситуации

     В связи с расширением производства предприятие планирует запустить новые цеха и изготавливать в них пластиковые окна 4 типов. Все типы окон изготавливаются из одних и тех же материалов, ресурс которых в данный момент не ограничен. Будет запущено 3 цеха: 1-ый будет разрезать стекла по размерам, соответствующим типам окон; 2-ой будет изготавливать стеклопакеты; 3-ий будет занимается окончательной сборкой окон и их загрузкой для отправления на склад фирмы-продавца. У предприятия уже есть обязательство на поставку 12 окон в день 4 типа. Каждый цех работает по 12 часов в сутки (720 минут в сутки). Затраты времени цехов, а также прибыль с реализации окон  указаны в таблице. Задача заключается в правильном распределении возможностей цехов, максимизации прибыли от реализации продукции.
     Таблица 2
     Производственные  возможности цехов и прибыль предприятия от реализации окон разных типов
Цех Запасы       времени, мин. Трудоемкость  работ, мин.
    Тип окна
1-ый 2-ой 3-ий 4-ый
1-ый 720 10 12 15 20
2-ой 720 15 18 20 25
3-ий
и т.д.................


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


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


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


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


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