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

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

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

Для составления математической модели необходимо:

1. выбрать переменные задачи;

2. составить систему ограничений;

3. задать целевую функцию.

Переменными задачи называются величины х 1 , х 2 ,…, х n , которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора Х = (х 1 , х 2 ,…, х n).

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

Целевой функцией называется функция F(X) = f(х 1 , х 2 ,…, х n) переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти.

Общая задача математического программирования формулируется следующим образом: найти переменные задачи х 1 , х 2 ,…, х n , которые обеспечивают экстремум целевой функции

F(X) = f(х 1 , х 2 ,…, х n) ® max (min) (2)

и удовлетворяют системе ограничений (1).

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

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

2. Примеры составления математических моделей экономических задач

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

1.Задача об оптимальном производственном плане

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

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

Решение.

Обозначим х 1 , х 2 – число единиц продукции соответственно Т 1 и Т 2 , запланированных к производству. Для их изготовления потребуется (х 1 + х 2) единиц ресурса S 1 , (х 1 + 4х 2) единиц ресурса S 2 , (х 1) единиц ресурса S 3 . Потребление ресурсов S 1 , S 2 , S 3 не должно превышать их запасов, соответственно 8, 20 и 5 единиц.

Тогда экономико-математическую модель задачи можно сформулировать так:

Найти план выпуска продукции Х = (х 1 , х 2), удовлетворяющий системе ограничений:

и условию ,

при котором функция принимает максимальное значение.

Задачу можно легко обобщить на случай выпуска n типов продукции с использованием m видов ресурсов.

2.Задача об оптимальном рационе

Имеется два вида корма К 1 и К 2 , содержащие питательные вещества S 1 , S 2 и S 3 . Содержание числа единиц питательных веществ в 1кг каждого вида корма, необходимый минимум питательных веществ, а также стоимость 1кг корма приведены в таблице:

Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

Решение.

Обозначим х 1 , х 2 – количество кормов К 1 и К 2 , входящих в дневной рацион. Тогда этот рацион будет включать (3х 1 + х 2) единиц питательного вещества S 1 , (х 1 +2х 2) единиц вещества S 2 , (х 1 +6х 2) единиц питательно вещества S 3 . Так как содержание питательных веществ S 1 , S 2 и S 3 в рационе должно быть соответственно 9, 8 и 12 единиц, то экономико-математическую модель задачи можно сформулировать так:

Составить дневной рацион Х = (х 1 , х 2), удовлетворяющий системе ограничений:

и условию ,

при котором функция принимает минимальное значение.

Формы записи ЗЛП

В ЗЛП требуется найти экстремум линейной целевой функции:

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

и условии неотрицательности

где а ij , b i , c j ( , ) – заданные постоянные величины.

Так записывается ЗЛП в общей форме. Если система ограничений содержит только неравенства, то ЗЛП представлена в стандартной форме. Канонической (основной) формой записи ЗЛП называется запись, когда система ограничений содержит только равенства. Так что приведенные выше ЗЛП записаны в стандартной форме.

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

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

Ограничение – неравенство (£) можно преобразовать к ограничению-равенству добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство (³) – в ограничение равенство вычитанием из его левой части дополнительной неотрицательной переменной. Число вводимых дополнительных неотрицательных переменных равно числу преобразуемых ограничений-неравенств.

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

Пример 1 . Записать в канонической форме ЗЛП:

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

Решение.

Целевая функция остается без изменений:

Система неравенств преобразуется в систему равенств:

При решении ЗЛП графическим методом требуется переход от канонической формы к стандартной форме.

Для приведения ЗЛП к стандартной форме используется метод Жордана – Гаусса решения СЛАУ. В отличие от метода Гаусса, в котором расширенная матрица системы приводится к ступенчатому виду, в методе Жордана – Гаусса в составе расширенной матрицы формируется единичная матрица. Поэтому обратный ход здесь не требуется.

Для преобразования исходной канонической ЗЛП в эквивалентную стандартную ЗЛП:

а) в расширенной матрице системы ограничений выбирается отличный от нуля элемент a qp . Этот элемент называется разрешающим , а q - я строка и р-й столбец называются разрешающей строкой и разрешающим столбцом .

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

Рассмотрим четыре элемента расширенной матрицы: элемент а ij , подлежащий преобразованию, разрешающий элемент a qp и элементы а i р и a qj . Для нахождения элемента а ij следует из элемента а ij вычесть произведение элементов а i р и a qj , расположенных в противоположных вершинах прямоугольника, деленное на разрешающий элемент a qp:

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

