Линейное программирование (лекция)

Исследование операций

Контрольные вопросы по предмету

0


Подпишитесь на бесплатную рассылку видео-курсов:

Смотреть лекцию по частям


Текст видеолекции

Содержание лекции:

  1. Основные понятия и определения.
  2. Математическая модель задачи.
  3. Графический метод решения.
  4. Табличный симплекс-метод.

 

  1. Основные понятия и определения

 

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

Полагают, что термин «исследование операций» впервые ввел английский ученый А. Раув, который в 1938 г. руководил научной группой, разрабатывающей эффективные средства противовоздушной обороны Англии. Становление исследования операций как научной дисциплины относят к 1952 г. и связывают с работами П. Блекетта, Ф. Морза и Д. Кимбелла. Последние два автора в том же году опубликовали книгу «Методы исследования операций».

Составной частью научной дисциплины «исследование операций» является математическое программирование. Наименование предмета — «математическое программирование» — связано с тем, что целью решения задач является выбор программы действий и изучаются методы решения задач условной оптимизации. Такие задачи находят применение в различных областях практической деятельности человека.

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

В последующем одни разделы математического программирования получили большее развитие, другие — меньшее. Наиболее впечатляющий результат получен в работе Л. Хачияна, который, будучи научным сотрудником вычислительного центра АН СССР, доказал в 1980 г., что для задач линейного программирования — одного из разделов математического программирования — существует теоретически эффективный (полиномиально - временной) алгоритм для их решения. На основе этой работы американский математик Н. Кармаркар разработал такой алгоритм1.

Характерной особенностью задач математического программирования является их большой объем, и поэтому реальные задачи недоступны для ручных вычислений. Для их решения разрабатываются компьютерные программы.

Процесс решения задачи математического программирования обычно включает следующие этапы:

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

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

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

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

