WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 11 |

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

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

4.3 ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Общая задача линейного программирования [2] заключается в отыскании вектора (u1, u2,..., un) максимизирующего критерий оптимальности (функцию цели задачи) Q (u) = C1u1 + C2u2 +... + Cnun (4.1) при ограничениях линейного типа в виде равенств:

a11u1 + a21u2 +... + a1nun = b1, a u1 + a22u2 +... + a2nun = b2, (4.2)...

a u1 + am2u2 +... + amnun = bm, m в виде неравенств:

am+11u1 + am+12u2 +... + am+1nun bm+1,... (4.3) ac1u1 + ac2u2 +... + acnun bc, и ограничениях на переменные состояния u1 0, u2 0, …, un 0. (4.4) Эта задача при наличии двух переменных u1 и u2 имеет наглядное геометрическое представление.

Пусть целевая функция имеет вид Q (u) = C1u1 + C2u2. На плоскости переменных u1 и u2, если придать Q (u) некоторое постоянное значение Q (u) = const, например, является не чем иным как линиями равного значения уровня. Причем, при u2 = u1 = 0 эта линия сжимается в точку (рис. 4.1), при Q0 = 0 имеем C1u1 + C2u2 = 0 и линия равного уровня Q0 Q является прямой линией, проходящей через точки, 0 и 0,.

CC uQ Q возрастает CQ0 u Q = CРис. 4.1 Геометрическое представление целевой функции Если теперь эту линию перемещать параллельно самой себе (рис. 4.1), то величина Q0, а, следовательно, и значение целевой функции Q (u) будет изменяться. Увеличению целевой функции соответствует перемещение в направлении, указанном на рис. 4.1 стрелкой.

Ограничения или условия типа равенств, называемые также связью, на плоскости u1, u2 изображаются так же, как целевая функция, прямыми линиями (рис. 4.2).

uЕсли связь a11u1 + a12u2 = b1, то ей "убивается" одна степень свободы, т.е.

число переменных, которыми можно варьировать, определяется разноbстью между числом переменных u, = 1, n и числом ограниaчений типа равенств (m) – = n - m (m < n). Эти переменные называются свободными переменными, а число определяет число степеней свободы.

Ограничения типа нера- венств оставляют ту же степень свободы, b1 uпоэтому их может быть сколько угодно. Эти ограничения опредеaРис. 4.2 Геометрическое представление связей типа равенства ляют только область допустимых решений.

uНеравенства a21u1 + +a22u2 b2, a31u1 + a32u2 b3 разделяют всю плоскость b(u1, u2) на две области: запрещенную и разрешенную a(рис. 4.3). Как правило, при геометрическом представлении ограничеbний типа неравенств на плоскости наносят штриховку в сторону запреa A щенной области. На рис. 4.3 разрешенной областью является область B АВС0, эта область всегда представляет собой выпуклый многогранник.

В задачах линейного программирования принято максимизиро C вать функцию цели Q, поэтому оптимальное решение всегда лежит в b3 u 0 b2 вершине допустимого многогранника, образованного ограниченияaaми.

Рис. 4.3 Геометрическое представле- П р и м е р 4.1.

Пусть Q(u) = u1 + u2 max, при наличии ограничений на переменные состояния 2u1 + u2 1, u1 + 2u2 1, u1 0, u2 0.

На фазовой плоскости U определяется область допустимых решений АВС0, которая ограничивается прямыми линиями 2u1 + u2 = 1, u1 + 2u2 = 1, u1 = 0, u2 = 0 (рис.

4.4).

u2u1 + u2 = l A B C 1 u u1 + u2 = Q0 u1 + 2u2 = Рис. 4.4 Геометрическая интерпретация задачи линейного программирования Q Q Необходимое условие экстремума функции дает, что = 1, = 1, эти производные непрерывны и u1 uне обращаются в нуль, следовательно, экстремальное значение Q достигается лишь на границе области U.

Критерий оптимальности имеет постоянное значение Q0 вдоль линии l, определяемой уравнением u1 + u= Q0. Если эту линию перемещать параллельно самой себе, то величина Q0, а, следовательно, и значение критерия Q(u) будет изменяться. Увеличению критерия оптимальности соответствует перемещение линии в направлении, указанном стрелкой, ее предельное положение, когда она проходит через точку В, являющуюся вершиной многоугольника АВС0 допустимых решений, отвечает максимальному значению Q(u). Это максимальное значение определяется координатами вершины В, т.е. координатами точки пере1 1 сечения уравнений 2u1 + u2 = 1, u1 + 2u2 = 1; u1опт = ; u2опт = Qmax =.

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

Если допустимая область решений является незамкнутой областью, то максимальное значение критерия оптимальности обеспечивается при бесконечно больших значениях переменных u1 и u2.

4.4 КАНОНИЧЕСКАЯ ФОРМА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Различные методы задач линейного программирования предъявляют определенные требования к типам ограничений. Так, некоторые из них требуют, чтобы ограничения были только типа равенств, т.е.

