Смекни!
smekni.com
Информатика и программирование

Линейное программирование (стр. 6 из 8)

Z=CX →max,

AX=B,

X≥0.

где 0 - нулевая матрица-столбец той же размерности, что и матрица X.

замечание.

Не ограничивая общности, можно полагать, что свободные члены неотрицательны, т.е. b i ≥ 0, гдеi =¯1,m(иначе ограничительные уравнения можно умножить на (-1)).


Пересчитаем таблицу:

Базисные переменные X4 X5 X3 Свободные члены
X1 1/4 -1/2 -1/2 3/4
X2 0 1 1 0
X6 -1/4 -3/2 -3/2 29/4
0-Z 3/4 11/2 7/2 233/4

Эта таблица является последней, по ней читаем ответ задачи.

Найдено оптимальное базисное решение:

При котором Zmax = 233/4= 58,25 ден. ед.

План производства:

X1 =3/4= 0,75; X2 = 0; X3 = 0; X4 = 3; X5 = 0; X6 = 29/4= 7,25

Соответственно по решению, вычисляем:

Z= 3*0,75+7*0+2*0+3+7,25= 24

Z= 24

Ответ поставленной задачи: План выпуска продукции (Z) для получения максимальной прибыли, при том, что сырьё IIвида было израсходовано полностью равен 24 (Z= 24). Из хода решения задачи по условию мы видим, что оценен каждый из видов сырья, используемых для производства продукции.

Блок-схемы основных процедур при решении и программировании задач

Алгоритм программы → Рис. 1. ↓



Рисунок 1 –Алгоритм программы для решения ЗЛП (частный случай)

Программа к поставленной задачи (код программы)

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

Программа определяет:

План выпуска продукции для получения максимальной прибыли.

1. Описание работы программы, листинг программы

1.1 Обоснование выбора языка

Программа для решения данной задачи составлена на языке C++.C++ представляет собой систему программирования. Как любая подобная система,C++ предназначена для разработки программ и имеет две характерные особенности: создаваемые с ее помощью программы могут работать не только под управлением Windows,но и в системе MS-DOS.

C++ представляет собой наиболее полный пакет объектно-ориентированного программирования. Язык прост в применении и базируется на C#,что упрощает создание программ, людям, знакомым с данным языком.

1.2 Описание работы программы

Программа составлена для общего случая. В первую матрицу вводятся ее члены в обычных дробях. Программа переводит эти дроби в десятичные и составляет каноническую форму. Затем происходит процесс формирования первой симплекс таблицы.

Следующим этапом программа начинает составлять итерации, до тех пор пока не будет найдено оптимальное решение (в данном случае составлено 2 итерации).

Программа выводит данные в строку F/

1.3 Листинг программы

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

#include <stdio.h>

#include <string.h>

#include <math.h>

#definePRECISION"%6.2f" // формат вывода дробных чисел

#definePRECISION2 "%.2f" // он же только целая часть любой длины

#defineMAXDIGIT 1000000 // должно быть очень большое число (больше всех)

typedefenum

{

NEXT_ITERATION, // нужно продолжать итерации

PLAN_OPTIMAL, // найден оптимальный опорный план

ODR_BREAK, // ОДР разомкнута

ODR_EMPTY, // ОДР пустая

DUAL_DONE /* первый этап (построение опорного плана) окончен,

переходим к поиску оптим.оп.плана (обычный Симплекс) */

} plan_t;

intcn=0; // длина вектора исходного ур-я

intcnr=0; /* cn, только без членов == 0 (cnr==cn_real)

нужно только для вывода сокращенной таблицы */

float *c = NULL; // исходное ур-е

intm=0, n=0; // размеры матрицы условий

float **a = NULL; // матрица условий

float *b = NULL; // столбец свободных членов матрицы условий

int *base = NULL; // базовые переменные

floatzb=0; // оценки оптимальности b

float *za = NULL; // оценки оптимальности a

intbase_column = -1; // разрешающий столбец

intbase_row = -1; // разрешающая строка

boolfull_table = true; // вид выводимой таблицы: true==полная, false==сжатая

