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

Федеральное агентство по образованию

Южно-Уральский  государственный университет 

Кафедра «Градостроительство» 
 
 
 
 
 
 
 
 
 
 

    Курсовая  работа по дисциплине

    «Экономико-математические методы и модели»

    Тема: «Построение экономической модели с использованием

    симплекс-метода» 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнил: студент гр. АС-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. изучить симплекс-метод и двойственный симплекс-метод,
2. рассмотреть реализацию симплекс-метода с помощью симплекс-таблиц,
3. описать производственную ситуацию и установить оптимальный производственный план, закрепив на практике симплекс-метод.

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

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

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

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

    Впервые симплексный метод был предложен  американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.

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

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

    1) так как при n > m система ограничений линейно зависима, то для построения многоугольника решений необходимо выделение всех линейно независимых систем уравнений и их решение;

    2) число вершин многогранника резко  возрастает с увеличением n > m, и такой метод перебора всех вершин может оказаться слишком трудоемким (n – число неизвестных, m – число ограничений).

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

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

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

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

    Для использования рассмотренного алгоритма симплексного метода к минимизации линейной формы связи F(X) следует искать максимум функции F₁(X) = – F(X), а затем полученное решение взять с обратным знаком.

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

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

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

 

    I. После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой. Для определенности записи считается, что в качестве базисных переменных можно взять переменные x₁, x₂, ..., x_r и что при этом b'₁, b'₂,..., b'_r ≥ 0 (соответствующее базисное решение является опорным). Предполагаем, что все добавочные переменные имеют тот же знак что и свободные члены; в противном случае используем так называемый М-метод.

f = γ₀+ γ_r+1 x_r+1+…+ γ_n x_n → max, min                           (1)

 
 
 

    II. Исходную расширенную систему заносим в первую симплексную таблицу (таблица 1). Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком: b_t = - q. В левом столбце таблицы записываем основные переменные (базис), в первой строке таблицы – все переменные (отмечая при этом основные), во втором столбце – свободные члены расширенной системы b₁, b₂ ..., b_r. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца второй строки) занесены коэффициенты а_ij при переменных из расширенной системы. Далее таблица преобразуется по определенным правилам.

Таблица 1

    Первая  симплексная таблица