PDA

Դիտել ողջ տարբերակը : Սիմպլեքս մեթոդի իրականացումը C++ լեզվով



Արիացի
26.12.2008, 21:59
Այս տարի պիտի քննություն հանձնեմ "Գործողությունների հետազոտում" առարկայից: 20-ից 8 բալը սիմպլեքս մեթոդի իրականացումն է C++-ով: Ձեզ եմ ներկայացնում իմ գրած ծրագիրը, որը լուծում է կանոնական տեսքի մինիմում գծային ծրագրավորման խնդիրը: Ուրախ կլինեմ լսել ձեր կարծիքները: Եթե ինչ-որ մեկին exe-ն ա պետք, ասեք ինձ, կուղարկեմ, չնայած դուք էլ կարաք կոմպիլյացիա անել: Ստուգել եմ, անցնում ա Linux-ի տակ, և Windows-ով Visual2005-ի տակ:
Ուրեմն երեք հատ ֆայլ է.
1. simplex_engine.hpp

#ifndef SIMPLEX_ENGINE
#define SIMPLEX_ENGINE

#include <map>
#include <vector>
#include <valarray>

class simplex_engine
{
public:
typedef unsigned index;
typedef std::vector<std::valarray<double> > matrix;
typedef std::valarray<double> row;
typedef std::valarray<double> column;

private:
/**
* Initial data
*/
const index m_length;
const index m_height;
matrix m_matrix;
row m_result;
column m_condition;

public:
index get_length()const;
index get_height()const;

public:
simplex_engine(index height, index length);
~simplex_engine();

public:
void fill_initial_data();

public:
const matrix& get_table()const;

private:
/**
* Solution data
*/
row m_solution;
std::vector<index> m_indices;
matrix m_table;
public:
enum final_state {
not_finished,
does_not_exist,
finished
};
private:
mutable final_state m_finish;

public:
final_state get_finished() const;

private:
index find_positive_column() const;
index find_minimal_row(index) const;
void fill_controlled_row();

public:
void initialize_engine();
void next_step();
double get_current_value() const;
row get_current_solution() const;
};

#endif

2. simplex_engine.cpp

#include "simplex_engine.hpp"

#include <iostream>

simplex_engine::index simplex_engine::get_height() const
{
return m_height;
}

simplex_engine::index simplex_engine::get_length() const
{
return m_length;
}

simplex_engine::simplex_engine(index height, index length)
:m_height(height)
,m_length(length)
,m_matrix(m_height)
,m_condition(m_height)
,m_result(m_length)
,m_solution(m_length)
,m_table(m_height + 1)
,m_finish(not_finished)
,m_indices(m_height)
{
row tmp(m_length);
for(index i = 0; i < m_length; ++i) {
tmp[i] = 0;
}
for(index i = 0; i < m_height; ++i) {
m_matrix[i] = tmp;
}
row tmp1(m_length + 1);
for(index i = 0; i <= m_length; ++i) {
tmp1[i] = 0;
}
for(index i = 0; i < m_height + 1; ++i) {
m_table[i] = tmp1;
}
}

simplex_engine::~simplex_engine()
{
}

void simplex_engine::fill_initial_data()
{
double val;
std::cout << "Inserting matrix" << std::endl;
for(index i = 0; i < m_height; ++i) {
for(index j = 0; j < m_length; ++j) {
std::cout << "A[" << i << "][" << j << "]=";
std::cin >> val;
m_matrix[i][j] = val;
}
}
std::cout << std::endl << "Inserting condition vector" << std::endl;
for(index i = 0; i < m_height; ++i) {
std::cout << "b[" << i << "]=";
std::cin >> val;
m_condition[i] = val;
}
std::cout << std::endl << "Inserting result vector" << std::endl;
for(index j = 0; j < m_length; ++j) {
std::cout << "c[" << j << "]=";
std::cin >> val;
m_result[j] = val;
}
}

const simplex_engine::matrix& simplex_engine::get_table()const
{
return m_table;
}

simplex_engine::final_state simplex_engine::get_finished() const
{
return m_finish;
}

void simplex_engine::fill_controlled_row()
{
for(index i = 0; i < m_height; i++) {
m_table[m_height] += m_table[i] * m_result[m_indices[i]];
}
for(index j = 0; j < m_length; j++) {
m_table[m_height][j] -= m_result[j];
}
}

