Решение задач оптимизации на основе авторских программ

Внедрение в повседневную жизнь каждого человека информационно-коммуникационных технологий вызывает у многих желание научиться программировать. Потребность в разработке компьютерных программ самим пользователем обусловила появление на рынке систем программирования «быстрой разработки» - RAD-систем (Rapid Application Development - среда быстрой разработки приложений). В их основе лежит технология визуального проектирования и событийного программирования, когда среда разработки берет на себя большую часть работы, а программист занимается конструированием диалоговых окон и функций обработки событий.

Рассмотрим одну из таких программ, разработанную в среде Borland Delphi 7, 0, реализующую приложение «Алгебраический симплексный метод». Напомним, симплексный метод как итерационный процесс начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области допустимых решений, пока не находится оптимальное значение целевой функции. Алгоритм симплекс-метода включает четыре этапа.

1⁰. Составление первого опорного плана.

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

Полагая, что основные переменные равны нулю, получаем первый опорный план, который заносим в симплекс-таблицу (табл. 1), состоящую из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком.

2⁰. Проверка плана на оптимальность.

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

3⁰. Определение ведущих столбца и строки.

Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободной в базисную. Затем элементы столбца свободных членов симплекс-таблицы делим на элементы того же знака (+/+; –/–) ведущего столбца. Результаты (всегда положительные) заносим в отдельный столбец min{Q_i}. Строка симплексной таблицы, соответствующая минимальному значению min{Q_i}, становится ведущей. Она определяет переменную x_i, которая на следующей итерации выходит из базиса и становится свободной.

Элемент симплекс-таблицы на пересечении ведущих столбца и строки называют разрешающим элементом (РЭ) и выделяют кружком.

4⁰. Построение нового опорного плана.

Переход к новому плану осуществляется при пересчете коэффициентов симплексной таблицы. Сначала заменим переменные в базисе, т.е. вместо x_iв базис войдет переменная x_j, соответствующая ведущему столбцу.

Все элементы ведущей строки предыдущей симплекс-таблицы делим на РЭ и результаты деления заносим в строку следующей симплекс-таблицы, соответствующую введенной в базис переменной x_j. В результате на месте разрешающего элемента в следующей симплекс-таблице ставим 1, а в остальных клетках j-го столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находим по правилу прямоугольника с применением формулы:

НЭ = СТЭ – (А*В)/(РЭ),

где СТЭ - элемент старого плана, РЭ - разрешающий элемент, А, В - элементы старого плана, образующие прямоугольник с элементами СТЭ, РЭ.

Далее идет возврат к п. 2⁰ – проверке плана на оптимальность.

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

Таблица 1. Примерная форма начальной симплекс-таблицы

План	Базисные пере- менные	Значения базисных переменных	Значения коэффициентов при	min {Qi}
X1	X2	X3	X4	X5	X6
I	4 5 6	– – –	– – –	– – –	– – –	– – –	– – –	– – –	– – –
Индексная строка		–	–	–	–	–	–	–	–
II	…	…	…	…	…	…	…	…	…

Приложение «Алгебраический симплексный метод» включает главное окно (рис. 1), на котором расположены поля для ввода данных и вывода результатов, кнопка «Вычислить» (при нажатии на нее производится расчет). Перед тем, как заполнять поля ввода, необходимо записать конкретную экономико-математическую модель ЗЛП.

Рис. 1. Окно приложения

Пример корректного заполнения формы приведен на рис. 2.

После нажатия кнопки «Вычислить» пользователь в нижнем поле окна пользователь видит результаты вычислений (рис. 3).

Рис. 2. Пример корректного заполнения формы

Пример 1. Торговое предприятие, имеющее материальные ресурсы, реализует три группы товаров А, В и С. Нормативы затрат ресурсов на 1 тыс. руб. товарооборота, доход от продажи, а также объем ресурсов даны в табл. 2. Требуется найти плановый объем продажи и структуру товарооборота, чтобы доход торгового предприятия был максимальный.

Таблица 2. Исходные данные задачи

Требуемые ресурсы	Нормы затрат ресурсов на 1 тыс. руб. товарооборота	Объем наличных ресурсов
Группа А	Группа Б	Группа В
Рабочее время продавцов, чел.-ч	0, 1	0, 2	0, 4
Площадь торговых залов, м2	0, 05	0, 02	0, 02
Складские помещения, м2
Доход, тыс. руб				max
Обозначения	х1	х2	х3

 

Решение. Занесем исходные данные ЗЛП, как это показано на рис. 2, с добавлением базисных переменных х₄-х₆. Нажмем кнопку «Вычислить», в итоге в нижней части окна получим результат.

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

В результате работы программы получаем:

- оптимальный план ЗЛП имеет вид: Х_опт = (250, 5375, 0, 0, 0, 1875);

- целевая функция равна F(Х) = 27625 тыс. руб.

Следовательно, необходимо продать товаров первой группы 250 ед., второй группы – 5375 ед., при этом предприятие получит максимальный доход в размере 27625 д.е. Товары третьей группы реализовать не следует. Попавшая в план дополнительная переменная х₆ указывает на то, что ресурсы третьего вида недоиспользованы на 1875 м².