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

Размещено на http://www.allbest.ru/

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

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

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

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

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

Проверил:

Теткин А.А.

Выполнил:

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

Левитин С. А

Волгоград 2011

Содержание

Введение

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

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

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

4. Пример работы программы

Заключение

Список используемой литературы

Введение

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

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

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

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

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

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

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

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

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

0.05x1 + 0.02x2 - 0.02x3 <= 120

3x1 + x2 + 2x3 <= 8000

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

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

Перед началом работы необходимо было понять сам алгоритм симплекс-метода. Для этого решалось несколько задач письменно. После освоение алгоритма была продумана структура самого проекта. Первым делом был написан класс 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];

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 << "\nЦелевая фукнция не ограничена, данная задача решений не имеет\n" << endl;

else {

cout << "\nf(x) = " << func << "\n" << endl;

for (i = 0; i < num_l; i++) {

cout << "x" << bv[i][0] + 1 << " = " << bv[i][1] << endl;

}

cout << "\nВсе вычисления были записаны в файл table.txt\n" << endl;

}

}

void simplex::print_result_to_file(int it_num)

{

int i, j;

if (!it_num) {

table << "Задана целевая функция:\n" << 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 << "\n" << endl;

table << f_x.str();

table << "И система ограничений:\n" << 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 << " методом симплексных таблиц.\nПостроим первый опорный план:\n" << endl;

}

for (i = 0; i < num_l; i++) {

table << "x" << bv[i][0] + 1 << "\t" << bv[i][1] << "\t";

for (j = 0; j < num_v * 2; j++)

table << sv[i][j] << "\t";

if (!plane_is_valid())

table << th[i];

table << "\n" << endl;

}

table << "f(x)\t" << func << "\t";

for (i = 0; i < num_v * 2; i++)

table << istr[i] << "\t";

table << "\n";

if (plane_is_valid()) {

if (plane_is_valid() && function_is_undefined())

table << "\nДанный план является оптимальным и не требует улучшения. Решение найдено." << 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 << "\n" << num_of_plane.str() << " не является оптимальным, поскольку\nв индексной строке присутствуют " << ln_or_gn << " элементы.\nErо необходимо улучшить.\n" << endl;

}

}

Сначала выполняется инициализация первого опорного плана. Этим занимается функция-член init() класса simplex.

Значение функции-цели в первом опорном плане всегда равно нулю, поэтому в init() выполняется инициализация переменной-члена func класса simplex именно нулем.

Затем выделяется память под матрицу коэффициентов sv. И производится ее заполнение. Первая часть данной матрицы заполняется коэффициентами системы ограничений исходной задачи, вторая часть является единичной матрицей, в случае решения задачи на максимум, если же решается задача на минимум, единицы в данной матрице меняют свой знак.

После заполнения sv производится выделение памяти под одномерный массив istr и иницализация этого массива (индексной строки первого опорного плана). Первая ее часть заполняется коэффициентами целевой функции с обратным знаком, вторая ее половина инициализируется нулями.

Затем вычисляется индекс ведущего столбца первого опорного плана задачи. Данный индекс соответствует индексу максимального по модулю отрицательного элемента индексной строки.

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

После вычисления колонки th производится вычисление индекса ведущей строки, который соответствует индексу минимального значения в столбце th.

Разрешающий элемент плана находится на пересечении ведущего столбца и ведущей строки текущего плана. После его вычисления производится вызов функции print_result_to_file(), которая заносит таблицу для первоначального опорного плана в объект table класса std::stringstream, который также является переменная-членом класса simplex.

После построения первого опорного плана необходимо вычилить оптимальный план исходной задачи. Грубо говоря, нужно призводить итерирование цикла, пока план не станет оптимальным. Проверкой оптимальности плана занимается функция bool plane_is_valid, которая проверяет индексную строку текущего плана на наличие отрицательных элементов в случае решения задачи на максимум и неотрицательный в противном случае. Если таковые элементы имеются в индексной строке, то план является неоптимальным и его необходимо улучшить, поэтому функция возвращает значение false в данном случае. Если план является оптимальным, функция возвратит значение true, что будет являться сигналом о прекращении итерирования для цикла, реализованного в функции gen_plane().

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

