7.4 Основные алгоритмы системы

Для реализации системы были разработаны следующие алгоритмы:

- алгоритм «Генерация задания» (рис. 7.11);

- алгоритм решения оптимизационной задачи – «Симплекс-метод» (рис. 7.12);

- алгоритм «Анализ моделей на чувствительность»;

- алгоритм «Двойственная оптимизационная задача линейного программирования»;

- алгоритм пошагового выполнения задания «Тренажер для изучения Симплекс-метода»;

- алгоритм «Проверка», предназначенный для проверки преподавателем контрольной работы, выполненной студентом;

- алгоритм «Экзамен», предназначенный для формирования различных заданий на экзамене и автоматизированной проверки результатов выполнения.

Рисунок 7.11 – Алгоритм генерации задания

Рисунок 7.12 – Алгоритм Симплекс-метода в модуле «Тренажер»

7.5 Интерфейс пользователя

На рисунках 7.13– 7.22 приведены основные экранные формы системы.

Рисунок 7.13 – Основная форма приложения для преподавателя

Рисунок 7.14 – Экранная форма выполнения Симплекс-метода в модуле «Тренажер»

Рисунок 7.15 – Экранная форма выполнения анализа чувствительности в модуле «Тренажер»

Рисунок 7.16 – Экранная форма решения двойственной задачи в модуле «Тренажер»

Рисунок 7.17 – Экранная форма ввода данных студента перед получением задания

Рисунок 7.18 – Экранная форма заполнения результатов расчета контрольной работы

Рисунок 7.19 – Экранная форма проверки контрольных работ

Рисунок 7.20 – Экранная форма модуля помощи «Help»

Рисунок 7.21 – Пример ввода ответа в модуле «Экзамен»

Рисунок 7.22 – Результат выполненного экзамена

Методы работы с системой описаны в руководстве пользователя приложение Б.

7.6 Тестирование

Для проверки работоспособности системы проведен расчет одного из вариантов контрольной работы ручным методом. После чего полученные данные введем в систему и сравним итоговые результаты.

Дана задача линейного программирования:

1 Необходимо найти оптимальное решение модели Симплекс-методом.

Решение состоит из пяти итераций, в результате которых получаем:

Оптимальное решение имеет вид:

Ниже приведен пример ввода результата расчетов Симплекс-методом (рис. 7.23).

Рисунок 7.23 – Ввод результата расчетов Симплекс-методом

2 Произвести анализ на чувствительность. Определить, в каких пределах могут меняться коэффициенты при базисных и небазисных переменных в выражении для целевой функции, не нарушая оптимальности прежнего базиса. Найти пределы, в которых могут меняться константы в правых частях, не нарушая оптимальности прежнего решения.

Небазисными переменными являются: x_1, x₂, x₃, x₆.

Предположим, что коэффициент при x получает положительное приращение δ. Тогда строка 0 исходной системы примет вид:

На заключительной итерации, строка 0 примет вид:

Если δ₁ > , то коэффициент при x₁ примет отрицательное значение, так же если δ₂ > , то коэффициент при x₂ примет отрицательное значение, то решение перестанет быть оптимальным, аналогично с δ₃ и δ_6.

Следовательно, получаем:

δ₁ < ; δ₂ < ; δ₃ < δ₆ < .

Запишем целевую функцию на последней итерации с измененным коэффициентом при базисной переменной x₄:

стр(0)

Так как x₄ по-прежнему входит в базис, то необходимо исключить x₄ из строки (0). Для этого умножим строку (3) на δ и прибавим к строке (0). В результате получим:

Отсюда следует, что при выполнении условия полученное решение остается оптимальным.

Запишем целевую функцию на последней итерации с измененным коэффициентом при базисной переменной x₅:

Так как x₅ по-прежнему входит в базис, то необходимо исключить x₅ из строки (0). Для этого умножим строку (1) на δ и прибавим к строке (0). В результате получим:

Отсюда следует, что при выполнении условия полученное решение остается оптимальным.

Находим пределы, в которых могут меняться константы в правых частях, не нарушая оптимальности прежнего решения. Таким образом, ранее полученное решение останется допустимым, если:

;

.

Ниже приведен пример ввода результата расчетов анализа на чувствительность (рис. 7.24).

Рисунок 7.24 – Ввод результата расчетов анализа на чувствительность

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

Результат выглядит следующим образом:

Следовательно, получаем:

Ниже приведен пример ввода результата расчетов двойственной задачи (рис. 7.25).

Рисунок 7.25 – Ввод результата расчетов двойственной задачи

При проверке преподавателем выполненной контрольной работы программа выведет следующий результат (рис. 7.26-7.28).

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

Рисунок 7.26 – Проверка результата расчетов Симплекс-метода

Рисунок 7.27 – Проверка результата расчетов анализа на чувствительность

Рисунок 7.28 – Проверка результата расчетов двойственной задачи