Задание 5. Задача об оптимальных назначениях

Фирма получила заказ на разработку пяти программных продуктов Z₁,.., Z₅. Эти работы могут выполнить пять программистов P₁, …, Р₅, которым (в силу особенностей их подготовки) требуется разное время на выполнение этих работ. Как следует распределить программистов по работам, чтобы суммарное время выполнения всех работ было наименьшим?

Замечание. Считать, что каждая работа выполняется только одним программистом.

Результаты работы программы.

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

// Приведение матрицы

void privod(BOOL ToMax){

int i, j, umin;

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

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

vmax = vmax > v[i][j]? vmax: v[i][j];

if(ToMax){

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

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

u[i][j] = vmax-v[i][j];

}

else{

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

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

u[i][j] = v[i][j];

}

for(i=0; i< n; i++){ // Приведение по строкам.

umin=u[i][0];

for(j=1; j< n; j++) // Минимум в строке.

umin = umin < u[i][j]? umin: u[i][j];

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

u[i][j]-=umin;

}

for(j=0; j< n; j++){ // Приведение по столбцам.

umin=u[0][j];

for(i=1; i< n; i++) // Минимум в столбце.

umin = umin < u[i][j]? umin: u[i][j];

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

u[i][j]-=umin;

}

}

void mark0(){ // Отмечаем и зачеркиваем нули.

int i, j;

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

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

cross0[i][j]=0;

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

str0[i]=col0[i]=0;

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

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

if(u[i][j]==0)

if(str0[i]==0 & & col0[j]==0){

cross0[i][j]=1;

str0[i]=col0[j]=1;

}

else

cross0[i][j]=-1;

}

int findcouple(int i){

int i1, j=0;

while(cross0[i][j]! =1) j++;

for(i1=0; i1< n; i1++)

// Если ноль зачеркнут и в этой строке еще не были

if(cross0[i1][j]==-1 & &! usestr[i1]){

// Если строка не помечена

if(! str0[i1]){

str0[i1]=1;

cross0[i1][j]=1;

cross0[i][j]=-1;

return 1;

}

else{

usestr[i1]=1;

if(findcouple(i1)){

cross0[i1][j]=1;

cross0[i][j]=-1;

return 1;

}

}

}

return 0;

}

// Нахождение паросочетания.

int upcouple(){

int i, j;

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

usestr[i]=0; // В какой строке побывали.

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

if(! col0[j])

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

if(cross0[i][j]==-1){ // Зачеркнутый ноль в непомеченном столбце.

usestr[i]=1;

if(findcouple(i)){

col0[j]=1;

cross0[i][j]=1;

return 1;

}

else

usestr[i]=0;

}

return 0;

}

// Нахождение максимального паросочетания.

void maxcouple(){

while(upcouple());

}

// Проверка на решенность задачи.

int fin(){

int i;

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

if(! str0[i])

return 0;

return 1;

}

// Нахождение минимальной опоры.

void minsupport(){

int i, j, b;

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

strround[i]=colround[i]=0;

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

strround[i]=1-str0[i];

b=1;

while(b){

b=0;

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

if(strround[i])

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

if(cross0[i][j]==-1)

colround[j]=1;

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

if(colround[j])

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

if(cross0[i][j]==1 & &! strround[i]){

b=1;

strround[i]=1;

}

}

}

// Перестановка нулей.

void rotate0(){

int i, j, min=vmax;

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

if(strround[i])

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

if(! colround[j])

if(min> u[i][j])

min=u[i][j];

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

if(! strround[i])

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

u[i][j]+=min;

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

if(! colround[j])

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

u[i][j]-=min;

}

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

Станция технического обслуживания (СТО) выполняет ремонт и обслуживание автомобилей. В среднем в час на СТО прибывает λ автомобилей. СТО имеет m боксов для ремонта и гараж, в котором могут ожидать обслуживания v автомобилей. Среднее время ремонта автомобиля составляет t часов.

Руководство СТО может выбрать одно из двух решений по развитию, затраты на реализацию которых приблизительно равны:

· построить и оборудовать ещё один бокс для ремонта,

· увеличить гараж для ожидающих ремонта автомобилей ещё на k мест.

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

Результаты работы программы.

Код основной части программы, выполняющий решение.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sto_station

