Распределительные задачи с однородными реcурсами

Размещено на http://www.allbest.ru/

Содержание

1. Теоретическое введение

2. Этапы решения распределительной задачи

3. Решение задачи

4. Пример решения задачи

Текст программы

1. Теоретическое введение

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

Исходные параметры модели РЗ

1) n - количество исполнителей;

2) m - количество видов выполняемых работ;

3) - запас рабочего ресурса исполнителя () [ед.ресурса];

4) - план по выполнению работы () [ед. работ];

5) - стоимость выполнения работы исполнителем [руб./ед. работ];

6) - интенсивность выполнения работы исполнителем [ед. работ/ед.ресурса].

Искомые параметры модели РЗ

1) - планируемая загрузка исполнителя при выполнении работ [ед. ресурса];

2) - количество работ , которые должен будет произвести исполнитель [ед. работ];

3) - общие расходы на выполнение всего запланированного объема работ [руб.].

Этапы построения модели

I. Определение переменных.

II. Построение распределительной матрицы (см. табл.6.1).

III. Задание ЦФ.

Таблица 1. Общий вид распределительной матрицы

Исполнители,	Работы,	Запас ресурса, ед.ресурса
			…
			…
			…
…	…	…	…	…	…
			…
План, ед.работы			…

Модель РЗ

;	1

Рис

где - это количество работ j-го вида, выполненных i-м исполнителем.

2. Этапы решения распределительной задачи

I. Преобразование РЗ в ТЗ:

1) выбор базового ресурса и расчет нормированных производительностей ресурсов :

;	2

2) пересчет запаса рабочего ресурса исполнителей :

[ед. ресурса];	3

3) пересчет планового задания :

;	4

4) пересчет себестоимостей работ:

.	5

II. Проверка баланса пересчитанных параметров и построение транспортной матрицы.

III. Поиск оптимального решения ТЗ.

IV. Преобразование оптимального решения ТЗ в оптимальное решение РЗ , причем переход выполняется по формуле (6.6)

[ед. ресурса],	6

где и - соответственно элементы решения РЗ и ТЗ.

V. Определение количества работ , соответствующее оптимальному решению РЗ :

.	7

VI. Определение ЦФ распределительной задачи согласно (6.1).

3. Решение задачи

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

· производительности станков по каждому виду ткани, м/ч

;

себестоимость тканей, руб./м

;

фонды рабочего времени станков (): 90, 220, 180 ч;

· планируемый объем выпуска тканей (): 1200, 900, 1800, 840 м.

Требуется распределить выпуск ткани по станкам с целью минимизации общей себестоимости производства ткани.

Решение

Пусть переменные - это время, в течение которого i-й станок будет выпускать j-ю ткань. Сведем исходные данные задачи в распределительную таблицу (табл.6.2).

Таблица 2 Распределительная матрица

Станки	Ткани	Фонд времени , ч
	В1	В2	В3	В4
А1	2 () () 24	1 30	3 18	1 42	90
А2	3 12	2 15	4 9	1 21	220
А3	6 8	3 10	5 6	2 14	180
Объем выпуска , м	1200	900	1800	840

ЦФ имеет смысл себестоимости выпуска запланированного количества ткани всех видов



Ограничения имеют вид

Преобразуем РЗ в ТЗ, т.е. представим исходную задачу в виде, когда ткани производит только один станок - базовый и все параметры задачи согласуем с его характеристиками. В качестве базового можно выбирать любой из станков. Мы выберем станок с максимальной производительностью, т.е. . По формуле (6.2) определим производительности станков , нормированные относительно производительности базового станка:

;

;

.

распределительный задача измерение

Таким образом, базовый станок работает в два раза быстрей второго станка и в три раза быстрей третьего.

Пересчитаем фонды времени станков по формуле (6.3):

[ч]; [ч]; [ч].

Из этих величин следует, что тот объем работ, который второй станок выполняет за свой фонд времени 220 ч базовый станок сможет выполнить за 110 ч. Аналогично объем работ, который третий станок выполняет за 180 ч базовый выполнит за 60 ч.

Пересчитаем плановое задание по формуле (6.4):

[ч]; [ч]; [ч]; [ч].

