6. Математический аппарат,
применяемый при курсовом проектировании

6.1. Линейное программирование

6.1.1. Графический метод решения
задач линейного программирования

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

Метод основан на том, что каждое ограничение неравенство отсекает в n-мерном пространстве n-мерную полуплоскость (в данной курсовой работе это – двухмерное пространство (плоскость) и простая полуплоскость). Совокупность этих полуплоскостей (если ограничения совместны) образует n-мерный многогранник допустимых решений. Оптимальное решение достигается в одной из вершин многогранника. Для определения этой вершины необходимо построить поверхность уровня целевой функции (в курсовом проекте – линию уровня). Затем следует перемещать эту поверхность (линию) в направлении градиента до крайней точки области допустимых решений (ОДР).

Рассмотрим следующий простой пример решения задачи линейного программирования (ЗЛП) графическим методом.

Математическая модель:

Перейдем от неравенств к равенствам:

Это уравнения прямых линий, которые могут быть легко построены по двум точкам:

для первого ограничения –

для второго ограничения –

для третьего ограничения –

Градиент целевой функции – это вектор, характеризующий направление и скорость изменения функции (в данном случае – целевой функции). Он определяется ее частными производными по каждой переменной:

Линия уровня целевой функции перпендикулярна градиенту.

Графическое решение данной задачи приведено на рисунке 6.1.

Рис. 6.1. Графическое решение задачи

Область допустимых решений (ОДР) в данном случае образуется четырехугольником ОВСД. Ни одна точка внутри его или на его границе не противоречит ни одному из ограничений. Оптимальное решение находится в одной из вершин четырехугольника. Для нахождения оптимального решения перемещаем линию уровня целевой функции в направлении градиента до крайней точки ОДР. Такой точкой является точка С с координатами: Х1=16; Х2=8. Значение целевой функции F=40×16+30×8=880. Очевидно, что это решение не отличается высокой точностью, что характерно для графического метода.

Из рисунка видно, что ресурсы второго и третьего видов использованы полностью, а ресурс первого вида оказался в избытке. Для количественной оценки этого избытка определим сначала расход данного ресурса: 2×16+3×8=56. Запас равен 60, тогда остаток составит 60–56=4.

6.1.2. Симплексный метод решения
задач линейного программирования

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

Приведем задачу, рассмотренную в предыдущем разделе, к канонической форме:

Дополнительные переменные Х3, Х4 и Х5 равны разности между левой и правой частями ограничений и характеризуют недовыполнение данного ограничения (в данном случае – излишний запас).

Задача решается в стандартных симплексных таблицах. Исходная таблица (см. табл. 6.1) заполняется коэффициентами модели.

Таблица 6.1

Базисными переменными являются переменные, входящие только в одно уравнение, с коэффициентом +1. Базисным переменным соответствует единичный вектор-столбец. Базисные переменные равны свободным членам. Свободные переменные (переменные, не вошедшие в базис) равны нулю. Таким образом, Х1=0; Х2=0; Х3= 60; Х4= 60; Х5=200; F=0.

Данное решение является опорным, так как в столбце свободных членов нет отрицательных элементов.

В качестве разрешающего столбца выбирается любой столбец с отрицательной оценкой в строке целевой функции F. Выберем в данном случае в качестве разрешающего – второй столбец. Для всех его элементов вычисляем симплексные отношения a_io/a_ip (отношение элемента столбца свободных членов к соответствующему элементу разрешающего столбца) и записываем их в последний столбец таблицы. Разрешающий элемент определяется минимальным симплексным отношением (в таблице он выделен жирным шрифтом). На месте разрешающего элемента ставится 1, а остальные элементы данного столбца равны нулю.

Остальные столбцы, соответствующие базисным переменным остаются без изменения. Столбец, соответствующий выводимой из базиса переменной, пересчитывается по общему правилу, описанному ниже. В данном случае Х2 вводится в базис вместо Х5 и столбец Х5 пересчитывается. Элементы разрешающей строки делятся на разрешающий элемент. Все остальные элементы таблицы пересчитываются по правилу прямоугольника. Пересчитываемый элемент образует с разрешающим элементом и соответствующими элементами разрешающей строки и столбца прямоугольник, изображенный на рисунке 6.2.

Рис. 6.2. Прямоугольник пересчета элементов симплексной таблицы

Пересчет производится по следующей формуле:

(6.1)

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

Например, пересчет элемента первого столбца первой строки:

Таблица 6.2

Решение задачи на любой итерации читается следующим образом: базисные переменные равны свободным членам (предпоследний столбец в таблице) а свободные переменные (те, которые не входят в базис) равны нулю. В данном случае

Или в краткой форме записи:

Здесь значения переменных приводятся в порядке возрастания их индексов.

Технико-экономический анализ полученного решения

Выпускается десять единиц продукции второго вида (Х2 = 10). При этом ресурс второго вида останется в количестве тридцати единиц (Х3 = 30), ресурс первого вида останется в количестве сорока единиц (Х4 = 40), а ресурс третьего вида оказывается израсходованным полностью (Х5 = 0).

Проверка полученного решения:

Данное решение не является оптимальным, так как в строке целевой функции еще есть отрицательный элемент а_1F = –3,4.

Вторая и все последующие итерации выполняются аналогично.

Таблица 6.3

Это решение оптимально, так как в строке целевой функции нет отрицательных оценок.

Технико-экономический анализ полученного решения

При имеющихся ресурсах следует выпустить 15,4 единицы (Х1=15,4) продукции первого вида и 6,9 единицы продукции второго вида (Х2=6,9). При этом ресурсы первого вида остаются в количестве 8,5 единицы (Х3=8,5), а ресурсы второго и третьего вида израсходованы полностью (Х4=Х5=0). Прибыль составит 823 у.е.

Проверка:

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