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

Цель работы

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

Методические указания

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

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

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

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

В случае, если и целевая функция и ограничения представлены линейными зависимостями, то такой класс задач получил название задач линейного программирования.

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

Пусть судно имеет грузоподъемность 12 тыс. т и вместимость 20 тыс. м³. Для перевозки предложено 4 типа грузов, характеристики которых приведены в табл. 13.

Таблица 13.

По своим техническим характеристикам судно может перевозить грузы 1 и 3 суммарным объемом не более 12 тыс. м³, а грузы 2 и 4 – суммарным объемом не более 15 тыс. м³. Также задана обязательная минимальная перевозка груза типа 4 в количестве 3 тыс. т.

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

Математическая модель задачи и ее решение проведено в следующем MathCAD документе:

Отметим, что:

- Решение задачи может зависеть от выбора начального приближения;

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

- Одним из вариантов задачи линейного программирования является транспортная задача. Имеется ряд пунктов отправления, в которых сосредоточены запасы груза в заданных количествах; в каждый из пунктов назначения должно быть доставлено груза в известных количествах. Требуется составить такой план перевозок, которому бы соответствовали минимальные суммарные транспортные издержки. Замена неравенств в ограничениях на равенства приводит к системе линейных алгебраических уравнений, но не с одним, а с множеством решений, одно из которых оптимизирует целевую функцию.