Раздел 1 7

Разработка эффективной товарной политики 7

предприятия 7

где _k (x) = С₁( ) — a_k - отклонение от целей; ^l_k 0 - коэффициенты, характеризующие важность для ЛПР тех или иных отклонений.

Если желательна максимизация каждой из целевых функций С_к (х), то можно выбрать

arg (x), (2.10)

где = mах(0, — _к ). Нетрудно убедиться, что (2.3) и (2.10) практи­

чески совпадают.

Отметим, что мы не относим к ЧМП методы решения многокритери­альных задач математического программирования, в которых: 1) ЛПР по­стулирует некоторые принципы, которым должно удовлетворять решение (например, принцип равномерного приближения к экстремальным значени­ям по всем критериям); 2) после задания ЛПР желаемой цели достигается наилучшее приближение к ней за счет изменения области допустимых зна­чений переменных (системная оптимизация [18]).

Во многих ЧМП, обычно, используются два вспомогательных преоб­разования.

Перед решением задачи рекомендуется произвести нормирование це­левых функций С_к(х), целей а_к, порогов 1_к, например,

(2.11)

где С_k(х), С_k(х) - соответственно минимальное и максимальное значе­ния. В большинстве ЧМП наряду с х¹ вычисляются экстремальные (или локально-оптимальные) решения (х), получаемые при попытках оптими­зировать какой-либо один критерий C_V Обозначим вектор целевых функций решения (х)_у оптимального по критерию С_V, через

z_v= (y_1v ,…,y_Nv), где С_kv = С_к(х_у). (2.12)

Анализ матрицы У способствует осознанию диапазона допустимых альтернатив. В частности, сравнение (у_п,.,y_NN.) и помогает ЛПР оце­

нить реалистичность и степень достижения поставленной цели.

2.3 Задача линейного программирования

В связи с тем, что в разделе 3 задача оптимизации товарного ассорти­мента решается методом линейного программирования, приведем краткое изложение основ этого метода решения задач оптимизации как в детерми­нированной, так и в нечеткой постановке.

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

Методы решения задачи линейного программирования (ЗЛП) хорошо раз-работаны, в частности, их подробное описание можно найти в [5,11,12,14, 15,20,23-27].

Постановка задач математического программирования отличается большим разнообразием. В общем случае задача математического програм­мирования ставится следующим образом:

Найти вектор X^T = (х₁, х₂,...,х_п), удовлетворяющий системе ограниче­ний

g_i(Х) = Ь, i= 1,2,...,k, (2.13)

g_i(Х) Ь, i = k+ 1,k + 2,...,m, (2.14)

и доставляющий экстремум функции

Z =f(Х). (2.15)

При этом предполагается, что известны функции g_l(X) и f(X). Функ-ция Z называется целевой функцией.

Обычно на некоторые или все переменные накладывается условие не-отрицательности. Кроме того, ограничением может служить условие цело- численности некоторых или всех компонент решения

Уравнения (2.13) называется связями, а неравенства (2.14) – неравен-ствами ограничений.

Если система ограничений и целевая функция являются линейными, задача называется задачей линейного программирования. В противном слу-чае она называется задачей нелинейного программирования(ЗНП).

Рассмотрим задачу линейного программирования:

минимизировать , (2.16)

при ограничениях

(2.17)

(2.18)

Отметим, что ограничения(2.17) могут быть двусторонними.

Определение 1. Планом или допустимым решением задачи линей-ного программирования называется вектор , удовлетворя-ющий ограничениям и связям задачи.

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

Если решение существует, то система (2.17, 2.18) называется сов-местной, в противном случае – система несовместная.

Если столбцы матрицы (2.17) линейно независимая, то план называ-ется опорным.

Каждое из неравенств (2.17) описывает полупространство n-мер-

ного пространства, ограниченное гиперплоскостью

(2.19)

Если система совместна, то она образует многогранник решений в n-мерном пространстве. При этом координаты каждой точки, принадлежащей этому многограннику, являются решением системы ограничений.

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

Каждая точка многогранника решений является вектором n–мерного пространства.

Определение 3. Точка А, для которой выполняются условия

(2.20)

называется выпуклой линейной комбинацией точек

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

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

Теорема 1. Замкнутый, ограниченный, выпуклый многогранник является линейной комбинацией своих угловых точек.

Если система ограничений совместна, то полупространства, ограниченный гиперплоскостями (2.17), образуют многогранник решений в n-мер-ном пространстве.

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

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

Теорема 3. Если матрица СЛАУ (2.17) не вырожденная и ЗЛП имеет решение, то оно является угловой точкой многогранника решения.

Теорема 4.Если Х – угловая точка многогранника решений, то векторы-столбцы матрицы (2.17), соответствующие (2.18), являются линейно независимыми.

Следствие 1. Угловая точка многогранника решений имеет не болееmположительных компонентов.

Следствие 2. Каждой угловой точке многогранника решений соответствует не более mлинейно независимых столбцов матрицы СЛАУ.

Таким образом, если целевая функция ЗЛП ограничена на многограннике решений, то:

1. Существует такая угловая точка, в которой целевая функция дости-гает экстремума.

2. Каждый опорный план соответствует угловой точке многогранника решений.

3. Для решения ЗЛП необходимо исследовать только угловые точки многогранника решений.

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

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

При решении практических задач ЛП наибольшее распространение получили методы двух типов: симплексные (конечные) и методы внут-ренней точки (итерационные).В учебной литературе обычно рассматрива-

ется симплекс-метод, предложенный Данцигом в 1947 году

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

Симплекс-метод состоит из трех основных элементов:

1. Определение первоначального базисного решения.

2. Правила перехода к очередному лучшему решению.

3. Проверка оптимальности решения.

Для использования симплекс-метода ЗЛП должна быть приведена к каноническому виду, то есть, система ограничений должна быть представ-лена в виде системы уравнений. Это делается путем введения дополнитель-ных переменных.

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

Двойственный симплекс-метод (метод последовательного уточнения оценок), по сути , является применением симплекс-метода к двойственной задаче.

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

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

В системе Mathcad ЗЛП решается с помощью встроенных функций Minimize и Maximize.