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

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

Рубрика Экономико-математическое моделирование
Вид курсовая работа
Язык русский
Дата добавления 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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.