Пример 2 . Привести к стандартному виду:

Решение.

Методом Жордана – Гаусса приведем систему уравнений-ограничений ЗЛП к равносильной системе неравенств. Выберем в качестве разрешающего элемента третий элемент первой строки:

Число -9, полученное в последнем столбце последней строки, необходимо записать в целевую функцию с противоположным знаком. В результате преобразований ЗЛП принимает вид:

Т.к. переменные х 2 и х 3 неотрицательные, то отбросив их, можно записать ЗЛП в симметричном виде:

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

Свойства ЗЛП

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

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

Согласно этому определению многоугольник на рис.1а является выпуклым множеством, а многоугольник на рис.1б таковым не является, т.к. отрезок MN между двумя его точками M и N не полностью принадлежит этому многоугольнику.

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

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

Точка Х называется выпуклой линейной комбинацией точек Х 1 , Х 2 ,…, Х n , если выполняются условия:

Х = α 1 Х 1 +α 2 Х 2 +…+ α n Х n ,

α j ≥ 0, Σα j = 1.

Очевидно, что в частном случае при n = 2 выпуклой линейной комбинацией двух точек является соединяющий их отрезок.

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

Из двух последних свойств следует: если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.

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

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

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

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

В общем виде математическая модель задачи линейного программирования (ЛП) записывается как

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

где x j - неизвестные; a ij , b i , c j - заданные постоянные величины.

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

Математическая модель в более краткой записи имеет вид

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

Определение. Допустимым решением (планом) задачи линейного программирования называется вектор = (x 1 , x 2 ,..., x п), удовлетворяющий системе ограничений.

Множество допустимых решений образует область допустимых решений (ОДР).

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

Базисное допустимое решение (х 1 , х 2 ,..., x r , 0, …, 0) является опорным решением, где r - ранг системы ограничений.

Математическая модель задачи ЛП может быть канонической и неканонической.

7.Решение задач линейного программирования графическим методом . Графики функций-ограничений. Линии уровня.

Графический метод решения задач линейного программирования

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

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

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

где е 1 и е 2 - единичные векторы по осям OX 1 и ОX 2 соответственно; таким образом, = (∂L/∂х 1 , ∂L/∂х 2 ). Координатами вектора являются коэффициенты целевой функции L(). Построениелинии уровня будет рассмотрено подробно при решении практических задач.

Алгоритм решения задач

1. Находим область допустимых решений системы ограничений задачи.

2. Строим вектор .

3. Проводим линию уровня L 0 , которая перпендикулярна .

4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум.

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

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

Где 0 ≤ t ≤ 1, 1 и 2 - оптимальные решения в угловых точках ОДР.

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

5. Находим координаты точки экстремума и значение целевой функции в ней.

Пример 3. Выбор оптимального варианта выпуска изделий

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

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

Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного - 14 р.

Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?

Решение. Обозначим: x 1 - суточный объем выпуска сливочного мороженого, кг; x 2 - суточный объем выпуска шоколадного мороженого, кг.

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

Цены на мороженное известна: соответственно 16руб и 14руб., поэтому целевая функция будет иметь вид:

Установим ограничения по молоку для мороженного. Расход его на сливочное мороженное - 0,8кг, на шоколадное - 0,5кг. Запас молок 400кг. Поэтому первое неравенство будет иметь вид:

0,8х 1 + 0,5х 2 ≤400 – первое неравенство – ограничение. Аналогично составляются остальные неравенства.

В результате получится система неравенств. что область решения каждого неравенства. Это можно сделать, подставив в каждое из неравенств координаты точки О(0:0). В результате получим:

Фигура OABDEF - область допустимых решений. Строим вектор (16; 14). Линия уровня L 0 задается уравнением 16x 1 +14x 2 =Const. Выбираем любое число, например число 0, тогда 16x 1 +14x 2 =0. На рисунке для линии L 0 выбрано некоторое положительное число, не равное нулю. Все линии уровня параллельны между собой. Вектор нормаль линии уровня.

Перемещаем линию уровня по направлению вектора. Точкой выхода L 0 из области допустимых решений является точка D , ее координаты определяются как пересечение прямых, заданных уравнениями:

Решая систему, получим координаты точки D (312,5; 300), в которой и будет оптимальное решение, т.е.

Таким образом, фирма должна выпускать в сутки 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9 200 р.

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

9.Симплекс-метод . Характеристика и алгоритм метода, применимость его.

Для решения задачи симплекс методом необходимо :

1. Указать способ нахождения оптимального опорного решения

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

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

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

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение, в виду несовместимости системы ограничений)

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

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