{

class Program

{

static void Main(string[] args)

{

double y=1;

double m=3;

double v=2;

double t=3.5;

double k=3;

Console.WriteLine(" Исходные данные: " + y + " " + m + " " + v + " " + t + " " + k + Environment.NewLine);

Console.WriteLine(" РЕШЕНИЕ");

Console.WriteLine(" По условию задачи, нужно сравнить два варианта функционирования СТО: ");

Console.WriteLine(" а) увеличить значение m до " + Convert.ToString(m + 1));

Console.WriteLine(" б) увеличить v на k мест, т.е. до v=" + Convert.ToString(v + k));

double u;

u = 1 / t;

u = Math.Round(u, 3);

Console.WriteLine(" μ = 1 / t =" + " 1/" + Convert.ToString(t) + " = " + Convert.ToString(u));

double a;

a = y / u;

a = Math.Round(a, 3);

Console.WriteLine(" α = λ / μ = " + Convert.ToString(y) + " /" + Convert.ToString(u) + " = " + Convert.ToString(a));

Console.WriteLine(Environment.NewLine + " РАССМОТРИМ ПЕРВЫЙ ВАРИАНТ");

Console.WriteLine(" Находим вероятность того, что в системе нет заявок: ");

double p0;

double summ1 = 0;

double fact = 1;

summ1 = Math.Pow(a, 0) / 1;

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

{

fact = fact * i;

summ1 = summ1 + ((Math.Pow(a, i)) / fact);

}

double summ2;

summ2 = 0;

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

{

summ2 = summ2 + Math.Pow((a / (m + 1)), r);

}

summ2 = summ2 * Math.Pow(a, m + 1);

fact = 1;

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

{

fact = fact * i;

}

summ2 = summ2 / fact;

p0 = 1 / (summ1 + summ2);

p0 = Math.Round(p0, 3);

Console.WriteLine(" P(0)=" + Convert.ToString(p0));

double p_mv;

p_mv = 0;

p_mv = Math.Pow(a, (m + 1 + v)) * p0 / (Math.Pow(m + 1, v) * fact);

p_mv = Math.Round(p_mv, 3);

Console.WriteLine(" P(m+v)=" + Convert.ToString(p_mv));

double q1;

q1 = 1 - p_mv;

Console.WriteLine(" Относительная пропускная способность составит " + Convert.ToString(q1));

Console.WriteLine(Environment.NewLine + " РАССМОТРИМ ВТОРОЙ ВАРИАНТ");

Console.WriteLine(" Находим вероятность того, что в системе нет заявок: ");

double p0_1;

fact = 1;

summ1 = Math.Pow(a, 0) / 1;

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

{

fact = fact * i;

summ1 = summ1 + ((Math.Pow(a, i)) / fact);

}

fact = 1;

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

{

fact = fact * i;

}

double fact1 = fact;

fact = fact * (m + 1 - a);

p0_1 = 1 / (summ1 + ((Math.Pow(a, m + 1)) * (1 - (Math.Pow(a / (m + 1), v)))) / fact);

p0_1 = Math.Round(p0_1, 5);

Console.WriteLine(" P(0)=" + Convert.ToString(p0_1));

double p_mv_1;

p_mv_1 = Math.Pow(a, (m + 1 + v)) * p0_1 / (Math.Pow(m + 1, v) * fact1);

p_mv_1 = Math.Round(p_mv_1, 3);

Console.WriteLine(" P(m+v)=" + Convert.ToString(p_mv_1));

double q2;

q2 = 1 - p_mv_1;

Console.WriteLine(" Относительная пропускная способность составит " + Convert.ToString(q2) + Environment.NewLine);

if (q1 > q2)

{

Console.WriteLine(" q1> q2, поэтому первый вариант предпочтительнее");

}

if (q1 < q2)

{

Console.WriteLine(" q1< q2, поэтому второй вариант предпочтительнее");

}

if (q1 == q2)

{

Console.WriteLine(" q1=q2, оба варианта оптимальны");

}

Console.ReadKey();

}

}

}

Заключение

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

- разработана управленческая информационная систему для осуществления оптимального руководства компанией;

- решена задача одного станка с помощью решающего правила;

- решена задача двух станков при помощи алгоритма Джонсона;

- решена задача о транспортном предприятии тремя способами (критерий Вальда, Сэвиджа, Гурвица);

- решена задача матричной игры;

- решена задача об оптимальных назначениях с помощью венгерского способа;

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