Грубо кажучи, потрібно виробляти ітерірованіе циклу, поки план не стане оптимальним. Перевіркою оптимальності плану займається функція 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 lt; lt;» на «cout lt; lt;» або на будь-який інший потоковий оператор виводу.
Але, щоб весь алгоритм, наведений у предидущех исходниках завівся, нам, природно, необхідна функція main (), без якої нічого працювати не буде.
Лістинг 5. main.cpp
# include simplex.h main ()
{(LC_ALL, Russian ); * ud=new simplex; gt; get_data_from_user (); gt; init (); gt; gen_plane ();
return 0;
}
Спочатку задається російська локаль для консолі Windows, потім створюється об'єкт класу simplex, після чого викликається функція get_data_from_user () успадкованого класу user_data, а потім init () і gen_plane () які також були розглянуті вище. return 0. повідомляє систему про вдале завершення роботи програми.
4. Приклад роботи програми
Задана цільова фукнція:
(X)=3x1 + 5x2 + 4x3= gt; max
І система обмежень:
, 1x1 + 0,2x2 + 0,4x3 lt;=1100
. 05x1 + 0.02x2 - 0.02x3 lt;=120
x1 + x2 + 2x3 lt;=8000
Вирішимо дану задачу за допомогою програми, алгоритм якої був описаний раніше.
Заглянемо в файл table.txt
...