Теперь, когда присутствуют все проверки, можно переходить к вычислению оптимального плана, т. е. Итерированию цикла до тех пор, пока план не оптимален и задача имеет решение. Этим занимается функция gen_plane().

Вычисление последующего плана весьма схоже с вычислением первого опорного плана. Единственным весомым отличием является метод «прямоугольника», по которому вычисляются все элементы таблицы, кроме тех, которые находятся в ведущей строке предыдущего плана. Последние вычиляются путем деления каждого элемента этой строки на разрешающий элемент предыдушего плана. Сам же метод «прямоугольника» можно выразить следующим образом:

НЭ = СТЭ -- (A * B) / РЭ.

Где «НЭ» - вычисляемые элемент нового плана, «СТЭ» - элемент предыдушего плана, соответвующий вычиляемому элементу, РЭ -- разрешающий элемент предыдушего плана. Переменные A и B -- это элементы старого плана, которые образуют «Прямоугольник», например.

СТЭ = 1 A = 2

B = 3 РЭ = 4.

В данном случае элемент нового плана будет вычисляться по вышеприведенной формуле, т. е.

НЭ = 1 -- (2 * 3) / 4 = 1 -- 1.5 = 0.5

Вычисление данным методом вручную занимает много времени, программа же делает это практически моментально. В этом и заключается наибольший смысл данного проекта.

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

Но перед тем, как вывести на экран ответ, в цикле производится вызов функции print_result_to_file(), которая в данном случает принимает в качестве аргумента номер итерации цикла, начиная с единицы. Функция пишет в объект table класса std::stringstream весь вывод, причем делает это «по умному», т. е. Формулирует весь алгоритм решения человеческим языком. Если план при текущей итерации стал оптимален, функция print_result_to_file() создает объект outfile класса std::oftream, т. е. Грубо говоря, выходной файл, в который записывается уже имеющийся объект table класса std::stringstream. Это является рациональным решением, т. к., если будет необходимо напечатать все решение на экран или еще куда-либо, нужно будет просто заменить «outfile <<» на «cout <<» или на любой другой потоковый оператор вывода.

Но, чтобы весь алгоритм, приведенный в предыдущех исходниках завелся, нам, естественно, необходима функция main(), без которой ничего работать не будет.

Листинг 5. main.cpp

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

}

Сначала задается русская локаль для консоли Windows, затем создается объект класса simplex, после чего вызывается функция get_data_from_user() наследуемого класса user_data, а затем init() и gen_plane() которые также были рассмотрены выше. return 0. сообщает системе об удачном завершении работы программы.

4. Пример работы программы

Задана целевая фукнция:

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

И система ограничений:

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

0.05x1 + 0.02x2 - 0.02x3 <= 120

3x1 + x2 + 2x3 <= 8000

Решим данную задачу с помощью программы, алгоритм которой был описан ранее.

Заглянем в файл table.txt

Решение, приведенное на данных скриншотах было проверено в MS Excel с помощью функции «Поиск решения» и является абсолютно верным, также данная таблица строилась вручную.

Исходники, тесты и сам исполняемый файл данной программы приглагаются на компакт-диске, который вложен в данную пояснительную записку.

Заключение

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

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

Данный проект несомненно, будет развиваться, в скором времени будет добавлен алгоритм решения задач методом искусственного базиса и написан графический интерфейс с использованием кроссплатформенной библиотеки QT. Усовершенствованная версия программы, возможно будет представлена в дипломной работе.

Список используемой литературы

1. Бьерн Страуструп -- Язык программирования С++ 2-е издание 2007 год.

2. Лунгу К. Н. - Линейное программирование. Руководство к решению задач. - 2005 год.

3. Настольная книга Gentoo Linux -- веб-издание, 2008 год.

4. А.В. Андреев - Программирования в Unix-подобных операционных системах -- 2006 год.

5. Система управления версиями GIT, полное руководство -- веб издание, 2011 год.

6. Также были использованы различные материалы из Википедии -- Свободной веб-энциклопедии и прочих интернет-ресурсов.

Размещено на Allbest.ru

...