void FreeMem ()

{

delete[] za;

delete[] base;

delete[] b;

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

delete[] a[i];

delete[] a;

delete[] c;

}

bool ReadInput (char *filename)

{

int i,j;

FILE *f = fopen(filename, "r");

if (NULL == f)

return false;

// исходное ур-е

fscanf(f, "%i", &cn);

c = new float [cn];

cnr=cn;

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

{

fscanf(f, "%f", &c[i]);

if (0 == c[i]) cnr--;

}

// матрица условий

fscanf(f, "%i %i", &n, &m);

a = new float* [m];

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

a[i] = new float[n];

b = new float [m];

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

{

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

fscanf(f, "%f", &a[j][i]);

fscanf(f, "%f", &b[j]);

}

// базовые переменные

base = newint [m];

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

{

fscanf(f, "%i", &base[j]);

--base[j];

}

// флаг - полную или сжатую таблицу выводить ?

int flag = 1;

fscanf(f, "%i", &flag);

full_table = flag ? true : false;

fclose(f);

za = new float[n];

// for(i=0;i<n;i++)za[i]=0;// !!! только для отладки !!!

returntrue;

}

// Вычисление оценок оптимальности {za==delta_j[] andzb==Z}

void EvaluationOptimal ()

{

int i,j;

zb=0;

for (i=0; i<n; i++) za[i]=0;

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

{

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

za[i] += c[base[j]]*a[j][i];

zb += c[base[j]]*b[j];

}

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

za[i] -= c[i];

}

// Построение опорного плана (этот этап только в двойственном симплекс-методе)

plan_t BuildPsevdoPlan ()

{

int i,j;

base_column = -1; // разрешающий столбец

base_row = -1; // разрешающая строка

floatacc; // временно: аккумулятор - будет хранить min, max, etc.

acc = 0; // min отрицательное значение b

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

if (b[j] < acc)

{

acc = b[j];

base_row = j;

}

if (-1 == base_row)

return DUAL_DONE;

acc = -MAXDIGIT; // max отношение za котрицат. эл-тамвстроке base_row

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

{

float temp;

if (a[base_row][i] < 0 && (temp = za[i]/a[base_row][i]) > acc)

{

acc = temp;

base_column = i;

}

}

if (-1 == base_column)

return ODR_EMPTY;

returnNEXT_ITERATION;

}

// Проверка опорного плана на оптимальность

plan_t CheckStrongPlan ()

{

int i,j;

float za_min = 0;

base_column = -1; // разрешающийстолбец

base_row = -1; // разрешающая строка

// выбор разрешающего столбца

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

{

if (za[i] >= 0)

continue;

else if (za[i] < za_min)

{

za_min = za[i];

base_column = i;

}

}

if (-1 == base_column)

return PLAN_OPTIMAL;

za_min = MAXDIGIT;

// выбор разрешающей строки

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

{

if (a[j][base_column] > 0)

{

float t = b[j]/a[j][base_column];

if (t < za_min)

{

za_min = t;

base_row = j;

}

}

}

if (-1 == base_row)

return ODR_BREAK;

return NEXT_ITERATION;

}

// Преобразование таблицы по ф-лам Жордана-Гаусса

void JGTransformation (int base_row, int base_column)

{

// проверка на всякий случай: чтобы не было деления на нуль

if (0 == a[base_row][base_column]) return;

base[base_row] = base_column;

int i,j;

float **a2 = new float* [m]; // матрица условий

float *b2 = newfloat [m]; // столбец свободных членов матрицы условий

memcpy(b2,b,m*sizeof(float));

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

{

a2[j] = new float[n];

memcpy(a2[j],a[j],n*sizeof(float));

}

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

{

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

{

if (i == base_column)

{

a2[j][i] = (float) (j == base_row ? 1 : 0);

}

else

{

if (j == base_row)

a2[j][i] = a[j][i]/a[base_row][base_column];

else

a2[j][i] = a[j][i] - a[base_row][i]*a[j][base_column]/

a[base_row][base_column];

}

}

if (j == base_row)

b2[j] = b[j]/a[base_row][base_column];

else

b2[j] = b[j] - b[base_row]*a[j][base_column]/

a[base_row][base_column];

}

memcpy(b,b2,m*sizeof(float));

delete[] b2;

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

{

memcpy(a[j],a2[j],n*sizeof(float));

delete[] a2[j];

}

delete[] a2;

}