Отсюда следует, что план выпуска первого вида ткани базовый станок выполнит за 50 ч, второго вида - за 30 ч и т.д.

Пересчет себестоимостей производим по формуле (6.5), например:

[руб./ч]; [руб./ч]; [руб./ч].

В полученной ТЗ условие баланса (4.2) не выполняется, т.к. суммарный фонд времени станков больше, чем это необходимо для выполнения плана по выпуску всех тканей (260 ч > 200 ч). Введем фиктивный столбец и запишем все пересчитанные параметры РЗ в транспортную матрицу (см. табл.6.3). Фиктивные тарифы для упрощения приравняем к нулю.

Таблица 3.Транспортная матрица задачи №1

Станки	Ткани	Фонд времени , ч
	В1	В2	В3	В4	ВФ
А1	48	30	54	42	0	90
А2	72	60	72	42	0	110
А3	144	90	90	84	0	60
Объем выпуска , ч	50	30	100	20	60

Руководство для использования

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

Рис

После ввода коэффициентов производительностей станков необходимо ввести производительность первого станка по выпуску всех видов тканей:



Рис

Затем на экране появится расчет производительностей остальных станков основанных на знании коэффициентов производительностей:

Рис

Затем необходимо ввести себестоимость производства каждого вида ткани на каждом станке:

Рис

Затем вводятся фонды рабочего времени и планируемые объемы выпуска:

Рис

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

Рис

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

1. Стивен Прата, «Язык программирования С++».

2. Б. М. Владимирский, А. Б. Горстко, Я. М. Ерусалимский, «Математика».

3. Материал с математического портала www.allmath.ru.

4. Подбельский В. В. «Язык С++».

5. Скотт Мейерс. «Наиболее эффективное использование С++».

Текст программы

//---------------------------------------------------------------------------

#include <vcl.h>

#include <iostream.h>

#include <conio.h>

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

int main(int argc, char* argv[])

