Численные методы. Корнюшин П.Н. - 67 стр.

                                                          67


        В этом случае говорят о задаче с двусторонними ограничениями. Конечно, задачу с
двусторонними ограничениями можно рассматривать как обычную, записывая отдельно оба
неравенства, составляющие двойное неравенство. Но так как созданы специальные приемы,
упрощающие решение, то эту задачу принято выделять при изучении теории линейного
программирования;
        в) от решения задачи дополнительно требуют, чтобы оно выражалось в целых числах. В
этом случае говорят о целочисленном программировании. Происхождение такого дополнительного
требования очевидно: числа, выражающие получаемое решение, могут означать физически
неделимые величины – число рейсов, число экземпляров, количество перевозочных средств
(судов, вагонов, автомобилей и др.) и т.д.
        Если поставить вопросы классификации задач шире, например, в объеме всего множества
оптимизационных задач, то можно наметить такие области.
        Прежде всего, следует отличать область линейных задач от области нелинейных задач. В
последнем случае говорят о нелинейном программировании. В области нелинейного
программирования в настоящее время разработаны методы решения таких задач:
        а) задачи, в которых целевая функция выражается отношением двух линейных функций
                                              c1' x1 + c2' x2 + ... + cn' xn
                                        Z=                                        .
                                              c1'' x1 + c 2'' x 2 + ... + cn'' xn
       К таким задачам приводит установка оптимизировать какой-то относительный (удельный)
показатель качества, например: себестоимость перевозок, рентабельность продукции и т.д. В этом
случае говорят о дробно-линейном программировании;
       б) задачи, в которых целевая функция выражается квадратичной функцией
                 Z = c1 x12 + c2 x22 + ... + c n xn2 + c12 x1 x2 + c13 x1 x3 + ... + c n−1 xn −1 xn ,
содержащей квадраты и попарные произведения параметров управления. Эти задачи называют
задачами квадратичного программирования;
        в) задачи, в которых целевая функция является так называемой выпуклой функцией от
параметров управления. Не будем здесь разъяснять математического содержания понятия
выпуклой функции многих переменных; в случае же одной переменной представление о выпуклой
функции дает выпуклая на некотором участке кривая линия. В частности, линейная функция есть
выпуклая функция. Оптимизационная задача, в которой целевая функция и ограничения
описываются выпуклыми функциями от параметров управления, называется задачей выпуклого
программирования.
        Отметим, наконец, весьма важную для задач оптимального управления область задач
динамического программирования. Само название говорит о содержании предмета. Речь идет о
таких оптимизационных задачах, в которых параметры управления связаны с состоянием
оптимизируемой системы на данный момент времени (на данном этапе). Эта область менее
исследована, чем область статических задач, к которой относится то, что сейчас излагается в
теории линейного программирования. Обычно здесь пользуются многошаговыми методами, т.е.
весь рассматриваемый динамический процесс разбивают на этапы; при этом конечные результаты
на одном этапе служат исходными для другого и т.д. Мы будем рассматривать модель общей
задачи линейного программирования.
        Выше было продемонстрировано, что ограничения задачи линейного программирования
могут выражаться только неравенствами (задача производственного планирования) или только
равенствами (транспортная задача). В случае, когда все ограничения выражаются неравенствами,
говорят о стандартной форме задачи линейного программирования. Когда все ограничения
выражаются равенствами, то говорят о канонической форме задачи линейного программирования.
Встречается и смешанная задача линейного программирования (расстановочная задача).
        Надо иметь в виду, что эти различия несущественны, т.к. одна форма легко преобразуется
в другую. Действительно, пусть, например, задано ограничение
                                           2x1 +3x2–x3 ≤ 8.
        Введем дополнительную неотрицательную переменную x4 ≥ 0, такую, чтобы было
                                          2x1+3x2–x3+x4=8.
        Благодаря этому ограничение, заданное неравенством, приобрело вид равенства. В общем
виде система ограничений-неравенств
                               ai1x1+ai2x2+…+ainxn ≤ bi (i=1, 2,…, m)