// проверка: входит ли номер столбца в число базисных переменных

bool InBase (int num)

{

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

if (num == base[j])

return true;

return false;

}

// вывод линии символов

void Rule (char c, int amount = full_table ? 5+(n+2)*8 : 5+(cnr+1)*8)

{

for (int i=0; i<amount; i++)

printf("%c", c);

printf("&bsol;n");

}

// выводСимплекс-таблицы

void ShowTable ()

{

int i,j;

static int iteration = 0;

printf("[%i]&bsol;n", iteration++);

if (full_table)

// полная таблица

{

Rule('=');

printf("Баз.| | |");

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

printf(PRECISION " |", c[i]);

printf("&bsol;nпер.| Ci | Bi |");

Rule('-', n*8);

printf(" | | |");

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

printf(" x%i |", i+1);

printf("&bsol;n");

Rule('=');

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

{

printf(" x%i |" PRECISION " |" PRECISION " |",

base[j]+1, c[base[j]], b[j]);

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

printf(PRECISION "%c|", a[j][i],

base_column == i && base_row == j ?'*':' ');

printf("&bsol;n");

}

Rule('=');

printf(" Z | --- |" PRECISION " |", zb);

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

printf(PRECISION " |", za[i]);

printf("&bsol;n");

Rule('-');

}

else

// сжатаятаблица

{

Rule('=');

printf("БvС>|");

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

{

if (!InBase(i))

printf(" x%i |", i+1);

}

printf(" Bi |&bsol;n");

Rule('=');

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

{

printf(" x%i |", base[j]+1);

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

{

if (!InBase(i))

printf(PRECISION "%c|", a[j][i],

base_column == i && base_row == j ?'*':' ');

}

printf(PRECISION" |&bsol;n", b[j]);

}

Rule('=');

printf(" Z |");

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

{

if (!InBase(i))

printf(PRECISION " |", za[i]);

}

printf(PRECISION " |&bsol;n", zb);

Rule('-');

}

if (base_column > -1 && base_row > -1)

printf("Разрешающий столбец:%2i&bsol;nРазрешающая строка: %2i&bsol;n&bsol;nX=(",

base_column+1, base_row+1);

else

printf("&bsol;nX=(");

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

{

int basen = -1;

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

if (base[j] == i) {basen = j; break;}

printf(PRECISION2 "%c ", -1==basen?0:b[basen], i!=n-1?',':')');

}

printf("&bsol;nZ=" PRECISION2 "&bsol;n&bsol;n&bsol;n", zb);

}

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

{

if (argc < 2)

{

printf("Missing argument&bsol;n");

return -1;

}

if (!ReadInput(argv[1]))

{

printf("Error open file %s.&bsol;n", argv[1]);

return -1;

}

printf("*** ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД ***&bsol;n&bsol;n");

plan_t plan;

bool dual_done = false;

for (int k=0; k<2*m+1; k++)

{

if (k) JGTransformation(base_row, base_column);

EvaluationOptimal();

if (dual_done)

{

plan = CheckStrongPlan();

}

else

{

plan = BuildPsevdoPlan(); // only in dual-simplex

if (DUAL_DONE == plan)

{

dual_done = true;

plan = CheckStrongPlan();

}

}

ShowTable();

if (NEXT_ITERATION != plan)

{

char *s;

switch (plan)

{

case PLAN_OPTIMAL: s="Опорный план оптимальный"; break;

caseODR_BREAK: s="Область допустимых решений разомкнутая"; break;

caseODR_EMPTY: s="Область допустимых решений пустая"; break;

}

printf("&bsol;n%s.&bsol;n", s);

 
назад
читать дальше
1
2
3
4
5
6
7
8
НАПИШИТЕ НАМ
Copyright © Smekni.com. All rigths reserved.