Применение симплекс-метода для решения экономических задач

#include "stdafx.h"
#include "simplex.h"
 
int main()
{
    setlocale(LC_ALL, "Russian");
    simplex *ud = new simplex;
    ud->get_data_from_user();
    ud->init();
    ud->gen_plane();
    return 0;
}

#include "stdafx.h"
#include <iostream> 
#include "cmath" 
#include <fstream> 
#include <sstream> 
#include <string> 
#include "user_data.h" 
#include "simplex.h" 
using std::cout; 
using std::endl; 
void simplex::init() 
{ 
    int i, j; 
    func = 0; 
    sv = new double *[num_l]; 
    for (i = 0; i < num_l; i++) 
        sv[i] = new double [num_v * 2]; 
    for (i = 0; i < num_l; i++) { 
        for (j = 0; j < num_v; j++) 
            sv[i][j] = system[i][j]; 
        for (; j < num_v * 2; j++) 
            if (i + num_v == j) 
                if (way) 
                    sv[i][j] = 1; 
                else 
                    sv[i][j] = -1; 
            else 
                sv[i][j] = 0; 
    } 
    istr = new double [num_v * 2]; 
    bv = new double *[num_l]; 
    for (i = 0; i < num_l; i++) { 
        bv[i] = new double [2]; 
        bv[i][0] = i + num_v; 
        bv[i][1] = fm[i]; 
    } 
    for (i = 0; i < num_v * 2; i++) 
        if (i < num_v) 
            istr[i] = function[i] * -1; 
        else 
            istr[i] = 0; 
    i_lcol = 0; 
    for (i = 0; i < num_v * 2 - 1; i++) { 
        if (istr[i] < 0) 
            if (fabs(istr[i + 1]) > fabs(istr[i])) 
                i_lcol = i + 1; 
    } 
    th = new double [num_l]; 
    for (i = 0; i < num_l; i++) 
        th[i] = bv[i][1] / sv[i][i_lcol]; 
    i_lrow = 0; 
    for (i = 0; i < num_l - 1; i++) 
        if (th[i] > th[i + 1]) 
            i_lrow = i + 1; 
    alm = sv[i_lrow][i_lcol]; 
    print_result_to_file(0); 
} 
bool simplex::plane_is_valid() 
{ 
    int i; 
    bool result = true; 
    if (way) 
        for (i = 0; i < num_v * 2; i++) 
            if (istr[i] < 0) { 
                result = false; 
                break; 
            } 
    if (!way) 
        for (i = 0; i < num_v * 2; i++) 
            if (istr[i] >= 0) { 
                result = false; 
                break; 
            } 
    return result; 
} 
bool simplex::function_is_undefined() 
{ 
    int i; 
    for (i = 0; i < num_l; i++) 
        if (th[i] < 0) { 
            return false; 
        } 
    return true; 
} 
void simplex::gen_plane() 
{ 
    int i, j, it_num = 0; 
    double A, B; 
    while (!plane_is_valid() && function_is_undefined()) { 
    A = bv[i_lrow][1]; 
    B = istr[i_lcol]; 
    func -= A * B / alm; 
    double *tmp_bv = new double [num_l]; 
    bv [i_lrow][0] = i_lcol; 
    A = bv[i_lrow][1]; 
    for (i = 0; i < num_l; i++) { 
        B = sv[i][i_lcol]; 
        tmp_bv[i] = bv[i_lrow][1]; 
        if (i != i_lrow) 
            tmp_bv[i] = bv[i][1] - A * B / alm; 
        else 
            tmp_bv[i] /= alm; 
    } 
    for (i = 0; i < num_l; i++) 
        bv[i][1] = tmp_bv[i]; 
    double *tmp_istr = istr; 
    B = istr[i_lcol]; 
    for (i = 0; i < num_v * 2; i++) { 
        A = sv[i_lrow][i]; 
        tmp_istr[i] = istr[i] - A * B / alm; 
    } 
    istr = tmp_istr; 
    double **tmp_sv = new double *[num_l]; 
    for (i = 0; i < num_l; i++) 
        tmp_sv[i] = new double [num_v * 2]; 
    for (i = 0; i < num_l; i++) 
        for (j = 0; j < num_v * 2; j++) { 
            tmp_sv[i][j] = sv[i][j]; 
            A = sv[i_lrow][j]; 
            B = sv[i][i_lcol]; 
            if (i == i_lrow) 
                tmp_sv[i][j] /= alm; 
            else 
                tmp_sv[i][j] = sv[i][j] - A * B / alm; 
        } 
    sv = tmp_sv; 
    i_lcol = 0; 
    for (i = 0; i < num_l; i++) 
        th[i] = bv[i][1] / sv[i][i_lcol]; 
    i_lrow = 0; 
    for (i = 0; i < num_l -1; i++) 
        if (th[i] > th[i + 1]) 
            i_lrow = i + 1; 
        alm = sv[i_lrow][i_lcol]; 
        it_num++; 
        print_result_to_file(it_num); 
    } 
    if (!function_is_undefined()) 
            cout << "Целевая фукнция не ограничена, данная задача решений не имеет" << endl; 
    else { 
        cout << "f(x) = " << func << "" << endl; 
        for (i = 0; i < num_l; i++) { 
            cout << "x" << bv[i][0] + 1 << " = " << bv[i][1] << endl; 
        } 
        cout << "Все вычисления были записаны в файл table.txt" << endl; 
    } 
} 
void simplex::print_result_to_file(int it_num) 
{ 
    int i, j; 
    if (!it_num) { 
    table << "Задана целевая функция:" << endl; 
    std::stringstream f_x; 
    f_x << "f(x) = "; 
    for (i = 0; i < num_v; i++) { 
        if (!i) 
            f_x << function[i] << "x" << i + 1 << " "; 
        else { 
            if (function[i] < 0) 
                f_x << "- " << fabs(function[i]) << "x" << i + 1 << " "; 
            if (function[i] > 0) 
                f_x << "+ " << function[i] << "x" << i + 1 << " "; 
        } 
    } 
    std::string minmax; 
    if (way) 
        minmax = "max"; 
    else 
        minmax = "min"; 
    f_x << "=> " << minmax << "" << endl; 
    table << f_x.str(); 
    table << "И система ограничений:" << endl; 
    std::stringstream math_sys; 
    std::string math_sign; 
    for (i = 0; i < num_l; i++) { 
        for (j = 0; j < num_v; j++) { 
            if (!j) 
                math_sys << system[i][j] << "x" << j + 1 << " "; 
            else 
                if (system[i][j] == 1) 
                    if (!j) 
                        math_sys << "x" << j + 1 << " "; 
                    else 
                        math_sys << "+ x" << j + 1 << " "; 
                else 
                    if (system[i][j] == -1) 
                    if (!j) 
                        math_sys << "-x" << j + 1 << " "; 
                    else 
                        math_sys << "- x" << j + 1 << " "; 
                    else { 
                        if (system[i][j] < 0) 
                            math_sys << "- " << fabs(system[i][j])<< "x" << j + 1 << " "; 
                        else 
                            math_sys << "+ " << system[i][j] << "x" << i + 1 << " "; 
                        if (!sign[i]) 
                                math_sign = "<="; 
                        if (sign[i] == 1) 
                            math_sign = "="; 
                         if (sign[i] == 2) 
                            math_sign = ">="; 
                } 
        } 
        math_sys << math_sign << " " << fm[i]; 
        math_sys << endl; 
    } 
    std::string min_or_max; 
    if (way) 
        min_or_max = "максимум"; 
    else 
        min_or_max = "минимум"; 
    table << math_sys.str() << endl; 
    table << "Решим данную задачу на " << min_or_max << " методом симплексных таблиц.Построим первый опорный план:" << endl; 
    } 
    for (i = 0; i < num_l; i++) { 
        table << "x" << bv[i][0] + 1 << "    " << bv[i][1] << "    "; 
        for (j = 0; j < num_v * 2; j++) 
            table << sv[i][j] << "    "; 
        if (!plane_is_valid()) 
            table << th[i]; 
        table << "" << endl; 
    } 
    table << "f(x)    " << func << "    "; 
    for (i = 0; i < num_v * 2; i++) 
        table << istr[i] << "    "; 
    table << ""; 
    if (plane_is_valid()) { 
        if (plane_is_valid() && function_is_undefined()) 
            table << "Данный план является оптимальным и не требует улучшения. Решение найдено." << endl; 
            std::ofstream outfile ("table.txt"); 
            outfile << table.str(); 
    } 
    else { 
        std::string ln_or_gn; 
        if (way) 
            ln_or_gn = "неположительные"; 
        else 
            ln_or_gn = "положительные"; 
        std::stringstream num_of_plane; 
        if (!it_num) 
            num_of_plane << "Первый опорный план"; 
        else 
            num_of_plane << it_num + 1 << "-й план также"; 
        table << "" << num_of_plane.str() << " не является оптимальным, посколькув индексной строке присутствуют " << ln_or_gn << " элементы.Erо необходимо улучшить" << endl; 
    } 
}