4. Выбор или написание компьютерной программы решения задачи. Для решения задачи с помощью компьютера необходимо выбрать существующую программу решения соответствующего класса задач или написать программу при ее отсутствии. Для решения задач линейного программирования в настоящее время существует достаточно много компьютерных программ, доступных в Интернете (см. http://softsearch.ru/). Для учебных целей можно рекомендовать программу Simplexwin (см. http://softsearch.ru/programs/56-557-simplexwin-download.shtml).

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

6. Анализ полученного решения. Производится формальный и содержательный анализ полученного решения (анализ на чувствительность).

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

Введем обозначения, используемые в задачах линейного программирования (ЗЛП).

f(x) – целевая функция (функция цели), xÎX – переменные, Х – допустимое множество решений, где X={xÎ Rn : g j(x)£ 0, j = 1...m}, f, g j - линейны для любого j, g j – функции системы ограничений, Rn – n-мерное пространство.

 

Определение:

Функция f  называется линейной, если справедливо равенство

f(l1x1+ l2x2) = l1f(x1) + l2f(x2), где liÎR, xiÎX.

В n-мерном пространстве линейная функция может быть определена так:

f(x) = (c,x)

f(x) = c1x1+ ....+ cnxn

 

 

Ограничения  имеют вид системы неравенств

Расширим класс задач:

,

 то есть можно передвинуть область решений в n-мерном пространстве.

Определение:

Если при задании допустимого множества X используются только неравенства, то это ЗЛП в стандартной форме.

Определение:

Если при задании X используются только равенства, то это задача линейного программирования в канонической форме. 

Возможны смешанные задачи.

ЗЛП в канонической форме эквивалентна некоторой задаче в стандартной форме и наоборот.

Пусть есть только неравенства. Как от них избавиться?

Надо расширить пространство: в каждое из неравенств добавляется еще одна координата (переменная) xn+i³ 0, т. е.

 

 

Ограничения типа равенств можно представить в виде двух ограничений типа неравенств. Пусть (l , x) = 0 , тогда (l , x) £ 0 и (l , x) ³ 0.

Матричная  форма записи ЗЛП

X = {A×x = b , x ³ 0 , xÎ Rn};    A - матрица размерности m´n ;  x - вектор размерности n ;     b - вектор размерности m ;

f(x) = (c,x) - линейная функция;

 f(x) – ЗЛП

Определение

 Множество X называется выпуклым, если для "x1,x2ÎX, lÎ[0,1], выполняется условие lx1+(1-l)x2ÎX, то есть вместе с любыми двумя точками оно содержит и отрезок их соединяющий.

На рис. 1 изображено выпуклое множество, на рис. 2 - невыпуклое.

 

 

Рис. 1                                Рис. 2

 

 

 

 

 

Определение

 Точка Z называется выпуклой комбинацией точек x1,x2,...,xm, если

, ,,

Теорема (о выпуклом множестве)

Выпуклое множество X содержит все выпуклые комбинации своих точек.

Теорема

Пересечение выпуклых множеств выпукло.

Определение

Функция f(x) называется выпуклой, если её область определения выпукла и для "x1,x2ÎX, lÎ(0,1) выполняется неравенство f(lx1+(1-l)x2)£ lf(x1)+(1-l)f(x2) (функция выпукла, если ее график находится под хордой).

 

 
   

 

 

 

 

 

Рис. 3

 

Определение

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

Теорема ( о представлении )

Всякая точка допустимого  ограниченного множества ЗЛП допускает представление в виде выпуклой комбинации его крайних точек.

 (без доказательства) 

Теорема ( о существовании оптимальной точки ) :

Если  целевая функция на допустимом множестве ЗЛП ограничена  снизу, то оптимальная точка существует.  

(без доказательства)

 

  1. 2.      Математическая модель задачи

 

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

Найти значения п неизвестных , х2, ..., хп, доставляющих экстремум (минимум или максимум) функции

                                                    (1.1)

и удовлетворяющих ограничениям

                            (1.2)

а также условиям неотрицательности

                                                      (1.3)

 

Задачу (1.1)-(1.3) называют задачей математического программирования. Функцию (1.1) называют функцией цели, а ограничения (1.2)-(1.3) - областью определения функции цели (1.1), или областью допустимых решений задачи.

Значения переменных х1 х2, ..., хn , удовлетворяющих ограничениям (1.2)-(1.3), называют допустимым решением задачи (1.1)-(1.3). Допустимое решение называют оптимальным, если оно доставляет экстремум функции (1.1).

Классификация задач математического программирования

В зависимости от вида функции (1.1) и ограничений (1.2)-(1.3) производят классификацию задач математического программирования.

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

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

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

• выпуклое программирование;

• квадратичное программирование;

• многоэкстремальные задачи.

Если система ограничений задачи (1.1)-(1.3) дополнена требованием целочисленности переменных, то такую задачу называют задачей целочисленного или дискретного программирования. Особое значение имеют задачи линейного целочисленного программирования.

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

Существуют также другие виды задач математического программирования (стохастическое, 0-1 программирование, геометрическое и т.п.). Выделение отдельных классов задач математического программирования связано с тем, что не существует единого метода решения таких задач в общем виде. Поэтому для отдельных выделенных классов задач разрабатывают методы решения, учитывающие особенности данного класса.

Построение математических моделей

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

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

а) выбрать переменные (неизвестные) задачи;

б) построить (линейную) функцию цели;

в) учесть все ограничения задачи.

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

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

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

Пример (ресурсная задача).

Для изготовления изделий типа А и В используется сырье трех видов, запасы каждого из которых Р1, Р2, Р3. На производство одного изделия типа А требуется затратить а1 кг сырья первого вида, а2 кг сырья второго вида, а3 кг сырья третьего вида. На одно изделие типа В расходуется соответственно b1, b2, b3 кг сырья каждого вида. Прибыль от реализации единицы изделия А составляет α /ден.ед./, а изделия В – β /ден.ед./. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.

Решение.

Экономико-математическая модель задачи

Запишем исходные данные в виде таблицы:

Сырье

Затраты сырья на 1 изделие

Запасы сырья  

Изделие типа А  

Изделие типа В  

Р1

4

1

220

Р2

1

2

140

Р3

4

3

260

Цена 1 изделия

6

3

 

 

Пусть x1 – неизвестное количество изделий типа А, x2 – неизвестное количество изделий типа В.

Тогда система ограничений имеет вид

                                 (1)

Функцией цели F является

F= 6×x1 + 3×x2®max                                   (2)

 Необходимо найти такие неотрицательные x1, x2, которые удовлетворяют ограничениям (1) и обращают в максимум функцию цели (2).

  1. 3.      Графический метод решения

 

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

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

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

Пусть на плоскости введена прямоугольная система координат Х?ОХ2. Тогда каждой точке М плоскости соответствует пара чисел (х? х2), называемых координатами этой точки. Чтобы найти координаты точки М, необходимо опустить перпендикуляры из этой точки на оси координат Ох? и Ох2.

Говорят, что координаты точки М(х?, х2) удовлетворяют уравнению g(х? х2)=0 некоторой линии, если при подстановке координат этой точки в уравнение последнее обращается в тождество.

