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

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. сообщает системе об удачном завершении работы программы.

 

 

 

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

 

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

 

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. Также были использованы различные материалы из Википедии — Свободной веб-энциклопедии и прочих интернет-ресурсов.