10.Транспортная задача. Определение, виды, методы нахождения начального решения транспортной задачи.

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

1. Нахождение исходного опорного решения;

2. Проверка этого решения на оптимальность;

3. Переход от одного опорного решения к другому.

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

Покажем, как можно перейти от задачи с ограничениями-неравенствами к основной задаче линейного программирования.

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

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

От поставленной таким образом задачи легко перейти к основной задаче линейного программирования. Действительно, введем обозначения:

где - некоторые новые переменные, которые мы будем называть «добавочными». Согласно условиям (4.1), эти добавочные переменные так же, как и должны быть неотрицательными.

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

Как видно, перед нами в чистом виде основная задача линейного программирования (ОЗЛП). Уравнения (4.3) заданы в форме, уже разрешенной относительно базисных переменных которые выражены через свободные переменные Общее количество переменных равно , из них «первоначальных» и «добавочных». Функция L выражена только через «первоначальные» переменные (коэффициенты при «добавочных» переменных в ней равны нулю).

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

Пример 1 Имеется задача линейного программирования с ограничениями-неравенствами: иайти неотрицательные значения переменных удовлетворяющие условиям

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

Требуется привести эту задачу к виду ОЗЛП.

Решение. Приводим неравенства (4.4) к стандартной форме;

Вводим дополнительные переменные:

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

удовлетворяющие уравнениям (4.6) и обращающие в минимум линейную функцию (4.5).

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

Пример 2. Имеется задача линейного программирования с ограничениями-равенствами (ОЗЛП):

и минимизируемой функцией

Требуется записать ее как задачу линейного программирования с ограничениями-неравенствами.

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

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

Так как условия (4 9) могут быть заменены неравенствами:

Перейдем в выражении линейной функции L к свободным переменным Подставляя в L вместо и их выражения (4.9). получим.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ФГОУ ПО “ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И ЭКОНОМИКИ”

Предмет “Математические методы”

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

Курсовая работа

Студента группы 315-ПО

Андреева Дмитрия Александровича

Руководитель курсовой работы

Васильева Наталья Анатольевна

Псков 2009 г.

Введение

Глава Ι Линейное программирование

§ 1 Общая постановка задачи линейного программирования

§ 2 Математическая модель задачи линейного программирования

§ 3 Каноническая форма задачи линейного программирования

Глава ΙΙ Решение задачи симплексным методом

§ 1 Постановка задачи

§ 2 Составление математической модели задачи

§ 3 Алгоритмы решения задачи симплексным методом

§ 4 Построение начального опорного решения методом Гаусса

§ 5 Решение задачи

Заключение

Литература

Введение

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

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

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

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

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

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

Глава Ι Линейное программирование

§ 1 Общая постановка задачи линейного программирования

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

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

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

§ 2 Математическая модель задачи линейного программирования

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

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

Принцип составления математической модели.

1. Выбирают переменные задачи.

Переменными задачи называются величины

Которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = () Причём )

2. Составляют систему ограничения задачи.

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

В общем виде система записывается в виде

3. Задают целевую функцию.

Целевая функция – это функция Z(X) которая характеризует качество выполнения задачи, экстремум которой надо найти. В общем виде целевая функция записывается Z(X) =

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

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

и условию неотрицательности

0 (j = ), которая обеспечивает экстремум целевой функции Z(Y) =

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

Множество допустимых решений образует область допустимых решений задачи (ОДР).

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

§ 3 Каноническая форма задачи линейного программирования

Математическая модель задачи должна иметь каноническую форму.

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

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