Линейному уравнению

                                       (1.4)

на плоскости соответствует прямая. Другими словами, множество точек плоскости Х?Ох2, координаты которых удовлетворяют данному уравнению, образуют прямую линию.

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

Если b#0, то для простоты вычислений удобно находить точки, в которых прямая пересекает оси координат. Для   этого полагая х? = 0, находим х2 = b/a2 ,полагая х2 =0, находим х?= b/a2. Через две найденные точки (0, b/a2 ) и (b/a1, 0) проводим искомую прямую (рис. 4).

 

            Рис.  4

Если b = 0, то прямая (1.4) проходит через начало координат (0, 0). Поэтому для нахождения второй точки можно взять любое отличное от нуля значение одной координаты, например, х? = 1.

Тогда х2 = x2=-a?/a2. В этом случае прямая будет проходить, очевидно, через точки (0, 0) и  (1, - a?/a2). 

Наконец, если имеется уравнение вида х? =b, либо х2 =b, то прямая параллельна оси Ох2 (соответственно Ох?).

Линейному неравенству

                                       (1.5)

на плоскости х?Ох2 соответствует полуплоскость, расположенная по одну сторону от граничной прямой .

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

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

а) построить область определения функции цели;

б) построить направляющий вектор С = (с?, с2);

в) найти точку области допустимых решений, в которой функция цели достигает экстремума;

г) найти экстремальное значение функции цели.

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

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

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

Направляющий вектор С указывает направление возрастания функции цели. Направляющий вектор имеет начало в начале координат, а конец - в точке ?, с2), где с? и с2 - значения коэффициентов при неизвестных х? и х2 в функции цели. Линия одного уровня (одного значения) функции цели будет располагаться перпендикулярно направляющему вектору.

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

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

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

Алгоритм графического решения задачи линейного программирования (n = 2)

Шаг 1. Ввести на плоскости прямоугольную систему координат х?Ох2.

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

Шаг 3. Построить направляющий вектор С = (с1,с2). Начало вектора С находится в начале координат, конец — в точке (сь с2).

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

Шаг 5. Выписать найденное решение и вычислить соответствующее ему экстремальное значение функции цели.

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

Особые случаи решения задач

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

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

 

 

Рис.  5

 

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

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

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

В заключение данного параграфа заметим, что любую задачу линейного программирования можно решать либо только на максимум, либо только на минимум. Так, если в задаче требуется найти минимум функции цели ƒ, то мы можем поменять знаки в выражении функции на противоположные, т.е. сформировать новую функцию цели F=ƒ,и решать задачу на максимум. Аналогично можно перейти от задачи максимизации к задаче минимизации. 

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

Пример 1

Найти значения х? и х2, для которых

 

при условиях

 

 

Введем на плоскости прямоугольную систему координат х?Ох2 и построим область определения функции цели. Рассмотрим первое неравенство системы ограничений

 

 

 

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

 

Это уравнение прямой, проходящей через начало координат. Другими словами, данная прямая проходит через точку 0(0, 0).

Найдем другую точку, лежащую на данной прямой. Для этого положим х2=1. Тогда    X? =3. Следовательно, прямая проходит и через точку (3, 1), Построим ее на плоскости, обозначив римской цифрой I (рис. 3.2).

 

 

Определим теперь искомую полуплоскость. Для испытания возьмем точку (1, 1), лежащую над данной прямой. Подставим координаты точки в уравнение прямой, получим 1-3·1 = -2<0, т.е. данное неравенство выполняется. Следовательно, искомая полуплоскость расположена над прямой. Отметим этот факт стрелочкой на прямой I.

Рассмотрим второе неравенство системы ограничений:

 

 

Уравнение границы соответствующей полуплоскости

 

Так как правая часть уравнения прямой не равна нулю, то эта прямая не проходит через начало координат.

Полагая х? =0, получим х2 =10, полагая х2 =0, получим XI =10. Следовательно, искомая прямая проходит через точки (0, 10) и (10, 0). Построим данную прямую, обозначив ее римской цифрой II (рис. 3.3).

Для нахождения искомой полуплоскости испытаем начало координат О (0, 0). Получим 0+0 < 10. Таким образом, искомая полуплоскость расположен по ту же сторону от прямой, что и тачало координат. Отметим этот факт стрелочкой на прямой.

 

Рассмотрим третье неравенство системы ограничений: 

 

 

Уравнение границы полуплоскости:

 

