Реализация алгоритма симплекс-метода с произвольными свободными членами

Алматинский Государственный  Бизнес колледж

 

 

 

Специальность «Вычислительная техника и программное обеспечение »

 

 

 

КУРСОВАЯ  РАБОТА

«Реализация алгоритма симплекс-метода с произвольными  свободными членами»

 

 

 

                                                                                                                Проверил:

Выполнил:

 

 

 

 

 

 

 

 

Алматы 2013

Содержание.

1. Содержание.
2. Введение.
3. Постановка задачи.
4. Математическое обеспечение.
5. Разработка алгоритма программы.
6. Пример работы программы.
7. Заключение.
8. Список используемой литературы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Симплексный метод решения задач линейного программирования - вычислительная процедура, основанная на принципе последовательного улучшения решений - перехода от одной базисной точки к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение сушествует, то оно обязательно будет найдено через конечное число шагов (за исключением так называемой «вырожденной задачи; при которой возможно явление «зацикливания», т. е. многократного возврата к одному и тому же положению).

 

Данный метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.

 

Постановка задачи

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

 

Математическое  обеспечение

Примером задачи линейного программирования является целевая функция с определенным направлением экстремума и система ограничений для этой целевой функции. Например:

F(X) = 3x1 + 5x2 + 4x3 => max

0,1x1 + 0,2x2 + 0,4x3 <= 1100

0.05x1 + 0.02x2 – 0.02x3 <= 120

3x1 + x2 + 2x3 <= 8000

 

Необходимо найти оптимальный  план данной задачи с помощью симплекс-метода с использованием симплекс-таблицы.

 

Разработка  алгоритма программы

Перед началом  работы необходимо было понять сам  алгоритм симплекс-метода. Для этого  решалось несколько задач письменно. После освоение алгоритма была продумана структора самого проекта. Первым делом был написан класс user_data, который принимает пользовательские данные, т.е. Саму задачу, которую необходимо решить с помощью симплекс-метода. Рассмотрим содержимое заголовочного файла этого класса.

 

Листинг 1. user_data.h

 

#ifndef _USER_DATA_H_

#define _USER_DATA_H_

 

class user_data {

public:

void get_data_from_user();

void user_data_is_valid();

protected:

double *function;

double *fm;

double **system;

int *sign;

int num_v;

int num_l;

bool way;

};

#endif /* _USER_DATA_H_ */

 

Рассмотрим  все защищенные переменные-члены  данного класса.

 

int num_v хранит в себе значение количества переменных исходной задачи.

Int num_l хранит в себе значение количества ограничений исходной задачи.

double *function хранит значения коэффициентов целевой функции задачи. Данный член является указателем типа double, для которого в последующем будет выделена память и произведется инициализация его как одномерного массива с размером num_v.

double *fm хранит в себе значения свободных членов системы ограничений. Также является указателем типа double, который будет инициализирован как одномерный массив с размером num_l.

double **system хранит в себе значения коэффициентов самой системы ограничений. Это член является указателем на массив указателей, который в последующем будет инициализирован как матрица, соответствующая по размеру системе ограничений поставленной задачи (num_l x num_v).

int *sign хранит в себе знак каждого ограничения системы. Является указателем типа int, который будет инициализирован как одномерный массив типа с размером num_l. Рационально использовать в данном случае целочисленный тип а не строковый. т.к. У нас есть три знака: <=, = и >=, которые храняться в *sign как 0, 1 и 2 соответственно.

bool way хранит в себе направление целевой функции задачи (min/max). При решении задачи на максимум эта переменная-член будет хранить в себе значение истины (true). А при решении на минимум, соответственно, ложь (false). Такой способ хранения данных очень рационален в данном случае, поскольку направлений у функции цели может быть только два. Поэтому тип bool идеально подходит для этого.

 

Функция void get_data_from_user(), собственно запрашивает у пользователя данные, которые обрабатывает должным образом и помещает в защищенные переменные-члены данного класса, приведенные выше. В заголовочном файле хранится только прототип данной функции. Само определение функции находится в файле user_data.cpp. Рассмотрим содержимое этого файла.

 

Листинг 2. user_data.cpp

