Графическое решение задачи распределения ресурсов


 

Пусть для двух видов продукции П1 и П2 требуются трудовые, материальные и финансовые ресурсы. Наличие ресурсов каждого вида и их нормы расхода, необходимые для выпуска единицы продукции, приведены в табл. 5.1.

 

Таблица 5.1

 

  Характеристика Вид продукции   располаг.
  П1 П2 ресурс
Резервы:      
трудовые
материальные
финансовые
выпуск ---
прибыль 8,5 ---
план х1 х2 ---

 

составим математическую модель задачи.

 

ìx1+4x2 £ 14

ï3x1+4x2 £ 18

(5.11) í6x1+2x2 £ 27

îx1 ³ 0, x2 ³ 0.

 

математическая модель представляет собой систему линейных неравенств. Значит ОДР нашей задачи выпуклый многоугольник. Для удобства построения неравенства можно записать в форме, аналогичной уравнениям в отрезках:

 

ìx1/14+x2/7/2 £ 1

ïx1/6+x2/9/2 £ 1

(5.12) íx1/9/2+x2/27/2 £ 1

îx1 ³ 0, x2 ³ 0.

 

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

 

F=x1+x2 ® max (5.13)

 

Эту зависимость представим в виде x2= F-x1. Из графика данного уравнения (Рис. 5.1) следует, что tga = -1, при этом a =135о, а величина F равна отрезку, отсекаемому прямой функции цели на оси координат. Если прямую перемещать параллельно самой себе в направлении, указанном стрелками, то эта величина будет возрастать. Очевидно, что оптимальным решением будут координаты точки С (x*1; x*2). При этом F=F*.

На основании рассмотренного, можно сделать исключительно важный вывод: оптимальным решением являются координаты вершин ОДР. А из этого вывода следует метод решения задачи линейного программирования.

 

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

 

À Найти вершины ОДР, как точки пересечения ограничений.

Á Определить последовательно значения целевой функции в вершинах.

 Вершина, в которой целевая функция приобретает оптимальное значение, является оптимальной вершиной.

à Координаты оптимальной вершины являются оптимальными значениями искомых переменных.

 

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

 

Тот факт, что оптимальное решение находится на вершине ОДР, дает еще два очень важных вывода:

 

À если оптимальным решением являются координаты вершин ОДР, значит, сколько вершин имеет ОДР, столько оптимальных решений может иметь задача.

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

 

Как видно на Рис. 5.1, вершина, координаты которой являются оптимальным решением, определяется углом наклона прямой, описывающей целевую функцию. Значит, каждая вершина будет соответствовать оптимальному решению для некоторой целевой функции. Поясним это на рассмотренном ранее примере. Раньше мы находили оптимальное решение по максимизации суммарного выпуска F1=x1+x2 ® max. Найдем оптимальные решения еще для четырех целевых функций:

 

F2=x2 ® max (максимизация выпуска продукции П2)

F3=x1 ® max (максимизация выпуска продукции П1)

F4=4x1+8,5x2 ® max (максимизация прибыли)

F5=(1+3+6)x1 + (4+4+2)x2 = 10х1+10х2 ® max (минимизация используемых ресурсов).

 

Для каждой целевой функции, так же как и для F1, можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведем в таблицу 5.2, из анализа которой можно сделать вывод: координаты каждой вершины могут быть оптимальным решением в некотором смысле.

 

Таблица 5.2

 

Целевая функция Вершина x1 x2 x1+x2 Прибыль Используемый ресурс
F1=x1+x2 ® max C 1,5 5,5 28,75
F2=x2 ® max A 3,5 3,5 29,75
F3=x1 ® max D 4,5 4,5
F4=4x1+8,5x2 ® max B 33,5
F5= 10х1+10х2

 

Симплексный метод

 

Симплексный метод или метод последовательного улучшения плана является одним из основных методов решения задач ЛП. название симплексный метод берет от слова «симплекс», которым создатель метода Р. Данциг обозначил наложенное на переменные x1, x2 ... xn ограничение x1+x2+ ... +xn=1.

 

þ В математике симплексом в k-мерном пространстве называется совокупность k+1 вершин.

 

Так для плоскости при k=2 симплексом будет треугольник; в пространстве при k=3 симплексом будет тетраэдр, имеющий 4 вершины.

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

 

þ Определение значения целевой функции и переменных в одной вершине считается итерацией.

 

Число итераций в реальных задачах может измеряться сотнями. Вручную, с помощью симплекс-метода, могут быть решены задачи, содержащие не более 10 итераций. Поэтому в реальных задачах применяют ЭВМ и пакеты прикладных программ (ППП).

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

 

ì4x1+9x2 £ 56

(5.14) í5x1+3x2 £ 37

î-x1+2x2 £ 2

 

обращающее в максимум линейную форму:

 

¦=3x1+4x2 (5.15)

 

Вначале перейдем от системы неравенств (5.14) к системе уравнений, добавив к левым частям неравенств неотрицательные переменные x3, x4, x5. Мы получим:

 

ì4x1+9x2+x3+0 . x4+0 . x5=56

(5.16) í5x1+3x2+0 . x3+x4+0 . x5=37

î-x1+2x2+0 . x3+0 . x4+ x5=2

 

