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

 

Санкт-Петербургский государственный  политехнический университет 

Кафедра управления в социально-экономических  системах

 

 

 

 

 

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

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

на тему«Определение оптимального производственного плана предприятия»

 

 

 

 

 

Выполнил студент гр. 3242/4 
     ____________     А.С. Гончарова

 

Проверил старший преподаватель

      ____________     А.В. Изотов

 

 

 

 

 

 

 

 

Санкт-Петербург

2012

 

 СОДЕРЖАНИЕ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

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

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

Выполнение работы включает в себя следующие пункты:  
1. Построение экономико-математических моделей однокритериальной и многокритериальной задач с подробным описанием всех входящих в модель постоянных и переменных величин;  
2. Решение однокритериальной задачи с целевой функцией выручка; 
3. Пост оптимизационный анализ;  
4. Решение задачи параметрического линейного программирования:  
a) с параметром в целевой функции; 
b) с параметром в правых частях системы ограничений. 
5. Решение многокритериальной задачи: 
a) методом свертывания критериев;  
b) методом главного критерия;  
c) модифицированным методом идеальной точки;  
d) методом последовательных уступок.  

1. ПОСТАНОВКА ЗАДАЧИ

Промышленное предприятие  может изготавливать три вида изделий А,В и С, используя при  этом три основных, т.е. определяющих программу выпуска вида ресурсов R₁, R₂ и R₃. Нормы расхода ресурса на единицу изделий каждого вида, запасы ресурсов на месяц, себестоимость изготовления единицы изделий и их цены представлены в табл. 1. По требованиям технологии ресурс R₃ должен быть полностью израсходован в течение месяца.

Необходимо сформировать план выпуск изделий на месяц, применяя следующие критерии:

1. Максимум выручки от реализации производственной продукции;
2. Минимум себестоимости изготовления изделий.

Таблица 1.1 «Условие задачи»

Наименование  показателей	Нормы расхода  ресурсов			Запасы ресурсов
	А	В	С
Ресурс R1	1	1	3	24
Ресурс R2	2	2	4	30
Ресурс R3	3	2	5	24
Себестоимость изготовления изделий, тыс. руб.	9	13	15
Цена единицы  изделия, тыс. руб.	12	16	19

 

2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РЕШЕНИЯ ЗАДАЧ

ПОСТРОЕНИЕ ЭКОНОМИКО-МАТЕМАТИЧЕКИХ  МОДЕЛЕЙ

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

 

 

 

 

 

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

Всякий набор значений переменных, то есть вектор X значений,

 

называется планом задачи.

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

Решить задачу линейного программирования - значит найти ее оптимальный план и оптимум.  

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

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

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

В частном случае, когда  в систему ограничений входят только две переменные x₁ и x₂, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x₁, x₂ ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.

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

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

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

Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.

Таким образом, оптимальное  решение ЗЛП следует искать среди  конечного числа допустимых базисных решений.

Симплекс-метод:

В данной работе также будет решаться задача симплекс-методом.

Этот метод является универсальным, применимым к любой задаче линейного  программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X₁, X₂, ..., X_r. Тогда наша система уравнений может быть записана как

 

 

 

 

К такому виду можно привести любую совместную систему, например, методом Гаусса.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через  свободные), мы будем получать различные  решения нашей системы ограничений. Таким образом, можно получить любое  ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны  нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X₁, X₂, ..., X_r, то решение {b₁, b₂,..., b_r, 0, ..., 0} будет опорным при условии, что b₁, b₂,..., b_r ≥ 0.

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

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

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

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

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

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

 

 

 

 

 

Здесь для определенности записи считается, что в качестве базисных переменных можно взять  переменные X₁, X₂, ..., X_r и что при этом b₁, b₂,..., b_r ≥ 0 (соответствующее базисное решение является опорным).

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

 

 

 

 

 

 

Далее эта система оформляется  в виде симплекс-таблиц:

Таблица 2.1. «Симплекс-таблица»

 

 

 

 

 

 

 

 

Алгоритм  перехода к следующей таблице  такой:

• просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов  ) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке- ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;
• в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:
• разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
• строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.
• в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.
• столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.
• строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.
• в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы: