Автор работы: Пользователь скрыл имя, 17 Января 2013 в 16:05, курсовая работа
Целью данной курсовой работы является составление плана производства для компании по производству гусеничных механизмов, который обеспечит максимальную прибыль от реализации продукции, выпускаемой данным предприятием.
Задачи курсовой работы:
1. Для составления плана производства необходимо свести имеющиеся данные к задаче линейного программирования, т. е. осуществить математическую формализацию задачи линейного программирования;
2. Полученную задачу необходимо решить симплексным методом;
3. Произвести оценку имеющихся ресурсов с помощью двойственной задачи;
4. Произвести анализ устойчивости полученных двойственных оценок.
ВВЕДЕНИЕ………………………………………………………………………..4
1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ
1.1. Понятие симплексного метода решения задач линейного программирования…………………………………………………………6
1.2. Порядок работы с симплекс-таблицей……………………………...10
1.3. Двойственная модель линейного программирования……………..12
1.3.1. Построение двойственной задачи………………………….12
1.3.2. Сравнительная характеристика прямой и двойственной модели………………………………………………………………15
1.4. Двойственный симплексный метод…………………………………16
2. ПРАКТИЧЕСКИЙ РАЗДЕЛ
2.1. Содержательная постановка задачи………………………………...18
2.2. Разработка и описание алгоритма решения задачи
2.2.1. Построение математической модели задачи……………....19
2.2.2. Решение задачи………………………………………………20
2.3. Анализ модели на чувствительность
2.3.1. Построение двойственной задачи и ее решение…………..24
2.3.2. Определение статуса и значимости ресурсов……………...25
2.3.3. Определение интервалов устойчивости решения…………26
ЗАКЛЮЧЕНИЕ………………………………………………………………….29
БИБЛИОГРАФИЧЕСКОЕ ОПИСАНИЕ…………………………………….....31
Максимизировать прибыть данного предприятия.
2.2. Разработка и описание алгоритма решения задачи
2.2.1. Построение математической модели задачи
Для построения математической модели задачи необходимо определить переменные, для которых будет составляться математическая модель, сформировать целевую функцию и систему ограничений.
1) Определение переменных математической модели
Обозначим через объем производимых товаров:
– количество производимого товара A
– количество производимого товара B
– количество производимого товара C
– количество производимого товара D
2) Формирование целевой функции
Известна стоимость
Таким образом, целевая функция примет вид:
3) Формирование системы ограничений
Для определения плана производства необходимо учесть имеющиеся ресурсы: сырье, сборка, обжиг, упаковка. Поэтому переменные , , и должны удовлетворять системе неравенств:
А так как объем производства товаров не может принимать отрицательные значения, то , , ,
2.2.2. Решение задачи
Для решения задачи ее необходимо привести к каноническому виду. Это осуществляется путем перехода от ограничений-неравенств к ограничениям-равенствам путем ввода в каждое неравенство системы ограничений дополнительной переменной и приравниванием его к правой части неравенства.
Таким образом, получим систему уравнений:
Дополнительные переменные , , и характеризуют в данном плане производства товаров неиспользуемые ресурсы.
Представим коэффициенты,
стоящие в левой части системы
ограничений, в матричной форме.
За обозначения столбцов примем переменные,
которым они соответствуют. Значения
правой части ограничений запишем
в отдельном столбце матрицы
справа. За обозначения строк примем
обозначения соответствующих
Заполним первую симплекс-таблицу (табл. 2.2).
Таблица 2.2
Первая симплекс-таблица
Cj |
40 |
42 |
44 |
48 |
0 |
0 |
0 |
0 |
||
Cб |
Базис |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
bi |
|
0 |
x5 |
6,0 |
6,5 |
6,1 |
6,1 |
1 |
0 |
0 |
0 |
35000 |
0 |
x6 |
1,0 |
0,75 |
1,25 |
1,0 |
0 |
1 |
0 |
0 |
6000 |
0 |
x7 |
3,0 |
4,5 |
6,0 |
6,0 |
0 |
0 |
1 |
0 |
30000 |
0 |
x8 |
0,5 |
0,5 |
0,5 |
0,75 |
0 |
0 |
0 |
1 |
4000 |
Dj |
−40 |
−42 |
−44 |
−48 |
0 |
0 |
0 |
0 |
0 |
Шаг 2. В строке коэффициентов целевой функции найдем наибольшее отрицательное значение (−48). Столбец, соответствующий этому значению, называется ведущим. Разделим значения правой части на соответствующие значения ведущего столбца. В результате получим ряд отношений.
Таблица 2.3
Первая симплекс-таблица с учетом отношений
Cj |
40 |
42 |
44 |
48 |
0 |
0 |
0 |
0 |
bi |
δi | |
|
Cб |
Базис |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 | ||
|
0 |
x5 |
6,0 |
6,5 |
6,1 |
6,1 |
1 |
0 |
0 |
0 |
35000 |
35000/6,1=5737,7 |
0 |
x6 |
1,0 |
0,75 |
1,25 |
1,0 |
0 |
1 |
0 |
0 |
6000 |
6000/1,0=6000 |
0 |
x7 |
3,0 |
4,5 |
6,0 |
6,0 |
0 |
0 |
1 |
0 |
30000 |
30000/6,0=5000 |
0 |
x8 |
0,5 |
0,5 |
0,5 |
0,75 |
0 |
0 |
0 |
1 |
4000 |
4000/0,75=5333,3 |
Dj |
−40 |
−42 |
−44 |
−48 |
0 |
0 |
0 |
0 |
0 |
Ведущий столбец
Шаг 3. Выберем среди полученных отношений наименьшее положительное отношение. В нашем случае оно равно 5000. Соответствующая ему строка x7 является ведущей. Пересечение ведущего столбца и ведущей строки дает ведущий элемент 6,0, в приведенной выше таблице 2.3 он обозначен «6,0».
Шаг 4. Разделим все элементы ведущей строки на ведущий элемент, 6,0. Заменим все элементы ведущей строки на полученные новые значения (табл. 2.4). Обозначение ведущей строки x7 заменим обозначением ведущего столбца – x4. Новые переменные, соответствующие обозначениям строк, – это базисные переменные второго базисного решения.
Таблица 2.4
Вторая симплекс-таблица
Cj |
40 |
42 |
44 |
48 |
0 |
0 |
0 |
0 |
bi |
δi | |
|
Cб |
Базис |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 | ||
|
0 |
x5 |
2,95 |
1,93 |
0 |
0 |
1 |
0 |
−1,02 |
0 |
4500 |
4500/2,95=1525,4 |
0 |
x6 |
0,5 |
0 |
0,25 |
0 |
0 |
1 |
−0,17 |
0 |
1000 |
1000/0,5=2000 |
48 |
x4 |
0,5 |
0,75 |
1 |
1 |
0 |
0 |
0,17 |
0 |
5000 |
5000/0,5=10000 |
0 |
x8 |
0,13 |
−0,06 |
−0,25 |
0 |
0 |
0 |
−0,13 |
1 |
250 |
250/0,25=1000 |
Dj |
−16 |
−6 |
4 |
0 |
0 |
0 |
8 |
0 |
240000 |
Ведущий столбец
Шаг 5. Применив к строкам матрицы арифметические операции (строчные операции в матричной алгебре), приведем все остальные элементы ведущего столбца x4 к нулю. В качестве базиса в этих арифметических операциях должна использоваться только ведущая строка.
Для определения остальных элементов таблицы 4 применяем правило прямоугольника.
Шаг 6. Шаги 2-5 повторяются до тех пор, пока не будет достигнута неотрицательность всех элементов в строке целевой функции. Результат решения задачи представлен в таблице 2.5.
Таблица 2.5
Третья, итоговая, симплекс-таблица
Cj |
40 |
42 |
44 |
48 |
0 |
0 |
0 |
0 |
bi | |
|
Cб |
Базис |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 | |
|
40 |
x1 |
1 |
0,65 |
0 |
0 |
0,34 |
0 |
−0,34 |
0 |
1525,42 |
0 |
x6 |
0 |
−0,33 |
0,25 |
0 |
−0,17 |
1 |
0,01 |
0 |
237,29 |
48 |
x4 |
0 |
0,42 |
1 |
1 |
−0,17 |
0 |
0,34 |
0 |
4237,29 |
0 |
x8 |
0 |
−0,14 |
−0,25 |
0 |
−0,04 |
0 |
−0,08 |
1 |
59,32 |
Dj |
0 |
4,44 |
4 |
0 |
5,42 |
0 |
2,49 |
0 |
264406,78 |