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

ФГОУ  СПО Волгоградский технологический  колледж 
 
 

Специальность 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» 
 
 

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

ПО  ДИСЦИПЛИНЕ «МАТЕМАТИЧЕСКИЕ  МЕТОДЫ»

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

Проверил:

Теткин  А.А.

Выполнил:

Студент гр. ВТ-3-1

Левитин С. А 

Волгоград 2011

Содержание.

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;