Симплекс метод — Курсовой проект на С++
Вчера я защитил курсовую работу по теме «Симплекс-метода» и решил поделиться своими наработками с читателем. Ниже представлена осноная часть пояснительной записки.
Если вам лень читать это здесь — скачайте весь курсовой проект в запакованном виде.
Введение
Основной целью данного проекта является закрепление теоретических знаний в области решения задач базовых линейного программирования симплекс – методом, получившем в литературе также название метода последовательного улучшения плана и реализация поставленной задачи на языке программирования С++. Симплексный метод решения задач линейного программирования — вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение сушествует, то оно обязательно будет найдено через конечное число шагов (за исключением так называемой «вырожденной задачи; при которой возможно явление «зацикливания», т. е. многократного возврата к одному и тому же положению).
Данный метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.
Постановка задачи
Необходимо разработать программу, решающую базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Свободные члены системы ограничений задачи могут быть произвольными.
Математическое обеспечение
Примером задачи линейного программирования является целевая функция с определенным направлением экстремума и система ограничений для этой целевой функции. Например:
Необходимо найти оптимальный план данной задачи с помощью симплекс-метода с использованием симплекс-таблицы.
Разработка алгоритма программы
Перед началом работы необходимо было понять сам алгоритм симплекс-метода. Для этого решалось несколько задач письменно. После освоение алгоритма была продумана структора самого проекта. Первым делом был написан класс user_data, который принимает пользовательские данные, т.е. Саму задачу, которую необходимо решить с помощью симплекс-метода. Рассмотрим содержимое заголовочного файла этого класса.
Рассмотрим все защищенные переменные-члены данного класса.
- int num_v хранит в себе значение количества переменных исходной задачи.
int num_l хранит в себе значение количества ограничений исходной задачи.
double function хранит значения коэффициентов целевой функции задачи. Данный член является указателем типа double, для которого в последующем будет выделена память и произведется инициализация его как одномерного массива с размером num_v .
double system хранит в себе значения коэффициентов самой системы ограничений. Это член является указателем на массив указателей, который в последующем будет инициализирован как матрица, соответствующая по размеру системе ограничений поставленной задачи ( num_l * num_v ).
int sign хранит в себе знак каждого ограничения системы. Является указателем типа int, который будет инициализирован как одномерный массив типа с размером num_l . Рационально использовать в данном случае целочисленный тип а не строковый. т.к. У нас есть три знака: , = и >= , которые храняться в *sign как 0, 1 и 2 соответственно.
Функция void get_data_from_user() , собственно запрашивает у пользователя данные, которые обрабатывает должным образом и помещает в защищенные переменные-члены данного класса, приведенные выше. В заголовочном файле хранится только прототип данной функции. Само определение функции находится в файле user_data.cpp.
Рассмотрим содержимое этого файла.
Функция 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.
Рассмотрим содержимое заголовочного файла этого класса.
Сначала рассмотрим закрытые переменная-члены данного класса.
- double func — содержит значение целевой фукнции. При каждой итерации оно меняется.
- double **bv — Содержит значения базисных переменных задачи. Данный член является указателем на массив указателей, который в последующем инициализируется двумерным массивом num_v * 2 , в первом стобце которого содержатся непосредственно. Сами значения базисных переменных задачи, а во втором номера этих переменных, которые изменяются при каждой последующей итерации. Номера базисных переменных необходимы для того, чтобы правильно вывести пользователю ответ и построить таблицу на выходе.
double **sv — Матрица коэффициентов при переменных задачи размером num_l * num_v * 2 . Первые num_v столбцы данной матрицы заполняются коэффициентами исходной системы ограничений, а последующие num_v столбцы заполняются единичной матрицей, если решается задача на максимум, если же производится решение задачи на минимум, единицы меняют свой знак.
double *istr — индексная строка, является одномерным массивом размером num_v * 2, первая половина которого заполняется коэффициентами функции-цели с обратным знаком, а вторая нулями на первой итерации. На последующих итерациях значения индексной строки меняются.
int i_lrow = индекс ведущей строки текущего плана.
double alm — разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки.
Собственно, сейчас были рассмотрены предназначения каждой переменная-члена класса simplex.
Весь алгоритм вычиления вышеприведенных значений производится в файле simplex.cpp.
Сначала выполняется инициализация первого опорного плана. Этим занимается функция-член 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 — это элементы старого плана, которые образуют «Прямоугольник», например.
В данном случае элемент нового плана будет вычисляться по вышеприведенной формуле, т. е.
Вычисление данным методом вручную занимает много времени, программа же делает это практически моментально. В этом и заключается наибольший смысл данного проекта.
Когда текущий план станет оптимальным или окажется, что задача не имеет решений, цикл закончит свою работу, после чего на экран будут выведены значение функции-цели и базисных переменных оптимального плана, если последний имеется. Если же функция не ограничена, то на экран будет выведено соответвующее сообщение пользователю.
Но перед тем, как вывести на экран ответ, в цикле производится вызов функции print_result_to_file(), которая в данном случает принимает в качестве аргумента номер итерации цикла, начиная с единицы. Функция пишет в объект table класса std::stringstream весь вывод, причем делает это «по умному», т. е. Формулирует весь алгоритм решения человеческим языком. Если план при текущей итерации стал оптимален, функция print_result_to_file() создает объект outfile класса std::oftream, т. е. Грубо говоря, выходной файл, в который записывается уже имеющийся объект table класса std::stringstream. Это является рациональным решением, т. к., если будет необходимо напечатать все решение на экран или еще куда-либо, нужно будет просто заменить «outfile
trevordixon / simplex.cs
| using System ; |
| using System . Diagnostics ; |
| using System . Collections . Generic ; |
| namespace Simplex < |
| class Simplex < |
| private double [] c ; |
| private double [,] A ; |
| private double [] b ; |
| private HashSet int > N = new HashSet int >(); |
| private HashSet int > B = new HashSet int >(); |
| private double v = 0 ; |
| public Simplex ( double [] c , double [,] A , double [] b ) < |
| int vars = c . Length , constraints = b . Length ; |
| if ( vars != A . GetLength ( 1 )) < |
| throw new Exception ( » Number of variables in c doesn’t match number in A. » ); |
| > |
| if ( constraints != A . GetLength ( 0 )) < |
| throw new Exception ( » Number of constraints in A doesn’t match number in b. » ); |
| > |
| // Extend max fn coefficients vector with 0 padding |
| this . c = new double [ vars + constraints ]; |
| Array . Copy ( c , this . c , vars ); |
| // Extend coefficient matrix with 0 padding |
| this . A = new double [ vars + constraints , vars + constraints ]; |
| for ( int i = 0 ; i constraints ; i ++ ) < |
| for ( int j = 0 ; j vars ; j ++ ) < |
| this . A [ i + vars , j ] = A [ i , j ]; |
| > |
| > |
| // Extend constraint right-hand side vector with 0 padding |
| this . b = new double [ vars + constraints ]; |
| Array . Copy ( b , 0 , this . b , vars , constraints ); |
| // Populate non-basic and basic sets |
| for ( int i = 0 ; i vars ; i ++ ) < |
| N . Add ( i ); |
| > |
| for ( int i = 0 ; i constraints ; i ++ ) < |
| B . Add ( vars + i ); |
| > |
| > |
| public Tuple double , double []> maximize () < |
| while ( true ) < |
| // Find highest coefficient for entering var |
| int e = — 1 ; |
| double ce = 0 ; |
| foreach ( var _e in N ) < |
| if ( c [ _e ] > ce ) < |
| ce = c [ _e ]; |
| e = _e ; |
| > |
| > |
| // If no coefficient > 0, there’s no more maximizing to do, and we’re almost done |
| if ( e == — 1 ) break ; |
| // Find lowest check ratio |
| double minRatio = double . PositiveInfinity ; |
| int l = — 1 ; |
| foreach ( var i in B ) < |
| if ( A [ i , e ] > 0 ) < |
| double r = b [ i ] / A [ i , e ]; |
| if ( r minRatio ) < |
| minRatio = r ; |
| l = i ; |
| > |
| > |
| > |
| // Unbounded |
| if ( double . IsInfinity ( minRatio )) < |
| return Tuple . Create double , double []>( double . PositiveInfinity , null ); |
| > |
| pivot ( e , l ); |
| > |
| // Extract amounts and slack for optimal solution |
| double [] x = new double [ b . Length ]; |
| int n = b . Length ; |
| for ( var i = 0 ; i n ; i ++ ) < |
| x [ i ] = B . Contains ( i ) ? b [ i ] : 0 ; |
| > |
| // Return max and variables |
| return Tuple . Create double , double []>( v , x ); |
| > |
| private void pivot ( int e , int l ) < |
| N . Remove ( e ); |
| B . Remove ( l ); |
| b [ e ] = b [ l ] / A [ l , e ]; |
| foreach ( var j in N ) < |
| A [ e , j ] = A [ l , j ] / A [ l , e ]; |
| > |
| A [ e , l ] = 1 / A [ l , e ]; |
| foreach ( var i in B ) < |
| b [ i ] = b [ i ] — A [ i , e ] * b [ e ]; |
| foreach ( var j in N ) < |
| A [ i , j ] = A [ i , j ] — A [ i , e ] * A [ e , j ]; |
| > |
| A [ i , l ] = — 1 * A [ i , e ] * A [ e , l ]; |
| > |
| v = v + c [ e ] * b [ e ]; |
| foreach ( var j in N ) < |
| c [ j ] = c [ j ] — c [ e ] * A [ e , j ]; |
| > |
| c [ l ] = — 1 * c [ e ] * A [ e , l ]; |
| N . Add ( l ); |
| B . Add ( e ); |
| > |
| > |
| class MainClass < |
| static void Main ( string [] args ) < |
| var s = new Simplex ( |
| new [] < 10.2 , 422.3 , 6.91 , 853 >, |
| new [,] < |
| < 0.1 , 0.5 , 0.333333 , 1 >, |
| < 30 , 15 , 19 , 12 >, |
| < 1000 , 6000 , 4100 , 9100 >, |
| < 50 , 20 , 21 , 10 >, |
| >, |
| new double [] |
| ); |
| var answer = s . maximize (); |
| Console . WriteLine ( answer . Item1 ); |
| Console . WriteLine ( string . Join ( » , » , answer . Item2 )); |
| > |
| > |
| > |
This comment has been minimized.
Copy link Quote reply
hassan181 commented May 16, 2017
How To minimize Answer?
This comment has been minimized.
Copy link Quote reply
souzamarcos commented Jun 8, 2018 •
@hassan181 You can convert your minimization problem into a maximization problem!