перейти от неравенств к уравнению следующим образом: в левую часть неравенств вводим дополнительную переменную с коэффициентом (+1) для неравенства (

) и (-1) для неравенства () дополнительные переменные не наложены целевые неотрицательности, то её заменяют разностью двух неотрицательных переменных, то есть: = – (

Общий вид канонической формы:

Глава ΙΙ Решение задачи симплексным методом

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

Название метода от латинского simplecx – простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.

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

§ 1 Постановка задачи

На предприятии в процессе производства используется 3 вида станков Ι, ІΙ, ІΙІ. При этом расходуется сырьё, трудовые ресурсы, и учитываются накладные расходы.

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

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

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
если некоторая переменная x j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
x 3 = x 3 + — x 3 — , где x 3 + , x 3 — ≥ 0 .

Пример 1 . Приведение к канонической форме задачи линейного программирования:

min L = 2x 1 + x 2 — x 3 ;
2x 2 — x 3 ≤ 5;
x 1 + x 2 — x 3 ≥ -1;
2x 1 — x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Введем в каждое уравнение системы ограничений выравнивающие переменные x 4 , x 5 , x 6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x 6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x 5 вводится со знаком "-".

2x 2 — x 3 + x 4 = 5;
x 1 + x 2 — x 3 — x 5 = -1;
2x 1 — x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x 2 — x 3 + x 4 = 5;
-x 1 — x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 — x 6 = 3.

В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x 1 = x 1 ‘ — x 7 , где x 1 ‘ ≥ 0, x 7 ≥ 0 .

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

L min = 2x 1 ‘ + x 2 — x 3 — 2x 7 ;
2x 2 — x 3 + x 4 = 5;
-x 1 ‘ — x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ‘ + x 2 — x 6 + 2x 7 = 3;
x 1 ‘ ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Условие оптимальности базисного плана канонической задачи ЛП. Симплекс-метод и его сходимость.

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

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

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

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

Опорным решением называется базисное неотрицательное решение.

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

1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

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

Возможны следующие случаи при решении задач на максимум:

1. Если все коэффициенты последней строки симплекс-таблицы Dj ³ 0, то найденное

решение оптимальное.

2 Если хотя бы один коэффициент Dj £ 0, но при соответствующей переменной нет ни одного положительного оценочного отношения, то решение задачи прекращаем , так как F(X) ® ¥ , т.е.целевая функция не ограничена в области допустимых решений.

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

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

5. Если хотя бы один коэффициент Dk < 0 ,то k — тый столбец принимаем за ведущий.

6. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k – того столбца.

7. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом.

Заполняем симплексную таблицу 2:

· заполняем базисный столбец нулями и единицей

· переписываем ведущую строку, разделив ее на ведущий элемент

· если ведущая строка имеет нули, то в следующую симплекс-таблицу можно перенести соответствующие столбцы

· остальные коэффициенты находим по правилу “прямоугольника”

Получаем новое опорное решение, которое проверяем на оптимальность:

Если все коэффициенты последней строки Dj ³ 0, то найденное решение максимальное.

Если нет, то заполняем симплексную таблицу 8-го шага и так далее.

Если целевая функция F(X) требует нахождения минимального значения , то критерием оптимальности задачи является неположительность коэффициентов Dj при всех j = 1,2,…n.

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

Легко заметить, что проблемы со сходимостью симплекс-метода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения отношения

будут достигнуты для нескольких строк таблицы Т (q) одновременно. Тогда на следующей итерации столбец b(β(q+1)) будет содержать нулевые элементы.

⇐ Предыдущая12345Следующая ⇒

Дата публикования: 2015-11-01; Прочитано: 4190 | Нарушение авторского права страницы

Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.002 с)…

Оптимальное решение — задача — линейное программирование

Cтраница 1

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

Используя оптимальное решение задачи линейного программирования, можно найти допустимые изменения ДС, при которых еще L остается постоянным.

Если существует оптимальное решение задачи линейного программирования, то существует базисное оптимальное решение.

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

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

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

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

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

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

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

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

Страницы: 1 2

Графический метод решения задачи линейного программирования

Рассмотрим ЗЛП в стандартной форме для случая двух переменных :

(10)

Пусть система неравенств (10) совместна (имеет хотя бы одно решение). Любое неравенство этой системы геометрически определяет полуплоскость с граничной прямой Условия не отрицательности определяют полуплоскости с соответственными граничными прямыми и .

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

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

Рассмотрим так называемую линию уровня целевой функции z , то есть линию, вдоль которой эта функция принимает одно и то же фиксированное значение : или

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

1. Строится многоугольная область допустимых решений на плоскости соответствующая ограничениям. Затем строится вектор-градиент

целевой функции z в любой точке область допустимых решений.

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

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

Формулировка основных типов задач ЛП, построение их математических моделей

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

Пример. Решить геометрически задачу:

Построим многоугольник всех допустимых решений OABCD и направляющий вектор целевой функции (Рис. 1). Направление вектора-градиента указывает направление возрастания целевой функции. Так как рассматриваемая задача на отыскание максимума, то прямую, перпендикулярную вектору перемещаем в направлении этого вектора параллельно самой себе до тех пор, пока эта прямая не покинет область допустимых решений. На границе области, в нашем случае в точке С , и будет решение задачи. Точка С находится на пересечении прямых и . Следовательно, ее координаты определяются решением системы этих уравнений уравнении:

откуда т.е. точка С имеет координаты (6, 4).

Максимум (максимальное значение целевой функции) равен: Ответ: при оптимальном решении т.е. максимальна прибыль может быть достигнута при производстве 6 единиц первой и 4 единиц второй продукции.