#include "stdafx.h"
#include <iostream>
#include <string>
#include <cstdlib>
 
#include "user_data.h"
 
using std::cout;
using std::cin;
using std::endl;
using std::string;
 
void error(int err_no)
{
    switch(err_no) {
        case 0:
            cout << "\nВы ввели некорректное значение.\n" << endl;
            break;
        case 1:
            cout << "\nВы не можете задать менее двух ограничений.\n" << endl;
            break;
        case 2:
            cout << "\nВы не можете задать больше 500 ограничений.\n" << endl;
            break;
        case 3:
            cout << "\nВы не можете задать менее двух переменных.\n" << endl;
            break;
        case 4:
            cout << "\nВы не можете задать более 500 уравнений.\n" << endl;
            break;
    }
}
 
void user_data::get_data_from_user()
{
    string num_limits, num_vars, s_var, fr_m, sn, func, w;
    int i, j;
    bool validator = false;
    
 
    do {
        cout << "Введите количество ограничений в системе: ";
        getline(cin, num_limits);
        if (atoi(num_limits.c_str()) < 2)
            error(1);
        else if (atoi(num_limits.c_str()) > 500)
            error(2);
        else
            validator = true;
            
    } while (!validator);
 
    num_l = atoi(num_limits.c_str());
    validator = false;
 
    do {
        cout << "Введите количество переменных в системе ограничений: ";
        getline(cin, num_vars);
    if (atoi(num_vars.c_str()) < 2) 
        error(3);
    else if (atoi (num_vars.c_str()) > 500)
        error(4);
    else
        validator = true;
    } while (!validator);
 
    num_v = atoi(num_vars.c_str());
    validator = false;
    
    function = new double [num_v];
    system = new double *[num_l];
    for (i = 0; i < num_l; i++)
        system[i] = new double [num_v];
    fm = new double [num_l];
    sign = new int [num_l];
 
    cout << "\nЗаполните коэффициенты при целевой функции.\n" << endl;
 
    for (i = 0; i < num_v; i++) {
        do {
            cout << "Введите коэффициент целевой фукнции при x" << i + 1 << ": ";
            getline(cin, func);
            if (atof(func.c_str()) == 0)
                error(0);
            else {
                validator = true;
                function[i] = atof(func.c_str());
            }
        } while (!validator);
        validator = false;
    }
    
    do {
        cout << "Введите направление целевой функции ( min, max ) : ";
        getline(cin, w);
        if (w == "max" || w == "MAX" || w == "min" || w == "MIN") {
            validator = true;
            if (w == "max" || w == "MAX")
                way = true;
            else
                way = false;
        }
        else
            error (0);
 
    } while (!validator);
    cout << "\nЗаполните систему ограничений.\n" << endl;
 
    for (i = 0; i < num_l; i++) {
        cout << "Заполните " << i + 1 << "-е ограничение.\n" << endl;
        for (j = 0; j < num_v; j++) {
            do {
                cout << "Введите коэффициэнт при x" << j + 1 << ": ";
                getline(cin, s_var);
                if (atof(s_var.c_str()) == 0)
                    error (0);
                else {
                    validator = true;
                }
            } while (!validator);
            system[i][j] = atof(s_var.c_str());
            validator = false;
        }
 
        do {
            cout << "Введите знак при " << i + 1 << "-м ограничении ( <=, =, >= ) : ";
            getline(cin, sn);
            if (sn == "<=" || sn == "=" || sn == ">=") {
                validator = true;
                if (sn == "<=")
                    sign[i] = 0;
                if (sn == "=")
                    sign[i] = 1;
                if (sn == ">=") 
                    sign[i] = 2;
                }
            else
                error(0);
            cout << sign[i] << endl;
        } while (!validator);
 
        validator = false;
 
        do {
            cout << "Введите свободный член при " << i + 1 << "-м ограничении: ";
            getline(cin, fr_m);
            if (atof(fr_m.c_str()) == 0)
                error(0);
            else
                validator = true;
        } while (!validator);
 
        fm[i] = atof(fr_m.c_str());
        validator = false;
 
        cout << endl;
    }
    
}