#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;

}

}

 

Функция error(int err_no) принимает в качестве аргумента номер ошибки, которая должна вывестись пользователю в том случае, если он ввел некорректные данные. Далее номер ошибки, переданный в функцию обрабатывается оператором switch(), и в зависимости от принимаемого функцией аргумента, выводится ошибка с помощью оператора cout.]

 

Теперь рассмотрим функцию-член get_data_from_user() класса user_data. Все данные, который вводит пользователь, первоначально помещаются в объект типа string, а затем проверяется  корректность данных, если все введено верно, то выполняется преобразование из std::string в int или double с помощью функций atoi() и atof() соответственно.

 

Сначала у пользователя запрашивается  количество ограничений в системе. Если было введено целое число, от 2 до 500, то это значение преобразуется в int и заностится в переменную-член num_l. В противном случае вызывается функция error() с номером соответвующей ошибки и снова запрашивается ввод данных.

 

Далее, таким же образом  пользователь вводит количество переменных задачи.

 

Затем выделяется память под  массив function и матрицу system, а затем  также идет ввод коэффициентов функции  цели в цикле. После идет ввод значения направления функции. Если оно введено  верно, то в переменная-член way заносится true или false, в зависимости от введенного значения. Регистр при вводе направления не учитывается при проверке. Если все верно, заполняется матрица system коэффициентами системы ограничений исходной задачи. Заполнение происходит в двух вложенных циклах, в первом из которых, также вводится знак ограничения и значение свободного члена при этом ограничении. Когда пользователь закончит ввод, все переменная-члены класса user_data будут заполнены, и тогда мы переходим к самому алгоритму, который реализован в классе simplex, являющимся прямым наследником класса user_data. Рассмотрим содержимое заголовочного файла этого класса.

Листинг 3. simplex.h

 

#ifndef _SIMPLEX_H_

#define _SIMPLEX_H_

 

#include <sstream>

 

#include "user_data.h"

 

class simplex : public user_data {

public:

void init();

void gen_plane();

bool plane_is_valid();

bool function_is_undefined();

void print_result_to_file(int it_num);

private:

double func;

double **bv;

double **sv;

double *istr;

double *th;

double alm;

int i_lrow;

int i_lcol;

std::stringstream table;

};

 

#endif /* _SIMPLEX_H_ */

 

Сначала рассмотрим закрытые переменная-члены данного  класса.

 

double func — содержит значение целевой фукнции. При каждой итерации оно меняется.

double **bv — Содержит  значения базисных переменных  задачи. Данный член является  указателем на массив указателей, который в последующем инициализируется двумерным массивом num_v x 2, в первом стобце которого содержатся непосредственно. Сами значения базисных переменных задачи, а во втором номера этих переменных, которые изменяются при каждой последующей итерации. Номера базисных переменных необходимы для того, чтобы правильно вывести пользователю ответ и построить таблицу на выходе.

double **sv — Матрица  коэффициентов при переменных  задачи размером num_l x num_v * 2. Первые num_v столбцы данной матрицы заполняются коэффициентами исходной системы ограничений, а последующие num_v столбцы заполняются единичной матрицей, если решается задача на максимум, если же производится решение задачи на минимум, единицы меняют свой знак.

 

double *istr — индексная  строка, является одномерным массивом размером num_v * 2, первая половина которого заполняется коэффициентами функции-цели с обратным знаком, а вторая нулями на первой итерации. На последующих итерациях значения индексной строки меняются.

 

Int i_lcol = индекс  ведущего столбца текущего плана.

 

double *th (греч. «тета») — последний столбец симплексной  таблицы, инициализируется одномерным  массивом размером num_l.

 

Int i_lrow = индекс  ведущей строки текущего плана. 

 

double alm — разрешающий  элемент, находящийся на пересечении ведущего столбца и ведущей строки.

 

std::stringstream table —  объект класса std::stringstream, который  содержит весь пользовательский  вывод в выходной файл.

 

Собственно, сейчас были рассмотрены  предназначения каждой переменная-члена  класса simplex. Весь алгоритм вычиления вышеприведенных значений производится в файле simplex.cpp.

 

Листинг 4. simplex.cpp

 

#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];