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

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

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

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

4. Шаг 2. Проверка на неразрешимость

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

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

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

k − строка, для которой это отношение минимально − ведущая. Элемент ak,l − ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис. Пересчитываем симплекс − таблицу по формулам . Если в новой таблице после перерасчета в строке F остались отрицательные элементы, то переходим к шагу 2.

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

Если в строке F и в столбце свободных членов все элементы положи-тельные, то найдено оптимальное решение.3

Правила преобразования симплекс-таблицы:

При составлении новой симплекс-таблицы в ней происходят следующие изменения (1): 

• вместо базисной переменной xk записываем xl;

• вместо небазисной пе-ременной xl записываем xk; 

• ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l ;

• все элементы ведущего столбца (кроме ak,l) умножаются на −1/ak,l ;

• все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l ;  
• оставшиеся элементы симплекс-таблицы преобразуются по формуле

                                                                                 (2) 

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого

базисного решения задачи;                 

2)  правило перехода к лучшему (точнее, не худшему) решению;

3)  критерий проверки оптимальности найденного решения.

Геометрический (графический) метод

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

Рис. 1.1. Система ограничений на плоскости

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис.1.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или минимальное) значение.

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

                                             c1x1+c2x2 = а                                                     (3)

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

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

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

Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а.

Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c1 и c2 и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели”, расположенные обычно под углом к осям координат.

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

Пусть имеются три линии уровня :

F=c1x1 + c2x2 = а1 (I)

F=c1x1 + c2x2 = а2 (II)

F=c1x1 + c2x2 = а3 (III)

Причём линия II заключена между линиями I и III. Тогда а1 < а2 < а3 и а1 > а2 > а3.

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

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c1x1 + c2x2, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1.1 – это точка С или А).

 

 

 

 

2. Разработка  модели и решение  задачи линейного программирования на примере задачи «производить» или определения оптимального плана производства

 

2.1. Вербальная постановка конкретной решаемой задачи «производить или покупать»

Фабрика ООО «Мельник» специализируется на выпуске двух сортов теста: бисквитное и песочное. Для изготовления теста используются такие ингредиенты как яйца и сахар, так же затрачивается и ресурсы труда. Для изготовления бисквитного теста требуется 5 штук яиц и 0,3 килограмма сахара, для изготовления затрачивается 15 минут. А для изготовления песочного теста потребуется 2 яйца, 0,25 килограмма сахара и 30 минут затраченного времени. Стоимость 1 кг бисквитного теста 30 руб., а песочного 20 руб. Общий запас яиц равен 1000 шт., 75 кг сахара и 125 часов трудовых ресурсов.

2.2. Разработка экономико-математической модели решаемой задачи

1. Переменные задачи.

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

х1 – суточный объем производства бисквитного теста, (кг);

х2 – суточный объем производства песочного теста, (кг).

2. Целевая функция.

В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции, т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи продукции обоих видов, необходимо знать объемы производства, т.е. x1 и х2 кг продукции в сутки, а также цены на продукцию бисквитного и песочного теста – согласно условию 30 и 20 руб. за 1 кг продукции соответственно. Таким образом, доход от продажи суточного объема производства продукции бисквитного теста равен 30х1 руб. в сутки, а от продажи песочного теста – 20х2 тыс. руб. в сутки. Поэтому запишем целевую функцию в виде суммы дохода от продажи продукции бисквитного и песочного теста.

 

(руб.).

3. Ограничения.

Возможные объемы производства продукции х1 и х2 ограничиваются следующими условиями:

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

– объем производства продукции не может быть выражен отрицательными значениями.

Запишем эти ограничения в математической форме.

Ограничение по расходу яиц имеет вид:

 

(т/сутки).

Левая часть ограничения – это расчет расхода яиц на производство теста обоих видов. Расход яиц на производство 1 кг бисквитного теста – 5 шт.; на производство 1 кг песочного теста – 2 шт. Тогда на производство х1 кг бисквитного теста и х2 кг песочного теста потребуется (5х1 + 2x2) шт. яиц. Правая часть ограничения – это величина запаса яиц на складе – 1000 шт.

Аналогична запись ограничения по расходу сахара:

 

(кг).

 

Так же ограничение по трудовым ресурсам имеет вид:

 

(чел.-ч.)

 

Неотрицательность объемов производства задается как

Таким образом, математическая модель задачи имеет вид:

 

;

 

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

 

2.3. Решение поставленной задачи

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

 

В качестве базисных переменных возьмем х3, х4, х5, тогда небазисные – х1, х2. Полагаем х1 = х2 = 0, тогда х3 =1000, х4=75, х5 =125.

I этап.

х3, х4, х5 – основные переменные;

х1, х2 - неосновные

или

 

Допустимое решение. Все переменные неотрицательные.

II этап

1.

а)

б) решение допустимо:

в) - решение неоптимальное, т.к. х1 и х2 положительные, значит можно увеличить

г) т.к. при х1 коэффициент больше, переводим ее в основные переменные, х3 переводим в неосновные

х1 max возможное =

таким образом, х1 = 200, х3= 0

Разрешающим будет 1-е уравнение, х3 = 0, х1 переводим в основные переменные

д) Новый состав переменных:

х1, х4, х5 – основные переменные;

х3, х2 – неосновные

2.

а)

б)

в)

Решение не оптимально. Его можно увеличить путем перевода х2 в основные переменные.

г) х2 переводим в основные переменные, х4 выводим в неосновные.

д) базисные переменные: х1 , х2 , х5

    неосновные переменные: х3 , х4

3.

а)

б)

 

в) =

= =6922 - 2,32х3

Так как все оценки свободных переменных положительные, найденное решение является оптимальным:

Максимальная прибыль составит 6922 рубля, при этом необходимо произвести 153,8 кг бисквитного теста и 115,4 кг песочного теста. В оптимальном плане ресурсы яиц и сахара равны нулю (х3=х4=0), так как они используются полностью. А резерв трудовых ресурсов х5 = 28,8, что свидетельствует о излишках.