Нахождение оптимального плана производства двух типов ремонтных работ с помощью симплексного метода

Нахождение оптимального плана производства двух типов ремонтных работ с помощью симплексного метода

ВВЕДЕНИЕ

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

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

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

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

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

В частности:

-       симплексный метод,

-       метод искусственного базиса,

-       двойственный симплексный метод,

-       графический метод.

В данной курсовой работе используется симплексный метод, задача линейного программирования реализуется на ЭВМ, используя средства ЯП Pascal для решения задач оптимизации.

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

Небольшая фирма производит два тина подшипников А и В, каждый из которых должен быть использован на трех станках, а именно на токарном, шлифовальном и сверлильном.

Время, требуемое для каждой из стадий производственного процесса, приведена в табл.1.

Таблица1

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

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

Математическая модель в общем виде:

Вводятся обозначения:- тип подшибников;- виды станков;_ij - норма расхода , i-го вида сырья на j вид ремонтных работ_i - общее количество сырья i-го вида;_j - прибыль от одного ремонта j - го вида;_j - выпуск ремонтных работ j-го вида;- максимальная прибыль от выпуска ремонтных работ.

Математическая модель данной ЗЛП:

при ограничениях:

Модель необходимо привести к каноническому виду, введем дополнительные переменные:x3,x4,x5,x6, а в целевую функцию они войдут с нулевыми коэффициентами.

Тогда модель примет вид

при ограничениях

3 МЕТОД РЕАЛИЗАЦИИ МОДЕЛИ

Поставлена задача линейного программирования. Найти максимальное значение функции

при ограничениях

Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов. Через конечное число шагов линейная форма достигает max или min.

Заполняется исходная таблица. После чего производится вычисления в последовательности:

·        Подсчитывается  и определяется, не является ли рассматриваемый план оптимальным, т.е. не выполняется ли для всех x условие: 0

·        Если для некоторого j значение >0, то выбирается вектор, который может быть введен в базис. Для этого разыскивается какое-нибудь j, для которого max()=>0, тогда P- вводится в базис.

; : j=1,2,…,n

·        Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: q = min= для всех X>0 , тогда P- исключается из базиса.

·        Если все X< 0, то линейная форма неограниченна снизу.

·        После выделения направляющей строки и направляющего столбца, таблица преобразуется по формуле полного исключения.

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

Таблица №2

АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

4.1 Вводятся коэффициенты a,b,c

.3 Находится базис

.4 Находится опорный план

.5 Вычисляется Z-C в m+1 строке

.6 Проверяется условие Z-C≤0 в m+1 строке, если выполняется, то переход на 4.11

.7 Вводится P по max (Z-C)=(Z-C)>0 в m+1 строке

.8 Выводится P по q = min=, X_{ik, lk} ≥0

.9 Производится преобразование таблицы

.10 Переход на 4.4

.11 Выводится на печать Xопт и Zопт.

ВЫЧИСЛИТЕЛЬНАЯ СХЕМА

Так как критерии оптимальности выполняются, т. е. Z-C0 то

Х_опт.= (2000; 7000; 0; 10; 0)_опт = 10350

симплексный планирование производство оптимальный

6 БЛОК-СХЕМА

# include <stdio.h>

# define m 6

# define m 10()

{v,j,k,kk;z[n],x[m][n],zx[n],mv,vv,c[n],t[m],cl[m],rr,xl[m][n];

printf(“Курсовая работа на тему: \n”);(“Выполнил студент группы П-17 Черниченко Николай\n”);(“Эта программа применима для всех задач, решаемых\n”);(“симплексным методом имеющим оптимальный план.\n”);(“С базиса для P0 вводится равным 0.\n”);(“\nВведите x(i,j) по таблицам\n ”);

for (j=0;j<n;j++)(i=0;i<m;i++)

{(“x(%d,%d)=”,i+1,j+1);(“%f”,&[i][j]);

}(“Введите С\n”);(j=0;j<n;j++);

{(“С%d=”,j+1);(“%f”,c[j]);

}(“Введите С базиса \n”); (i=0;i<m;i++)

{(“cl%d=”,i+1);(“%f”,&cl[i]);

}:(j=0;j<n;j++)

{[j]=0;(i=0;i<m;i++);[j]=z[j]+cl[i]*x[i][j];[j]=z[j]-c[j];

}=zx[l];=l;(j=2;j<n;j++);(min>=zx[j]);

{=zx[j];=j;

}(“\n********************************************************************************”);(j=0;j<n;j++)(“P%d”,j);(“\n********************************************************************************”);(i=0;i<m;i++);

{(j=0;j<n;j++)

{((x[i][j]>=-0.0001)&(x[i][j]<0)) x[i][j]=0;(“%6.2f”,xp[i][j]);

}(“\n”);

}(“________________________________________________________________________________”);(j=0;j<n;j++)(“%6.1f”.zx[j]);();(“________________________________________________________________________________”);(“Целевая функция Z0=%6.2f\n”,zx[0]);(“________________________________________________________________________________”);(zx[v]>=0) goto en;(i=0;i<m;i++);(x[i][v]==0) x[i][v]=0.0000000001;(i=0;i<m;i++);[i]=x[i][0]/x[i][v];=0;=t[0];(i=0;i<m;i++);(t[i]>0);(mv>=t[i]);

{=t[i];=I;

}[k]=c[v];

printf(“Ведущий элемент = %7.2f\n”,x[k][v]);=k;(“Ведущая строка %d\n”,kk+l);

rr=x[kk][v];(i=0;i<m;i++);

{(i!=kk)

{=x[i][v];(j=0;j<n;j++)[kk][j]=x[kk][j]*vv;(j=0;j<n;j++)[i][j]=x[i][j]-xl[kk][j];

}

}up;: getch();

ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

.1 Ознакомиться с вариантами задания

.2 Подготовить исходные данные

.3 Включить ПЭВМ

.4 Найти на каком диске находятся файлы работы с C\System\C++/exe

.5 Открыть файл stdio.h с помощью File\Open\<имя файла>

.6 Откомпилировать программу

.7 Для её выполнения нажать Run

.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

.00 8.00 0.00 0.00 1.00 0.00

.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

8 0 0 1 0

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

1 0 0 1/8 1/6

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)_опт = 765

Экономический смысл таков:

Ремонтных работ вида В-30 ед.

При этом сырье первого , второго и третьего вида используется полностью.

А сырье 4-го вида ремонтных работ используется не полностью;

Остаток -75 ед.

Максимальная прибыль от выполненных ремонтных работ равна 765 ед.

11 ЗАКЛЮЧЕНИЕ

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

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

12 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

·   Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко «Математическое программирование» М. «Высшая школа», 1980г.

·   С.А. Соколицин «Применение математических методов в экономике и организации машиностроительного производства» Л, «Машиностроение», 1970г.

·   Методические указания к курсовой работе по дисциплине «Математические методы», Таганрог, ТАК, 2008г.

·   ЕСПД Схема алгоритмов и программ, данных и систем ГОСТ 19.701- 90