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

Теперь, когда присутствуют все проверки, можно переходить к вычислению оптимального плана, т. е. Итерированию цикла до тех пор, пока план не оптимален и задача имеет решение. Этим занимается функция 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. сообщает системе об удачном завершении работы программы.

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

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

(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. Усовершенствованная версия программы, возможно будет представлена в дипломной работе.

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

программа симплекс таблица функция

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

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

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

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

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

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