Полагая х? = 0, получим х2 = 2; полагая х2 = 0, получим х? = 3. Следовательно, прямая проходит через точки (0, 2) и (3, 0). Построим прямую, обозначив ее римской цифрой III (см. рис. 3.3).

 

 

Для испытания выбираем, начло координат. Получим 0+0 < 6. Неравенство не выполняется. Следовательно, искомая полуплоскость расположена по другую сторону от прямой, чем начало координат. Отметим этот факт стрелочкой.

Рассмотрим четвертое неравенство

 

 

Уравнение границы полуплоскости

 

задает прямую, параллельную оси Ох2. Изобразим ее на рис. 3.3, обозначив римской цифрой IV. Испытывая начало координат, получим 0 < 1. Заданное неравенство не выполняется. Искомая полуплоскость находится справа от прямой. Рассматривая неравенство

 

получим уравнение граничной прямой х2 = 5, расположенной параллельно оси Ох? (на рис. 3.3 прямая V). Искомая полуплоскость находится ниже граничной прямой.

 

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

Построим направляющий вектор С, начало которого - в начале координат, конец в точке (-3, 2) (см. рис. 3.3). Проведем линию одного уровня функции цели перпендикулярно направляющему вектору С и будем смещать ее в направлении, противоположном направлению вектора, так как нам необходимо отыскать минимум функции цели. Смещать эту линию будем до тех пор, пока это возможно, т.е. пока она будет иметь только одну общую точку с областью определения функции цели. Легко видеть, что такой точкой будет точка С. Следовательно, в точке С достигается минимум функции цели.

Точка С образована пересечением граничных прямых I и II, поэтому для определения ее координат решим систему линейных уравнений:

 

 

Отсюда находим х?= 15/2, х2=5/2.Соответствующее значение функции цели

 

 

Решение задачи записываем так:

 

Пример 2 (ресурсная задача)

Используем стандартную форму постановки задачи.

                                 (1)

F= 6×x1 + 3×x2®max                                   (2)                                                               

Необходимо найти такие неотрицательные x1 и x2, которые удовлетворяют ограничениям (1) и обращают в максимум функцию цели (2).

1) Для построения области решений первого неравенства

 

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

 

а) x1=0; x2=220; M1(0; 220);

б) x2=0; x1=55; N1(55; 0).

 

2) x1+2x2£140 Þ x1+2x2=140

а) x1=0; x2=70; M2(0; 70);

б) x2=0; x1=140; N2(140; 0).

 

3) 4x1+3x2£260 Þ 4x1+3x2=260

а) x1=0; x2=86,67; M3(0; 86,67);

б) x2=0; x1=65; N3(65; 0).

 

4) x1³0 Þ x1=0;

5) x2³0 Þ x2=0.

Областью решений системы линейных неравенств (1) является выпуклый замкнутый многоугольник OABCD.

6) Построим направление наискорейшего возрастания функции цели

F= 6×x1 + 3×x2

Его указывает вектор .

N

 

 

D

 

 

С 

 

 

B

 

 

A

 

 

 

 

7) Уровень максимального значения функции цели проходит через угловую точку С (50;20), которая является пересечением прямых  и 4x1+3x2=260.

Итак, если произвести количество изделий вида А  x1=50 (ед.) и количество изделий вида B x2=20 (ед.), то получим максимальное значение функции цели.

Fmax=6×50 + 3×20=360 (руб.)

 

Ответ: для получения наибольшей прибыли Fmax=360 руб. необходимо произвести изделий вида А  x1=50 ед. и изделий вида B x2=20 ед.

 

  1. 4.      Табличный симплекс-метод

 

Универсальным вычислительным методом решения задачи ЛП является так называемый Симплекс-метод. Идея метода состоит в последовательном “улучшении” планов задачи по определенному критерию до получения оптимального решения.

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

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

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

 

 

 

Алгоритм симплекс-метода. 

Шаг I:  Приведение математической модели задачи к каноническому виду (систему активных ограничений типа неравенств привести к уравнениям путем введения дополнительных “искусственных” переменных).

Шаг II: Выбор начального базисного решения.

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

Шаг IV: Продолжение поиска допустимых базисных решений. (Если полученное решение не является оптимальным, то симплекс-метод позволяет перейти к смежному допустимому базисному решению).

Шаг V: Переход на соседнюю вершину многогранника ОДР. Смежное допустимое базисное решение отличается только одной базисной переменной (независимая переменная становится базисной, а одна из базисных переменных становится независимой). 