ВВЕДЕНИЕ

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

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

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

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

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

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

где и – заданные функции, а – некоторые действительные числа.

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

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

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

Задача линейного программирования (стр. 1 из 3)

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

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

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

Рассмотрим некоторые задачи линейного программирования (ЗЛП).

1. Задача об использовании ресурсов (задача планирования производства).

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

сырья каждого вида, которое может быть использовано предприятием, приведены в табл.

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

Построим математическую модель данной задачи.

Обозначим через искомый выпуск изделий , через – изделий ,

через – изделий .

Так как на сырье каждого вида имеются нормы затрат, тогда мы можем найти общий объем затрат сырья каждого вида для изготовления всех изделий. Из таблицы следует, что общий объем сырья I вида составит , II –
,

III –
. А так как на фонд сырья имеются ограничения, следовательно общий объем сырья каждого вида должен быть не больше общего количества сырья, т.е.

получим следующую систему неравенств

(1)

По экономическому смыслу переменные могут принимать только неотрицательные значения:

(2)

Стоимость всех изделий вида составит – – Соответственно общая стоимость произведенной предприятием продукции составит (3)

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

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

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

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

дополнительной системе ограничений

при котором целевая функция –

принимает максимальное значение.

Замечание. Чтобы составить математическую модель ЗЛП необходимо:

– ввести обозначения переменных;

– исходя из цели экономических исследований, составить целевую функцию;

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

Решение задач линейного программирования основываются на понятиях аналитической геометрии в – мерном векторном пространстве.

Приведение общей ЗЛП к каноническому виду.

Общий вид ЗЛП следующий:

(1)

(2)

(3)

где соотношение (1) – целевая функция, (2) – система основных ограничений, (3) – система дополнительных ограничений.

Соотношения (2) и (3) образуют полную систему ограничений.

Приведение системы основных ограничений к каноническому виду осуществляется введением в левые части неравенств дополнительных неотрицательных переменных с коэффициентами «+1», если неравенства вида и «-1», если неравенства вида . В целевую функцию дополнительные переменные входят с нулевыми коэффициентами.

Определение . ЗЛП называется заданной в каноническом виде, если ее система основных ограничений представлена уравнениями.

Определение. ЗЛП называется заданной в стандартной форме канонического вида, если выполняются следующие условия:

1) система основных ограничений представлена уравнениями и все они линейно независимы;

2) число уравнений меньше числа переменных;

3) решается задача минимизации целевой функции;

4) правые части системы основных ограничений неотрицательны;

5) все переменные также неотрицательны.

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

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство

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

При этом данная величина является неотрицательной.

Пример

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

Решение:

Перейдем к задаче на отыскивание максимума целевой функции.

Для этого изменим знаки коэффициентов целевой функции.

Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x 4 x 5 (на математической модели эта операция отмечена буквой Д).

Переменная х 4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".

Переменная x 5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".

В целевую функцию переменные x 4 x 5 вводятся с коэффициентом. равным нулю.

Записываем задачу в каноническом виде:

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

1. Привести задачу к каноническому виду

Тема 8. Линейное программирование

Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

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

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

Пример решения задачи симплексным методом

Пример 1

Решить симплексным методом задачу:

Минимизировать значение функции

F = 10×1 — 4×3 max

При наличии ограничений в виде неравенств

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 5 с коэффициентом +1. В целевую функцию переменная x 5 входит с коэффицентом ноль (т.е. не входит).

Получаем:

F = 10×1 — 4×3+0∙x5 max

При наличии ограничений в виде неравенств

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,5,9/15,6) с единичным базисом Б1 = (А4, А5, А6).

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

Δ k = C б X k - c k

· C б = (с 1 , с 2 , … , с m) - вектор коэффициентов целевой функции при базисных переменных

· X k = (x 1k , x 2k , … , x mk) - вектор разложения соответствующего вектора А к по базису опорного решения

· С к - коэффициент целевой функции при переменной х к.

Оценки векторов входящих в базис всегда равны нулю.

Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу:

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

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

Приращение целевой функции находится по формуле:

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора

ΔZ 1 = - 6*(- 2) = 12,

и третьего вектора ΔZ 3 = - 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение

Х2 = (0,0,3,21,42,0)

с базисом Б2 = (А3, А4, А5).

(таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = - 6.

Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2.

Следовательно, из базиса выводим второй вектор базиса А4.

Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение

Х3 = (0,7,10,0,63,0)

Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ : max Z(X) = 201 при Х = (0,7,10,0,63).

⇐ Предыдущая123456789Следующая ⇒

3.1. Общая задача линейного программирования

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

Линейное программирование включает в себя целый ряд эвристических (приближенных) методов решения, позволяющих при заданных условиях из всех возможных вариантов решений производственных задач выбрать наилучший, оптимальный. К этим методам относятся следующие – графический, симплексный, метод потенциалов (модифицированный распределительный метод – МОДИ), Хичкова, Креко, метод аппроксимации Фогеля и другие.

Часть этих методов объединяют общим названием - распределительный, или транспортный, метод.

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

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

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

Целевая функция и ограничения выражены линейными зависимостями (равенствами или неравенствами);

Число зависимостей всегда меньше числа неизвестных (условие неопределенности);

Неотрицательность искомых переменных. Общая форма записи модели линейного программирования в сокращенном виде выглядит следующим образом:

Найти х ij ≥ 0 (j = 1, 2…n) при ограничениях следующего типа:

Эти ограничения минимизируют (или максимизируют) целевую функцию

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

а 11 х 1 + а 12 х 2 + …+ а 1 n х n = b 1 ;

а 21 х 1 + а 22 х 2 + … + а 2 n х n = b 2 ; (3.1)

……………………………..

a m х 1 + а m 2 х 2 + …+ а mn х n = b m ..

Если модель записана в форме неравенств в неотрицательных числах, т. е. имеет вид

а 11 х 1 + а 12 х 2 + …+ а 1 n х n ≤ b 1 ;

а 21 х 1 + а 22 х 2 + … + а 2 n х n ≤ b 2 ; (3.2)

……………………………..

a m х 1 + а m 2 х 2 + …+ а mn х n ≤ b m ,..

то эта запись приводится к канонической форме (3.1) путем введения дополнительных переменных х n +1 > 0 (i =1,2…m ) в левую часть неравенства (или сокращения числа переменных, если знак неравенства направлен в другую сторону). Дополнительные переменные составляют базис.

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

L = с 1 х 1 + с 2 х 2 …с n х n → min, (3.3)

где с 1 , с 2 … с n – коэффициенты целевой функции L при переменных х j .

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

В случае максимизации целевой функции L следует знаки при переменных целевой функции изменить на противоположные, и мы вновь придем к задаче минимизации, т.е. одна задача сводится к другой заменой L на –L или max L = min (–L ).

Базисным решением системы линейных уравнений (3.1) называется решение, в котором небазисным переменным даны нулевые значения.

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

Оптимальным называется допустимое решение, максимизирующее (или минимизирующее) целевую функцию (3.3).

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

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

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

3.2. Графоаналитический метод

Графоаналитический метод – это один из простейших методов линейного программирования. Он наглядно раскрывает сущность линейного программирования, его геометрическую интерпретацию. Его недостаток в том, что он позволяет решать задачи с 2 или 3 неизвестными, т. е. применим для узкого круга задач. Метод основан на правилах аналитической геометрии.

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

Метод решения рассмотрим на конкретном примере.

Пример 3.1. На складе имеются 300 т изделий из пенобетона и 200 т из стали. Автопредприятию необходимо доставить эти изделия на строящийся объект. На автопредприятии имеются грузовые автомобили КамАЗ - 5320 и

ЗИЛ-4314. За одну поездку КамАЗ-5320 может доставить 6 т пенобетона и 2 т стали, а прибыль от ездки составит 4 тыс. руб. ЗИЛ-4314 за одну поездку доставляет 2 т пенобетона и 4 т стали, прибыль от ездки составляет 6 тыс. руб. Необходимо организовать перевозку так, чтобы обеспечить автопредприятию наибольшую прибыль.

Построим математическую модель задачи. Обозначим через х 1 искомое количество ездок КамАЗ-5320 и через х 2 искомое количество ездок ЗИЛ-4314.

Общая перевозка в т изделий из пенобетона составляет 6х 1 + 2х 2 , а из стали 2х 1 + 4х 2 . Ограничения по перевозке, исходя из имеющегося количества изделий, составляют 6х 1 + 2х 2 ≤ 300т по пенобетону и 2х 1 + 4 х 2 ≤ 200т по стали.

Суммарная прибыль в тыс. руб. выражается величиной 4х 1 + 6х 2 , которую нужно максимизировать и которая является критерием оптимальности в рассматриваемой задаче. Математическая модель задачи, таким образом, выглядит следующей. Необходимо максимизировать целевую функцию

L = 4х 1 + 6х 2 → mах при условиях: 6х 1 + 2х 2 ≤ 300; 2х 1 + 4х 2 ≤ 200; х 1 ≥ 0; х 2 ≥ 0.

Рассмотрим уравнение 6х 1 + 2х 2 = 300. Чтобы построить прямую, описываемую этим уравнением, найдем две точки, лежащие на этой прямой. При х 1 = 0 из уравнения прямой найдем 2х 2 = 300, откуда х 2 = 150. Следовательно, точка А с координатами (0,150) лежит на искомой прямой. При х 2 = 0 имеем 6х 1 = 300, откуда х 1 = 50, а точка D с координатами (50,0) также находится на искомой прямой. Через эти две точки проводим прямую AD (рис. 3.1).

Линейное неравенство 6х 1 + 2х 2 ≤ 300 представляет собой полуплоскость, расположенную с одной из сторон от построенной прямой 6х 1 + 2х 2 = 300. Чтобы выяснить, с какой стороны от этой прямой расположены точки искомой полуплоскости, подставим в неравенство 6х 1 + 2х 2 ≤ 300 координаты какой-либо точки, не лежащей на граничной прямой. Например, начало координат 0-(0,0). Для него справедливо неравенство 6∙0 + 2∙0 = 0 < 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD и на рис. 3.1 заштрихована.

Уравнение 2х 1 + 4х 2 = 200 построим по двум точкам. При х 1 = 0 4х 2 = 200, откуда х 2 = 50. Тогда точка Е имеет координаты (0,50) и принадлежит искомой прямой. При х 2 = 0, 2х 2 = 200, точка с находится на данной прямой с координатами (100,0). Подставив в неравенство координаты точки с (0,0), получим 2∙0 + 4∙0 = 0 < 200. Значит, начало координат находится в области допустимых значений от прямой 2х 1 + 4х 2 = 200.

Система ограничений задачи требует, чтобы планы (х 1 ; х 2 ) удовлетворяли всем четырем неравенствам, т. е. допустимые планы – точки (х 1 ; х 2 ) должны одновременно находиться во всех четырех полуплоскостях. Этому требованию отвечают только точки, расположенные внутри и на границе многоугольника OEKD , который и является многоугольником допустимых решений.

Вершинами многоугольника допустимых решений являются точки O, E, K, D, отрезки прямых OE, EK, KD, OD – его ребра. Любая точка многоугольника OEKD является планом задачи, удовлетворяя все ее условия. Вершины многоугольника образованы пересечением двух прямых и соответствуют опорным планам задачи, среди которых находится и наилучший (оптимальный) план. Таким образом, опорных планов будет столько, сколько вершин у многоугольника допустимых решений.

Наглядное геометрическое представление можно получить и для целевой функции L = 4х 1 + 6х 2 . Зафиксируем какое-либо значение целевой функции, например L = 120. уравнение 4х 1 + 6х 2 = 120 определяет прямую, проходящую через точку В с координатами (х 1 = 0; х 2 = 20) и точку L с координатами ((х 1 = 30; х 2 = 0). Отрезок ВL лежит внутри многоугольника OEKD . Следовательно, для всех планов (точек) этого отрезка значение целевой функции одинаково и равно 120. Придавая другие значения целевой функции, получим параллельные прямые, которые называют линиями уровня целевой функции.

Перемещая прямую L параллельно самой себе в одном направлении, получим возрастание целевой функции, а в противоположном направлении – ее убывание. В рассматриваемом примере передвижение прямой ВL вправо определяет возрастание целевой функции, которую мы максимизируем. Так поступаем до тех пор, пока прямая ВL будет иметь хотя бы одну общую точку с многоугольником допустимых решений OEKD . Из рис. 3.1 следует, что последней точкой, которую пересечет прямая уровня целевой функции, будет точка К . Это значит, что точка К определяет оптимальный план задачи.

Направление возрастания, перпендикулярное к линии уровня, называется направлением наибольшего возрастания целевой функции и определяет ее максимальный прирост. Это направление можно установить без построения линий уровня. Для этого необходимо на осях х 1 и х 2 отложить отрезки, равные коэффициентам целевой функции, и по ним, как по координатам, построить вектор наибольшего возрастания целевой функции. В математике его называют градиентом и обозначают знаком grad. Градиентом для функции L = 4х 1 + 6х 2 будет вектор n | 4; 6 | . Для удобства его построения увеличим координаты, например, в 10 раз, т.е. n | 40; 60 | . Построим градиент целевой функции L , для чего соединим точку с координатами (40; 60) с началом координат. Линии уровня целевой функции строят перпендикулярно к направлению градиента.

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

6х 1 + 2х 2 = 300;

2х 1 + 4х 2 = 200.

Уравняем коэффициенты при х 1 , умножив второе уравнение на 3, и вычтем из второго уравнения первое. Получим 10х 2 = 300, х 2 = 30. Подставив значение х 2 = 30 в любое из уравнений, например в первое, определим значение х 1:

6х 1 + 2х · 30 = 300,

откуда 6х 1 = 300 – 60 = 240, следовательно, х 1 = 40.

Таким образом, чтобы получить наибольшую прибыль автопредприятию, необходимо выполнить 40 ездок на КамАЗ-5320 и 30 ездок на ЗИЛ-4314. Максимальная прибыль при этом составит

L = 4х 1 + 6х 2 = 4 · 40 + 6 · 30 = 340 тыс. руб.

На основе рассмотренного примера и геометрической интерпретации задачи оптимизации с двумя переменными можно сделать следующие выводы:

1) в двухмерном пространстве область допустимых решений представляет собой многоугольник;

2) каждой стороне многоугольника соответствует значение одной переменной, равной нулю;

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