Q(u) = C1u1 + C2u2+... + Cnun max, при условии a11u1 + a12u2 +..., + a1nun = b1;

a21u2 + a22u2 +..., + a2nun = b2;

...

am1u1 + am2u2 +..., + amnun = bm;

u1 0, u2 0, un 0.

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

Общую задачу линейного программирования (4.1) – (4.4) можно свести к канонической форме введением дополнительных переменных un+, i = 1, l -m. Для этого в каждом неравенстве прибавляется дополнительная переменная, которая превращает неравенство в равенство am+11u1 + am+12 +.., + am+1n un + un+1 = bm+1,..., al1u1 + al2 u2 +..., + aln un + un+l -m = bl тогда система ограничений может быть записана в единой форме n+l -m u = b, = 1, l.

aj j j =Дополнительные переменные формально могут быть включены в критерий оптимальности исходной задачи, т.е.

n+l-m Q(u) = u, где С = 0 для > n.

C =Таким образом, общую задачу линейного программирования (4.1) – (4.4) свели к канонической форме n+ j -m Q(u) = u max (4.5) C =при ограничениях n+l -m u = b, = 1, l, u 0, j = 1, n + l - m. (4.6) aj j j j =Геометрическое представление можно осуществить только в случае двух переменных. Пусть требуется найти максимум функции Q(u) = C1u1 + C2u2 при ограничениях a1u1 + a2u2 < b, u1 0, u2 0.

В рассмотрение вводится дополнительная переменная u3, которая неравенство u3 0 превращает в равенство a1u1 + a2u2 + u3 = b или a1u1 + a2u2 = b - u3.

Геометрическое представление получаемой области допустимых решений после введения дополнительной переменной u3 изображено на рис. 4.5.

ub aРис. 4.5 Геометри- u3 < ческое представление сведения огра u3 > ничений типа неравенств к ограb uничениям типа ра u3 = aвенств Полученная каноническая задача Q (u) = C1u1 + C2u1 max при ограничениях a1u1 + a2u2 + u3 = b, u1 0, u2 0, u3 0 является равноценной задачей по отношению к исходной.

4.5 СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Основным методом решения задач линейного программирования является симплексный метод. Для его изложения необходимо ввести некоторые определения.

Переменные (u1, u2,..., un), удовлетворяющие условиям (4.2) – (4.4) общей задачи линейного программирования называются планом задачи линейного программирования.

n План (u1, u2,..., un) = U называется опорным, если в разложении P0= при u > 0, – линейно u =независимы.

План, максимизирующий линейный критерий оптимальности (4.1) называется оптимальным планом или решением задачи линейного программирования.

В теории линейного программирования строго доказывается [2], что множество всех планов задачи линейного программирования выпукло. Критерий оптимальности (4.1) достигает своего максимума в крайней точке этой выпуклой области.

Каждой крайней точке выпуклой области соответствует m линейно независимых векторов из системы 1, 2,..., n.

Симплексный метод позволяет, отталкиваясь от известного опорного плана задачи линейного программирования, за конечное число итераций получить ее решение. Так как оптимальный план связан с системой m линейно независимых векторов – базисами плана, то поиски разумно ограничить опорными n! m планами, число которых конечно и равно числу сочетаний из n по m Cn =. Как видно, при больших m! значениях m и n отыскать решение путем перебора всех опорных планов невозможно. Симплексный метод упорядочивает переход от одного опорного плана к другому таким образом, чтобы критерий оптимальности принимал значение большее или равное предыдущему. Суть алгоритма симплексного метода сводится к следующему.

1 Определяется некоторый опорный план, которому соответствует вершина области допустимых решений ( u1, u2,..., un ).

2 Найденный опорный план (вершина) проверяется на оптимальность. Пусть этот план не оптимален.

3 Определяется следующий опорный план (вершина) лучший по отношению к предыдущему в результате движения по ребру. Найденная таким образом вершина проверяется на оптимальность.

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

Использование симплексного метода удобно рассматривать на примере решения задачи линейного программирования для случая двух переменных.

Пусть требуется изготовить два продукта из четырех видов сырья – S1, S2, S3, S4. Требуется определить сколько должно быть изготовлено продукта П1 – u1, продукта П2 – u2, чтобы стоимость их (прибыль) была максимальна Q(u) = 7u1 + 5u2 max, где коэффициенты 7 и 5 характеризуют стоимость изготовления единицы продукта П1 и П2 соответственно. Нормы расхода сырья на единицу соответствующего продукта представлены в табл. 4.1.

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

Таблица 4.Продукт Запас сыП1 Прья Сырье S1 2 3 S2 2 1 S3 0 3 S4 3 0 Цена 7 2u1 + 3u2 19, 2u1 + u2 13, 3u2 15, 3u1 18, u1 0, u2 0.