{

int n, m, t;

float l[10][10], c[10][10], a[10], b[10];

float l1[10], max;

cout<<"Vvedite kolichestvo stankov: ";

cin>>n;

cout<<"Vvedite kolichestvo tipov vipuskaemoy tkani: ";

cin>>m;

cout<<"\n";

for (int i=1; i<=n; i++)

{

cout<<"Vvedite koeffitsient proizvoditelnosti "<<i<<"-go stanka: ";

cin>>l1[i];

}

cout<<"\n";

clrscr();

for (int j=1; j<=m; j++)

{

cout<<"Vvedite proizvoditelnost 1-go stanka\

\npo "<<j<<"-mu vidu tkani: ";

cin>>l[1][j];

}

clrscr();

cout<<"\n";

for (int i=2; i<=n; i++)

{

cout<<"\n";

for (int j=1; j<=m; j++)

{

l[i][j]=l[1][j]/(l1[1]/l1[i]);

cout<<"Proizvoditelnost "<<i<<"-go stanka\

\npo "<<j<<"-mu vidu tkani (m/ch): "<<l[i][j]<<endl;

}

}

getch();

clrscr();

cout<<"\n";

for (int i=1; i<=n; i++)

{

cout<<"\n";

for (int j=1; j<=m; j++)

{

cout<<"Vvedite sebestoimost "<<j<<"-go vida tkani\

\nna "<<i<<"-m stanke (rub/m): ";

cin>>c[i][j];

}

}

getch();

clrscr();

cout<<"\n";

for (int i=1; i<=n; i++)

{

cout<<"Vvedite fond rabochego vremeni "<<i<<"-go stanka (ch): ";

cin>>a[i];

}

cout<<"\n";

for (int j=1; j<=m; j++)

{

cout<<"Vvedite planiruemiy obyem vipuska "<<j<<"-y tkani (m): ";

cin>>b[j];

}

clrscr();

float aL[10];

for (int i=1; i<=n; i++)

{

aL[i]=1/(l1[1]/l1[i]);

// cout<<aL[i]<<" ";

}

int a1[10];

for (int i=1; i<=n; i++)

{

a1[i]=aL[i]*a[i];

// cout<<a1[i]<<" ";

}

cout<<"\n";

int b1[10];

for (int j=1; j<=m; j++)

{

b1[j]=b[j]/l[1][j];

// cout<<b1[j]<<" ";

}

cout<<"\n";

int c1[10][10];

for (int i=1; i<=n; i++)

for (int j=1; j<=m; j++)

c1[i][j]=c[i][j]*l[1][j];

clrscr();

/*int x=0, y=0;

for (int i=1; i<=n; i++)

{

x=1;

y++;

for (int j=1; j<=m; j++)

{

gotoxy(x+=5,y);

cout<<c1[i][j];

}

} */

int xs[10][10];

int matr[10][10];

int min=xs[1][1];

int p, q;

for (int i=1; i<=n; i++)

for (int j=1; j<=m; j++)

matr[i][j]=0;

int s1=0;

for (int i=1; i<=n; i++)

s1=s1+a1[i];

int s2=0;

for (int j=1; j<=m; j++)

s2=s2+b1[j];

if (s1>s2)

{

for (int i=1; i<=n; i++)

for (int j=1; j<=m; j++)

xs[i][j]=c1[i][j];

int j=m+1;

for (int i=1; i<=n; i++)

xs[i][j]=0;

b1[m+1]=s1-s2;

// ----------------

while (min!=10000)

{

min=10000;

for (int i=1; i<=n; i++)

for (int j=1; j<=m+1; j++)

if (xs[i][j]<min)

{

min=xs[i][j];

p=i;

q=j;

}

if ((b[q]==0) || (a[p]==0))

xs[p][q]=10000;

else

if (a[p]>b[q])

{

matr[p][q]=b[q];

a[p]=a[p]-b[q];

b[q]=0;

xs[p][q]=10000;

}

else

{

matr[p][q]=a[p];

b[q]=b[q]-a[p];

a[p]=0;

xs[p][q]=10000;

}

}

// ----------------

}

else if (s1<s2)

{

for (int i=1; i<=n; i++)

for (int j=1; j<=m; j++)

xs[i][j]=c1[i][j];

int i=n+1;

for (int j=1; j<=m; j++)

xs[i][j]=0;

a1[n+1]=s2-s1;

// ----------------

while (min!=10000)

{

min=10000;

for (int i=1; i<=n+1; i++)

for (int j=1; j<=m; j++)

if (xs[i][j]<min)

{

min=xs[i][j];

p=i;

q=j;

}

if ((b[q]==0) || (a[p]==0))

xs[p][q]=10000;

else

if (a[p]>b[q])

{

matr[p][q]=b[q];

a[p]=a[p]-b[q];

b[q]=0;

xs[p][q]=10000;

}

else

{

matr[p][q]=a[p];

b[q]=b[q]-a[p];

a[p]=0;

xs[p][q]=10000;

}

}

// ----------------

}

else

for (int i=1; i<=n; i++)

for (int j=1; j<=m; j++)

xs[i][j]=c1[i][j];

// ----------------

while (min!=10000)

{

min=10000;

for (int i=1; i<=n; i++)

for (int j=1; j<=m; j++)

if (xs[i][j]<min)

{

min=xs[i][j];

p=i;

q=j;

}

if ((b[q]==0) || (a[p]==0))

xs[p][q]=10000;

else

if (a[p]>b[q])

{

matr[p][q]=b[q];

a[p]=a[p]-b[q];

b[q]=0;

xs[p][q]=10000;

}

else

{

matr[p][q]=a[p];

b[q]=b[q]-a[p];

a[p]=0;

xs[p][q]=10000;

}

}

// ----------------

/*int x=0, y=0;

for (int i=1; i<=n; i++)

{

x=1;

y++;

for (int j=1; j<=m+1; j++)

{

gotoxy(x+=5,y);

cout<<xs[i][j];

}

}

cout<<endl;

for (int j=1; j<=m+1; j++)

cout<<" "<<b1[j]; */

cout<<"Reshenie: skolko metrov dolzhen proizvodit kakoy tkani kazhdiy stanok\

\n(stroki - stanki, stolbtsi - vidi tkaney)";

int x=0, y=0;

for (int i=1; i<=n; i++)

{

x=1;

y++;

for (int j=1; j<=m; j++)

{

gotoxy(x+=5,y);

cout<<matr[i][j];

}

}

getch();

return 0;

}

//---------------------------------------------------------------------------

Размещено на Allbest.ru