4) каждому значению целевой функции соответствует прямая;

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

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

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

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

На рис. 3.2,б изображены невыпуклые множества. В невыпуклых множествах можно указать хотя бы две точки отрезка АВ, не принадлежащие рассматриваемому множеству.

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

Симплексный метод – это распространенный метод решения задач линейного программирования. Свое название метод получил от слова «симплекс», обозначающего простейший выпуклый многоугольник, число вершин которого всегда на единицу больше, чем размерность пространства. Симплексный метод разработан в США математиком Дж. Данцигом в конце 1940-х годов.

Симплексный метод включает получение неотрицательного базисного решения системы канонических линейных уравнений типа (3.1), последующую минимизацию (максимизацию) целевой функции (3.3) и нахождение таким способом оптимальных значений искомых переменных х 1 , х 2… х n .

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

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

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

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

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

Пусть необходимо минимизировать линейную форму

L = с 1 х 1 + с 2 х 2 + … с n х n .

При условиях (для наглядности нулевые и единичные коэффициенты в уравнениях сохранены):

1х 1 + 0х 2 + … 0х m + a 1m+ 1x m+1 …+a 1n x n = b 1 ;

0х 1 + 1х 2 + … 0х m + a 2m+ 1x m+1 …+a 2n x n = b 2 ;

