Нахождение оптимального плана производства двух типов ремонтных работ с помощью симплексного метода
Математические и программные средства моделирования при решении конкретной производственной задачи. Метод реализации задачи планирования производства и нахождение оптимального плана с помощью симплексного метода. Программа на языке программирования С.
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 06.06.2011 |
| Размер файла | 603,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ВВЕДЕНИЕ
Оптимальной производственной программой предприятия считается такая программа выпуска продукции, при которой достигается максимальный экономический эффект. Такая производственная программа может быть определена только путем решения задачи по размещению и концентрации производства по отрасли или народному хозяйству в целом.
Под оптимальной производственной программой следует понимать такой выпуск изделий за определенный промежуток времени, при котором достигается максимальная экономическая эффективность для данного предприятия.
Применение экономико-математических методов в планировании производства позволяет рационально использовать сырьевые ресурсы, а, следовательно, снижать себестоимость выпускаемой продукции, а прибыль приносить максимальную. Наибольшее значение и наиболее широкое применение при решении экономических задач в настоящее время приобрели методы линейного программирования.
Методы линейного программирования позволяют обеспечивать рациональный раскрой материалов, рациональное смешивание взаимозаменяемых компонентов, помогают разрабатывать технически обоснованные нормы расхода материалов.
Экономические задачи в большинстве случаев относятся к экстремальным задачам, для решения которых необходимо из большого количества возможных решений найти одно, оптимальное, т.е. максимизирующее или минимизирующее соответствующую числовую функцию. Задачи такого типа решаются методами линейного программирования.
В частности:
- симплексный метод,
- метод искусственного базиса,
- двойственный симплексный метод,
- графический метод.
В данной курсовой работе используется симплексный метод, задача линейного программирования реализуется на ЭВМ, используя средства ЯП Pascal для решения задач оптимизации.
1 ПОСТАНОВКА ЗАДАЧИ
Небольшая фирма производит два тина подшипников А и В, каждый из которых должен быть использован на трех станках, а именно на токарном, шлифовальном и сверлильном.
Время, требуемое для каждой из стадий производственного процесса, приведена в табл.1.
Таблица1
|
Тип подшипника |
Время обработки (час) |
Прибыль от продажи 1 подшипника (доллары) |
|||
|
Токарный станок |
Шлифовальный станок |
Сверлильный станок |
|||
|
А |
0.01 |
0.02 |
0.04 |
80 |
|
|
В |
0.02 |
0.01 |
0.01 |
125 |
|
|
Полное время работы В неделю (час) |
160 |
120 |
150 |
Фирма хотела бы производить подшипники в количествах, максимизирующих ее прибыль. Задачу решить симплексным методом. Программу составить на языке программирования С и реализовать на ПЭВМ.
2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
Математическая модель в общем виде:
Вводятся обозначения:
m - тип подшибников;
n - виды станков;
aij - норма расхода , i-го вида сырья на j вид ремонтных работ
bi - общее количество сырья i-го вида;
cj - прибыль от одного ремонта j - го вида;
xj - выпуск ремонтных работ j-го вида;
Z - максимальная прибыль от выпуска ремонтных работ.
Математическая модель данной ЗЛП:
при ограничениях:
Модель необходимо привести к каноническому виду, введем дополнительные переменные:x3,x4,x5,x6, а в целевую функцию они войдут с нулевыми коэффициентами.
Тогда модель примет вид
при ограничениях
3 МЕТОД РЕАЛИЗАЦИИ МОДЕЛИ
Поставлена задача линейного программирования. Найти максимальное значение функции
при ограничениях
Размещено на http://www.allbest.ru/
Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов. Через конечное число шагов линейная форма достигает max или min.
Заполняется исходная таблица. После чего производится вычисления в последовательности:
· Подсчитывается и определяется, не является ли рассматриваемый план оптимальным, т.е. не выполняется ли для всех x условие: 0
· Если для некоторого j значение >0, то выбирается вектор, который может быть введен в базис. Для этого разыскивается какое-нибудь j, для которого max()=>0, тогда P- вводится в базис.
; : j=1,2,…,n
· Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: = min= для всех X>0 , тогда P- исключается из базиса.
· Если все X< 0, то линейная форма неограниченна снизу.
· После выделения направляющей строки и направляющего столбца, таблица преобразуется по формуле полного исключения.
В результате каждой итерации образуется новый опорный план. В конце концов, либо придем к оптимальному плану, либо убедимся в неограниченности линейной формы задачи. Вычисления сводятся в табл.2:
Таблица №2
|
i |
Базис |
C |
P0 |
C1 |
C2 |
…… |
Cl |
…… |
Cm |
Cm+1 |
…… |
Cj |
…… |
Ck |
…… |
Cn |
|
|
P1 |
P1 |
…… |
P1 |
…… |
Pm |
Pm+1 |
…… |
Pj |
…… |
Pk |
…… |
Pn |
|||||
|
1 |
P1 |
C1 |
X1 |
1 |
0 |
…… |
0 |
…… |
0 |
X1,m+1 |
…… |
X1j |
…… |
X1k |
…… |
X1n |
|
|
2 |
P2 |
C2 |
X2 |
0 |
1 |
…… |
0 |
…… |
0 |
X2,m+1 |
…… |
X2j |
…… |
X2k |
…… |
X2n |
|
|
... |
… |
… |
… |
… |
… |
…… |
… |
…… |
… |
… |
…… |
… |
v… |
… |
…… |
… |
|
|
l |
Pl |
Cl |
Xl |
0 |
0 |
…… |
1 |
…… |
0 |
Xl,m+1 |
…… |
Xlj |
v… |
Xlk |
…… |
Xln |
|
|
… |
… |
… |
… |
… |
… |
…… |
…… |
… |
… |
…… |
… |
…… |
… |
…… |
|||
|
m |
Pm |
Cm |
Xm |
0 |
0 |
…… |
0 |
…… |
1 |
Xm,m+1 |
…… |
Xmj |
…… |
Xmk |
…… |
Xmn |
|
|
m+1 |
Z0 |
0 |
0 |
…… |
0 |
…… |
0 |
Zm+1-Cm+1 |
…… |
Zj-Cj |
v… |
v… |
4 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
4.1 Вводятся коэффициенты a,b,c
4.2 Заполняется симплексная таблица
4.3 Находится базис
4.4 Находится опорный план
4.5 Вычисляется Z-C в m+1 строке
4.6 Проверяется условие Z-C?0 в m+1 строке, если выполняется, то переход на 4.11
4.7 Вводится P по max (Z-C)=(Z-C)>0 в m+1 строке
4.8 Выводится P по = min=, Xik, lk ?0
4.9 Производится преобразование таблицы
4.10 Переход на 4.4
4.11 Выводится на печать Xопт и Zопт.
5 ВЫЧИСЛИТЕЛЬНАЯ СХЕМА
|
Таблица №3 |
80 |
125 |
0 |
0 |
0 |
||||
|
i |
Базис |
C Базис |
P0 |
C1 |
C2 |
C3 |
C4 |
C5 |
|
|
P1 |
P2 |
P3 |
P4 |
P5 |
|||||
|
1 |
P3 |
0 |
160 |
0.01 |
0.02 |
1 |
0 |
0 |
|
|
2 |
P4 |
0 |
120 |
0.02 |
0.01 |
0 |
1 |
0 |
|
|
3 |
P5 |
0 |
150 |
0.04 |
0.01 |
0 |
0 |
1 |
|
|
m+1 |
zj - cj |
0 |
-80 |
-125 |
0 |
0 |
0 |
||
|
1 |
P3 |
125 |
8000 |
0.5 |
1 |
50 |
0 |
0 |
|
|
2 |
P4 |
0 |
40 |
0.02 |
0 |
-0,5 |
1 |
0 |
|
|
3 |
P2 |
0 |
70 |
0.04 |
0 |
-0,5 |
0 |
1 |
|
|
m+1 |
zj - cj |
1000000 |
-17.5 |
0 |
6250 |
0 |
0 |
||
|
1 |
P3 |
125 |
7000 |
0 |
1 |
54.14 |
0 |
-14.29 |
|
|
2 |
P1 |
0 |
10 |
0 |
0 |
-0.29 |
1 |
-0.43 |
|
|
3 |
P2 |
80 |
2000 |
1 |
0 |
-14.29 |
0 |
28.57 |
|
|
m+1 |
zj - cj |
1035000 |
0 |
0 |
600 |
0 |
500 |
Так как критерии оптимальности выполняются, т. е. Z-C0 то
Хопт.= (2000; 7000; 0; 10; 0)
Zопт = 10350
симплексный планирование производство оптимальный
6 БЛОК-СХЕМА
7 ПРОГРАММА
# include <stdio.h>
# define m 6
# define m 10
main()
{
int v,j,k,kk;
float z[n],x[m][n],zx[n],mv,vv,c[n],t[m],cl[m],rr,xl[m][n];
printf(“Курсовая работа на тему: \n”);
printf(“Выполнил студент группы П-17 Черниченко Николай\n”);
printf(“Эта программа применима для всех задач, решаемых\n”);
printf(“симплексным методом имеющим оптимальный план.\n”);
printf(“С базиса для P0 вводится равным 0.\n”);
printf(“\nВведите x(i,j) по таблицам\n ”);
for (j=0;j<n;j++)
for (i=0;i<m;i++)
{
printf(“x(%d,%d)=”,i+1,j+1);
scanf(“%f”,&[i][j]);
}
printf(“Введите С\n”);
for (j=0;j<n;j++);
{
printf(“С%d=”,j+1);
scanf(“%f”,c[j]);
}
printf(“Введите С базиса \n”);
for (i=0;i<m;i++)
{
printf(“cl%d=”,i+1);
scanf(“%f”,&cl[i]);
}
up:
for(j=0;j<n;j++)
{
z[j]=0;
for(i=0;i<m;i++);
z[j]=z[j]+cl[i]*x[i][j];
zx[j]=z[j]-c[j];
}
min=zx[l];
v=l;
for(j=2;j<n;j++);
if(min>=zx[j]);
{
min=zx[j];
v=j;
}
printf(“\n********************************************************************************”);
for(j=0;j<n;j++)
printf(“P%d”,j);
printf(“\n********************************************************************************”);
for(i=0;i<m;i++);
{
for(j=0;j<n;j++)
{
if((x[i][j]>=-0.0001)&(x[i][j]<0)) x[i][j]=0;
printf(“%6.2f”,xp[i][j]);
}
printf(“\n”);
}
print(“________________________________________________________________________________”);
for(j=0;j<n;j++)
printf(“%6.1f”.zx[j]);
getch();
print(“________________________________________________________________________________”);
printf(“Целевая функция Z0=%6.2f\n”,zx[0]);
print(“________________________________________________________________________________”);
if(zx[v]>=0) goto en;
for(i=0;i<m;i++);
if(x[i][v]==0) x[i][v]=0.0000000001;
for(i=0;i<m;i++);
t[i]=x[i][0]/x[i][v];
k=0;
mv=t[0];
for(i=0;i<m;i++);
if(t[i]>0);
if(mv>=t[i]);
{
mv=t[i];
k=I;
}
cl[k]=c[v];
printf(“Ведущий элемент = %7.2f\n”,x[k][v]);
kk=k;
printf(“Ведущая строка %d\n”,kk+l);
rr=x[kk][v];
for(i=0;i<m;i++);
{
if(i!=kk)
{
vv=x[i][v];
for(j=0;j<n;j++)
xl[kk][j]=x[kk][j]*vv;
for(j=0;j<n;j++)
x[i][j]=x[i][j]-xl[kk][j];
}
}
goto up;
en: getch();
8 ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ
8.1 Ознакомиться с вариантами задания
8.2 Подготовить исходные данные
8.3 Включить ПЭВМ
8.4 Найти на каком диске находятся файлы работы с C\System\C++/exe
8.5 Открыть файл stdio.h с помощью File\Open\<имя файла>
8.6 Откомпилировать программу
8.7 Для её выполнения нажать Run
8.8 Ввести исходные данные задачи
8.9 Оформить протокол решения
9 РЕЗУЛЬТАТЫ СЧЕТА ПО ПРОГРАММЕ
Выполнил Черниченко Николай
Эта программа применима для всех задач, решаемых
Симплексным методом и имеющих оптимальный план.
Р0 следует вводить как X[I,j] в первый столбец.
С базиса для Р0 вводится равным 0.
P0 P1 P2 P3 P4 P5
1.00 2.00 3.00 1.00 0.00 0.00
120.00 8.00 0.00 0.00 1.00 0.00
180.00 0.00 6.00 0.00 0.00 1.00
-15.00 -18.00 0.00 0.00 0.00 0.00
Целевая функция Z0=-18.00
Ведущий элемент = 6.00
Ведущая строка 3
P0 P1 P2 P3 P4 P5
120 2 0 1 0 -1/2
120 8 0 0 1 0
50 0 1 0 0 1/6
540 -15.00 0 0 0 3
Целевая функция Z0=-15
Ведущий элемент = 8
Ведущая строка 2
P0 P1 P2 P3 P4 P5
0 0 0 1 1/4 1/2
15 1 0 0 1/8 1/6
30 0 1 0 0 0
765 1.6 0.00 0.00 1.32 0.00
Целевая функция Z0=765
10 ЭКОНОМИЧЕСКОЕ ОБЪЯСНЕНИЕ РЕЗУЛЬТАТОВ
В результате решения задачи по производству двух типов ремонтных работ, при использовании трех видов сырья, получен оптимальный план:
Хопт=. (15,30,0,0,0,75)
Zопт = 765
Экономический смысл таков:
Ремонтных работ вида А-15 ед;
Ремонтных работ вида В-30 ед.
При этом сырье первого , второго и третьего вида используется полностью.
А сырье 4-го вида ремонтных работ используется не полностью;
Остаток -75 ед.
Максимальная прибыль от выполненных ремонтных работ равна 765 ед.
11 ЗАКЛЮЧЕНИЕ
В результате выполнения курсовой работы закреплены знания по математическим и программным средствам моделирования при решении конкретной производственной задачи.
При выполнении курсовой работы были закреплены навыки нахождения оптимального плана с помощью симплексного метода, а также изучен и применён метод реализации задачи планирования производства
12 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко «Математическое программирование» М. «Высшая школа», 1980г.
С.А. Соколицин «Применение математических методов в экономике и организации машиностроительного производства» Л, «Машиностроение», 1970г.
Методические указания к курсовой работе по дисциплине «Математические методы», Таганрог, ТАК, 2008г.
ЕСПД Схема алгоритмов и программ, данных и систем ГОСТ 19.701- 90
Размещено на Allbest.ru
Подобные документы
Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
контрольная работа [135,3 K], добавлен 01.06.2014Математическая модель планирования производства. Составление оптимального плана производственной деятельности предприятия методом линейного программирования. Нахождение оптимального способа распределения денежных ресурсов в течение планируемого периода.
дипломная работа [8,8 M], добавлен 07.08.2013Нахождение области допустимых значений и оптимумов целевой функции с целью решения графическим методом задачи линейного программирования. Нахождение оптимальных значений двойственных переменных при помощи симплексного метода и теории двойственности.
контрольная работа [116,0 K], добавлен 09.04.2012Построение математических моделей по определению плана выпуска изделий, обеспечивающего максимальную прибыль, с помощью графического и симплексного метода. Построение моделей по решению транспортных задач при применении метода минимальной стоимости.
задача [169,2 K], добавлен 06.01.2012Сущность модифицированного симплексного метода при решении задач линейного программирования. Характеристика подходов к вычислительной схеме симплекс-метода. Использование в экономическом моделировании. Графический способ решения транспортной задачи.
контрольная работа [32,0 K], добавлен 15.03.2016Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
контрольная работа [613,3 K], добавлен 18.02.2014Многошаговые процессы в динамических задачах. Принцип оптимальности и рекуррентные соотношения. Метод динамического программирования. Задачи оптимального распределения средств на расширение производства и планирования производственной программы.
курсовая работа [129,8 K], добавлен 30.12.2010Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Моделирование задачи определения оптимального плана выпуска продукции, вывод ее в канонической форме. Решение задания с помощью надстройки MS Excel "Поиск решения", составление отчетов по устойчивости и результатам. Оптимальная прибыль при заданной цене.
курсовая работа [635,6 K], добавлен 07.09.2011Линейное программирование как инструмент исследования линейных моделей. Основы симплекс-метода. Моделирование экономической ситуации в инструментальном цехе. Применение симплекс-метода для оптимизации плана производства. Применимость линейной модели.
курсовая работа [112,0 K], добавлен 09.12.2014