Симплексный метод, как уже отмечалось раньше, работает с канонической формой задач линейного программирования. Для сведения исходной задачи к канонической вводятся дополнительные переменные u3, u4, u5, u6, позволяющие ограничения типа неравенств u1 0, u2 0, u3 0, u4 0, u5 0, u6 0 преобразовать в ограничения типа равенств 2u1 + 3u2 + u3 = 19, 2u1 + u2 + u4 = 13, 3u2 + u5 = 15, 3u1 + u6 = 18.

Таким образом имеем 6 неизвестных, 4-связи, = 6 – 4 = 2 степени свободы. В качестве свободных переменных выбираются u1 и u2. Полагая u1 = 0, u2 = 0, определяют вершину, дающую базисное решение. Остальные неизвестные находятся из равенств u3 = 19 - 2u1 - 3u2, u4 = 13 - 2u1 - u2, u5 = 15 - 3u2, u6 = 18 - 3u1.

Строится область допустимых решений, которая изображена на рис. 4.6, на этом же рисунке наносится линия l, соответствующая критерию оптимальности Q.

При u1 = u2 = 0 критерий оптимальности Q = 0. Если u, – 1,2 увеличиваются, то и критерий Q увеличивается, следовательно, данная вершина оптимальной не является. Далее необходимо изменять u1, uтаким образом, чтобы критерий увеличивался, т.е. двигаться по ребру, изменяя одну из переменных, а другую оставлять без изменения.

u u4 = u6 = u5 = B 0 C 2 4 6 8 10 12 u Q = u3 = Рис. 4.6 Геометрическое решение задачи линейного программирования Коэффициент в критерии оптимальности при u1 больше, чем при u2, поэтому увеличивать надо u1 до тех пор, пока не будет достигнута следующая вершина, в которой u6 = 0, а u1 = 6, u2 = 0, u3 = 7, u4 = 1, u5 = 15, Q = 42. На этом заканчивается первая итерация.

На второй итерации свободной переменной является u6, u2 = 0. Все переменные выражаются через u6 и u1 2 u1 = 6 - u6, u3 = 7 + u6 - 3u2, u4 = 1+ u6 - u2, 3 3 u5 = 15 - 3u2, Q = 42 - u6 + 5uВ качестве базиса принимается u2 = 0, u6 = 0. Коэффициент в критерии оптимальности при u6 отрицателен, поэтому для его увеличения необходимо изменить u2 до значения, при котором u4 = 0, тогда в полученной вершине u1 = 6, u2 = 1, u3 = 4, u5 = 12, u6 = 0, Q = 47. Критерий увеличился, можно переходить к третьей итерации.

На третьей итерации в качестве базиса выбираются переменные u6 = 0, u4 = 0. Все переменные выражаются через них:

1 2 u1 = 6 - u6, u2 = 1+ u6 - u4, u3 = 4 - u6 + 3u4, 3 3 u5 = 12 - 2u6 + 3u4, Q = 47 + u6 - 5u4.

Движение до следующей вершины осуществляется по ребру u4 = 0, т.е. изменяется в сторону увеличения u6 до значения, при котором u3 = 0. Другие переменные принимают значения u1 = 5, u2 = 3, u5 = 6, u6 = 3, Q = 50. Критерий увеличился, следовательно, можно проводить четвертую итерацию.

На четвертой итерации за базис берется u3 = 0, u4 = 0, движение проводится по ребру u3 = 0 до значения, при котором u5 = 0, тогда, выражая переменные через u3 и u4, получают 1 3 1 1 3 u1 = 5 + u3 - u4, u2 = 3 - u3 + u4, u5 = 6 - u4 + u3, 4 4 2 2 2 9 3 3 u6 = 3 + u4 - u3, Q = 50 + u3 - u4.

4 4 4 В вершине u3 = 0, u5 = 0 имеем u1 = 2, u2 = 5, u4 = 4, u6 = 12, Q = 27.

Критерий оптимальности уменьшается, следовательно, оптимальной вершиной является предыдущая, в которой Q = 50.

5 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Целый ряд интересных и важных видов деятельности можно трактовать как многошаговые процессы решения. Применение классических методов в этих новых областях оказалось полезным, но их диапазон и гибкость явно недостаточным, особенно, когда речь шла о получении численных результатов.

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

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

5.1 ОСНОВНЫЕ ПОНЯТИЯ В динамическом программировании рассматриваются многостадийные процессы принятия решения.

Многостадийные процессы – это такие процессы, в которых решения принимаются на каждой из последовательных стадий.

Динамическое программирование является средством оптимизации математически описанных процессов.

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

При рассмотрении вопросов динамического программирования принята следующая терминология:

а) стадия – единичный элемент, на которые делится весь процесс во времени или в пространстве;

ступень – часть стадии. В любом случае стадия и ступень – это математические конструкции, применяемые для представления в дискретном виде непрерывной переменной;

б) состояние системы характеризуется совокупностью переменных, последние описывают состояние системы на любой стадии процесса;

в) переход от стадии к стадии и от состояния к состоянию описывается функциональными уравнениями;

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

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

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

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 11 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.