Критерий оптимальности. Обозначим относительную оценку небазисной переменной  через 

 

Оценки базисных переменных.

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

Формулы пересчета исходной таблицы:

1). r-я  строка преобразуется так:

   

 - т.е. меняет знак.

2). Столбец с номером  s преобразуется так :

 

3). Остальные элементы пересчитываются так:

 

 

Особые случаи решения задач симплекс - алгоритмом

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

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

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

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

Проиллюстрируем все выше сказанное примером.

Пример  (ресурсная задача)

 

Составим систему уравнений. Для этого введем три дополнительные переменные x3, x4, x5.

Тогда систему ограничений (1) можно переписать в виде системы уравнений:

                      (3)

Функция цели при этом остается прежней:

F= 6×x1 + 3×x2®max                                   (2)

Необходимо найти такие неотрицательные x1, x2, x3, x4, x5, которые удовлетворяют системе ограничений (3) и обращают в максимум функцию цели (2).

В качестве базисных переменных выбираем дополнительные переменные x3, x4, x5 .

Заносим коэффициенты из системы в таблицу 1.

Таблица 1

Неизвестные

 

Базис

x1

x2

x3

x4

x5

bi

x3

4

1

1

0

0

220

x4

1

2

0

1

0

140

x5

4

3

0

0

1

260

m+1

-6

-3

0

0

0

0

Полагаем свободные переменные x1 , x2   равными нулю:

x1=0;  x2=0,

а базисное решение получаем из 1-го и последнего столбцов:

x3=220;  x4=140;  x5=260.

При этом функция цели F=0.

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

min(-6; -3) =-6,

следовательно, первый столбец x1 является разрешающим.  Он показывает, что переменную x1 надо вводить в базис. Чтобы определить вместо какой переменной, будем делить элементы последнего столбца на соответствующие элементы разрешающего столбца:

 

Из этих чисел выбираем минимальное:

min(55; 140; 65)=55.

Это число соответствует первой строке, которая называется разрешающей. Она показывает, какую переменную надо выводить из базиса, т. е. x3 вывести из базиса, а на ее место поставить x1. Элемент, стоящий на пересечении разрешающих строки и столбца, называется разрешающим: а*=4.

Заполним симплекс-таблицу 2.

Таблица 2

Неизвестные

 

Базис

x1

x2

x3

x4

x5

bi

x1

1

0,25

0,25

0

0

55

x4

0

1,75

-0,25

1

0

85

x5

0

2

-1

0

1

40

m+1

0

-1,5

1,5

0

0

330

Делим все элементы разрешающей строки таблицы 1 на разрешающий элемент а*=4. Элементы разрешающего столбца, кроме разрешающего элемента, обнуляем.

Остальные элементы определяем по правилу прямоугольника:

             а*                B

 

             A                  aij

Свободными в этом решении являются x2 и x3:

x2=0, x3=0, тогда  x1=55,  x4=85, x5=40,  F=330.

Проверяем полученное решение на оптимальность. В индексной строке имеется отрицательное число -1,5, значит, решение не является оптимальным. Второй столбец x2 является разрешающим, он показывает, что переменную xнадо вводить в базис. Чтобы определить вместо какой переменной, будем делить элементы последнего столбца на соответствующие элементы разрешающего столбца:

.

Из этих чисел выбираем минимальное:

min(220; 48,57; 20)=20.

Это число соответствует третьей строке, которая называется разрешающей, т. е. x5 вывести из базиса, а на ее место поставить x2. Элемент а*=2 – разрешающий.

Заполним симплекс-таблицу 3.

Таблица 3

Неизвестные

 

Базис

x1

x2

x3

x4

x5

bi

x1

1

0

0,375

0

-0,125

50

x4

0

0

0,625

1

-0,875

50

x2

0

1

-0,5

0

0,5

20

m+1

0

0

0,75

0

0,75

360

Свободными в этом решении являются x3 и x5:

x3=0; x5=0, тогда  x1=50,  x2=20, x4=50,   F=360.

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

 

Список литературы

1. Пантелеев, А.В. Методы оптимизации в примерах и задачах. - Москва: Высшая школа, 2008.

2. Струченков, В.И. Методы оптимизации. Основы теории, задачи, обучающие компьютерные программы. - Москва: Экзамен, 2005.

3. Е. С. Вентцель, Исследование операций: задачи, принципы, методология. Из-во Дрофа, 2006.

4. Е. В. Шикин, Г. Е. Шикина, Исследование операций. Из-во Проспект, 2006.