……………………………………………

0х 1 + 0х 2 + … 1х m + a mm + 1x m +1 …+a mn x n = b m .

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

Решим уравнения относительно базисных переменных:

х 1 = b 1 – (a 1m+1 ·х m+1 …+ a 1n x n);

х 2 = b 2 – (a 2m+1 ·х m+1 …+ a 2n x n);

………………………………

х m = b m – (a mm+ 1x m+1 …+ a mn x n),

а целевую функцию выразим через свободные переменные, подставив в нее на место базисных переменных их выражения через свободные переменные:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Переменные х 1 , х 2 …, х m , с помощью которых найден первый базисный план, являются базисными, а остальные x m +1 , x m +2 ,…x n – свободными. Базисных переменных должно быть всегда столько, сколько уравнений в системе. Исходя из условия неотрицательности, наименьшее значение свободных переменных равно нулю. Полученное базисное решение системы уравнений и является ее первоначальным допустимым решением, т.е. x 1 = b 1 , x 2 =b 2 , … x m =b m , x m +1 = 0,…, x n = 0.

Этому решению соответствует значение целевой функции

L = с 1 b 1 + с 2 b 2 + … с m b m .

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

Симплексные таблицы составляют следующим образом (см. табл. 3.1). Вверху таблицы помещают все переменные х 1 , х 2 …, х n и коэффициенты c j , с которыми соответствующие переменные входят в целевую функцию. Первый столбец c i состоит из коэффициента целевой функции при переменных, вошедших в базис. Затем следует столбец базисных переменных и свободных членов уравнений. Элементы остальных столбцов таблицы представляют собой коэффициенты при переменных, с которыми последние входят в систему уравнений. Таким образом, каждой строке таблицы соответствует уравнение системы, решенное относительно базисной переменной. В таблице показан и вариант плана, который соответствует целевой функции при данном базисе.

Нижняя строка таблицы называется индексной . Каждый ее элемент (оценка) ∆ j определяют

∆ j = z j – c j ,

где c j – коэффициенты при соответствующих переменных в целевой функции; z j – сумма произведений коэффициентов целевой функции при базисных переменных на соответствующие переменные – элементы j –го столбца таблицы.

Таблица 3.1

Симплексная таблица с первоначальным допустимым