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

После заполнения 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= 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"main()

{(LC_ALL, "Russian");*ud = new simplex;>get_data_from_user();>init();>gen_plane();

return 0;

}

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

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

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

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

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

.05x1 + 0.02x2 - 0.02x3 <= 120

x1 + x2 + 2x3 <= 8000

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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