void simplex_engine::initialize_engine()
{
simplex_engine* s = new simplex_engine(m_height, m_length + m_height);
for(index i = 0; i < m_height; i++) {
s->m_indices[i] = m_length + i;
s->m_result[m_length + i] = 1;
s->m_condition[i] = m_condition[i];
}
for(index j = 0; j < m_length; j++) {
s->m_result[j] = 0;
}
for(index i = 0; i < m_height; i++) {
for(index j = 0; j < m_length; j++) {
s->m_table[i][j] = m_matrix[i][j];
}
for(index j = m_length; j < m_length + m_height; j++) {
s->m_table[i][j] = static_cast<double>(i == j - m_length);
}
s->m_table[i][m_length + m_height] = m_condition[i];
}
s->fill_controlled_row();
while(s->get_finished() == not_finished) {
s->next_step();
}
if(s->get_table()[m_height][m_length + m_height] != 0) {
m_finish = does_not_exist;
return;
}
for(index i = 0; i < m_height; i++) {
m_indices[i] = s->m_indices[i];
}
for(index i = 0; i < m_height; i++) {
for(index j = 0; j < m_length; j++) {
m_table[i][j] = s->m_table[i][j];
}
m_table[i][m_length] = s->m_table[i][m_length + m_height];
}
fill_controlled_row();
}

simplex_engine::index simplex_engine::find_positive_column() const
{
index i = 0;
for(; i < m_length; i++) {
if(m_table[m_height][i] > 0) {
return i;
}
}
return i;
}

simplex_engine::index simplex_engine::find_minimal_row(index j) const
{
index ret = 0;
index i = 0;
while(m_table[i][j] <= 0 && i != m_height) {
i++;
}
if(i == m_height) {
m_finish = does_not_exist;
return i;
}
double min = m_table[i][m_length]/m_table[i][j];
ret = i++;
for(; i < m_height; i++) {
if(m_table[i][j] > 0 && m_table[i][m_length] / m_table[i][j] < min) {
min = m_table[i][m_length] / m_table[i][j];
ret = i;
}
}
return ret;
}

void simplex_engine::next_step()
{
index j = find_positive_column();
if(j == m_length) {
m_finish = finished;
return;
}
index i = find_minimal_row(j);
if(i == m_height) {
return;
}
m_indices[i] = j;
double koef = m_table[i][j];
m_table[i] /= koef;
for(index i1 = 0; i1 <= m_height; i1++) {
if(i1 == i) {
continue;
}
row tr(m_length);
for(index j1 = 0; j1 <= m_length; j1++) {
tr[j1] = m_table[i1][j1] - m_table[i][j1] * m_table[i1][j];
}
for(index j1 = 0; j1 <= m_length; j1++) {
m_table[i1][j1] = tr[j1];
}
}
}

double simplex_engine::get_current_value() const
{
return m_table[m_height][m_length];
}

simplex_engine::row simplex_engine::get_current_solution() const
{
row tmp(m_length);
for(index i = 0; i < m_length; i++) {
tmp[i] = 0;
}
for(index i = 0; i < m_height; i++) {
tmp[m_indices[i]] = m_table[i][m_length];
}
return tmp;
}

3. main.cpp

#include "simplex_engine.hpp"

#include <iostream>

int main()
{
simplex_engine::index h, l;
std::cout << "Insert height: ";
std::cin >> h;
std::cout << "Insert length: ";
std::cin >> l;
simplex_engine s(h, l);
s.fill_initial_data();
s.initialize_engine();
while(s.get_finished() == simplex_engine::not_finished) {
s.next_step();
}
if(s.get_finished() == simplex_engine::does_not_exist) {
std::cout << "Solution doesn't exist" << std::endl;
return 1;
}
std::cout << "Problem solved!!!!" << std::endl;
std::cout << "Value: " << s.get_current_value() << std::endl;
std::cout << "Solution: " << std::endl;
simplex_engine::row r = s.get_current_solution();
for(simplex_engine::index i = 0; i < r.size(); i++) {
std::cout << r[i] << "\t";
}
std::cout << std::endl;
return 0;
}

Լեռնցի
08.01.2009, 03:26
Լավ կլիներ, որ ակումբում գիտական քննարկումներն էլ ակտիվ լինեն, ընդհանուր ինտելեկտն ավելի բարձր կլինի...
հա ի դեպ, լավ էլ աշխատում ա, ժողովուրդ ջան, եթե կիրառական եք սովորում, պատրաստի ռեֆերատ ա....:)