¦= 3x1+4x2+0 . x3+0 . x4+0 . x5 (5.17)

 

перепишем теперь систему (5.16) в виде системы 0-уравнений:

 

ì0=56 - (4x1+9x2+1 . x3+0 . x4+0 . x5)

(5.18) í0=37 - (5x1+3x2+0 . x3+1 . x4+0 . x5)

î0=2 - (-x1+2x2+0 . x3+0 . x4+1 . x5)

 

¦=0 - (-3x1-4x2-0 . x3-0 . x4-0 . x5) (5.19)

 

заметим, что система (5.18) может быть записана в виде одного векторного равенства:

 

0=B-(A1x1+A2x2+A3x3+A4x4+A5x5),

 

где вектор-столбец В имеет своими компонентами свободные члены, а векторы A1, A2, ... , A5 - коэффициенты при соответствующих переменных x1, x2, x3, x4, x5. Иными словами:

 

                     
В=   A1=   A2=   A3=   A4=   A5=
      -1                

 

Линейная форма имеет вид: ¦=3x1+4x2+0 . x3+0 . x4+0 . x5.

 

Векторы A3, A4, A5 образуют базис. Это означает, что, присвоив х1=0, х2=0, получаем из (5.16) первое базисное решение: x1=0; x2=0; x3=56; x4=37; x5=2.

При этом значение линейной формы ¦=0. На основании (5.18) строим первую симплексную таблицу.

 

Симплексная таблица строится следующим образом:

 

В заглавной строке пишем последовательно векторы B, A1, A2, A3, A4 , A5. Слева добавляем колонку «Базисные векторы», рядом с ней колонку «С», в которой поставлены коэффициенты при базисных переменных в линейной форме, в данном случае величины С3, С4, С5. В последней строке, называемой индексной, и обозначаемой через ¦ j-Сj, проставляются числа, равные значению линейной формы, в соответствием с уравнением (j=1, 2, 3, 4, 5). В итоге мы имеем таблицу 5.3.

 

Таблица 5.3.

 

Базисные Коэффициенты Вектор свободных
векторы линейной формы С членов В A1 A2 A3 A4 A5
A3
A4
A5 -1
Индексная строка ¦ j-Сj -3 -4

 

Это первая симплексная таблица, соответствующая первому базисному решению: x1=0; x2=0; x3=56; x4=37; x5=2. Значение линейной формы, равное нулю, мы записываем в первой клетке индексной строки.

Т.к. мы решаем задачу на максимум, то из выражения линейной формы видно, что имеет смысл увеличить x1 или x2. Действительно, коэффициенты при этих переменных в скобках отрицательны (а по существу положительны), и если мы положим x1>0 или x2>0, то значение ¦ увеличится. Но эти же коэффициенты с их знаками стоят в индексной строке.

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

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

 

Таким образом, ведущей строкой будет строка A5. На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент. В нашем случае - это число 2.

Теперь мы приступаем к составлению второй таблицы или второго плана. Вместо единичного вектора A5 мы в базис вводим вектор A2. Переход к новому базису, как это известно, эквивалентен элементарному преобразованию матрицы, элементами которой служат числа табл. 5.3. А именно: в новой таблице элемент строки, соответствующий элементу ведущей строки прежней таблицы, равен этому элементу ведущей строки, разделенному на разрешающий элемент. чтобы получить любой другой элемент новой симплексной таблицы, нужно от соответствующего элемента прежней таблицы отнять произведение элемента ведущей строки на элемент ведущего столбца, разделенное на разрешающий элемент. Например, элементу 4 (табл. 5.3) будет соответствовать элемент табл. 5.4:

 

Таким образом, мы переходим ко второй таблице (таблица 5.4). Указанные выше преобразования относятся к столбцам B, A1, A2, A3, A4 , A5.

 

Таблица 5.4.

 

Базисные Коэффициенты Вектор свободных
векторы линейной формы С членов В A1 A2 A3 A4 A5
A3 17/2 -9/2
A4 13/2 -3/2
A5 -1/2 1/2
Индексная строка ¦ j-Сj -5

 

Из табл. 5.4 видно, что значение линейной формы возросло и теперь равно 4. Однако наличие в индексной строке отрицательных чисел свидетельствует о том, что это значение еще можно увеличить. Переходим к следующей симплексной таблице. число «5» определяет ведущий столбец. Находим ведущую строку. Для этого определяем:

 

Итак, разрешающим элементом будет 13/2. Вектор A4 выводим из базиса и вводим вместо него вектор A1. Пересчет коэффициентов осуществляем по указанным выше правилам и получаем таблицу 5.5.

 

Таблица 5.5

 

Базисные Коэффициенты Вектор свободных
векторы линейной формы С членов В A1 A2 A3 A4 A5
A3 33/13 -17/13 -33/13
A1 68/13 2/13 -3/13
A2 47/13 1/13 5/13
Индексная строка ¦ j-Сj 392/13 10/13 11/13

 

В индексной строке нет отрицательных элементов. Следовательно, мы получим оптимальную программу. Оптимальное решение:

 

x1=68/13; x2=47/13; x3=33/13; x4 = x5 = 0.



Дата добавления: 2021-09-25; просмотров: 426;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.024 сек.