Вопрос №1 Общая характеристика симплексного метода. Запись задачи линейного программирования для решения симплексным методом.





Тема №4 «Симплексный метод линейного программирования»

Вопросы:

1. Общая характеристика симплексного метода. Запись задачи линейного программирования для решения симплексным методом;

Заполнение первой симплексной таблицы.

3. Определение оптимальности плана. Алгоритм построения новой симплексной таблицы.

4. Пример перехода к новой симплексной таблице.

Вопрос №1 Общая характеристика симплексного метода. Запись задачи линейного программирования для решения симплексным методом.

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

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

1) приведение задачи к канонической форме и нахождение первоначального варианта допустимого плана;

2) проверка найденного варианта плана на оптимальность (если полученный вариант окажется оптимальным, то решение получено, в противном случае план должен быть улучшен);

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

Рассмотрим пример записи экономической задачи.

Пример.Коммерческое предприятие, располагающее матери­ально-денежными ресурсами, реализует три группы товаров А, В и С. Плановые нормативы затрат ресурсов на 1 тыс. руб. товарообо­рота, доход от продажи товаров на 1 тыс. руб. товарооборота, а также объем ресурсов заданы в таблице 1.

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

Таблица 1 – Исходные данные для решения задачи

Виды материально-денежных ресурсов Норма затрат материально-денежных ресурсов на 1 тыс. руб. товарооборота   Объем ресурсов
А (х1)   В(х2)     С(х3)    
Рабочее время продав­цов, чел.-час.   0,1   0,2   0,4    
Площадь торговых за­лов, м2   0,05   0,02   0,02    
Площадь складских помещений, м          
Доход, тыс. руб.         максимум  

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

0,1х1 + 0,2х2 + 0,4х3 ≤ 1100 – по рабочему времени продавцов, чел.-час.

0,05 х1 +0,02 х2 + 0,02 х3≤ 120 – по площади торговых залов, м2

3 х 12 + 2 х3 ≤ 8000 - по площади складских помещений

XI ≥0, X2 ≥0, X3 ≥0 – условие неотрицательности переменных

и обеспечивающих максимальное значение целевой функции

Z = 3х 1+5х 2+4х 3 ->max

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

Для построения первого опорного плана систему неравенств приведем к канонической форме путем введения дополнительных (базисных) переменных х 1, х 2, х 3. В том случае, если неравенство имеет знак ≤, базисная переменная добавляется в неравенство со знаком «+», если знак неравенства ≥, базисная переменная добавляется со знаком «-». В нашем примере все неравенства со знаком ≤, следовательно, базисные переменные х4, х5 и х6 добавляются со знаком «+»:

0,1х1+0,2х2+0,4хз4 = 1100

0,05х1+0,02х2+0,02х35 = 120

12+2х +х6= 8000

XI ≥0, X2 ≥0, X3 ≥0, X4 ≥0, X5 ≥0, X6 ≥0

Z = 3 х 1+ 5х 2 + 4х 3 + 0х 4 + 0х 5 + 0х 6 ->max

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

Вопрос №2 Заполнение первой симплексной таблицы.

1. В первом столбце перечисляют базисные переменные.

2. Во второй столбец записывают оценки базисных переменных, указанные в целевой функции.

3. В третьем столбце указывают свободные члены.

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

5. Над рабочей частью таблицы перечисляют свободные переменные.

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

7. Оценки Z – строки рассчитывают по формуле:

где j=1, 2,…,n

aij – коэффициенты j –ого столбца,

Ci - коэффициенты при базисных переменных в уравнении Z,

Cj - коэффициенты при свободных переменных в уравнении Z.

 

 

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

0,1 х1+0,2х2+0,4хз4 = 1100

0,05х1+0,02х2+0,02х35 = 120

1+1*х2+2х36= 8000

XI ≥0, X2 ≥0, X3 ≥0, X4 ≥0, X5 ≥0, X6 ≥0

Z = 3 х 1+ 5х 2 + 4х 3 + 0х 4 + 0х 5 + 0х 6 ->max

Таблица 2 – Заполнение первой симплексной таблицы (опорного плана)

Базисные переменные Cj
Ci ai0 X1 X2 X3
X4 0,1 (0,2) 0,4
X5 0,05 0,02 0,02
X6
Z   -3 -5 -4

 

  Базисные переменные
  Коэффициенты при базисных переменных в целевой функции
  Свободные члены уравнения
Свободный член целевой функции (число без переменной, заносится с противоположным знаком) – если отсутствует – принимается равным 0
  Свободные переменные
  Коэффициенты перед свободными переменными в целевой функции (оценки свободных переменных)
Коэффициенты при соответствующих переменных в системе уравнений
Коэффициент z-строки = 0*1100+0*120+0*8000-0
-3 Коэффициент z-строки = 0*0,1+0*0,05+0*3-3
-5 Коэффициент z-строки = 0*0,2+0*0,02+0*1-5
-4 Коэффициент z-строки = 0*0,4+0*0,02+0*2-4

 

Вопрос №3 Определение оптимальности плана. Алгоритм построения новой симплексной таблицы

В симплексных таблицах формальным признаком оптимальности является содержание оценочной строки (Z-строки).

Ключевая теорема симплексного метода (Z на максимум): Если после выполнения очередной итерации: 1) найдется хотя бы одна отрицательная оценка, а в столбце, где она стоит, есть хотя бы один положительный элемент, то опорное решение можно улучшить, выполнив следующую итерацию; 2) найдется хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, то функция Z неограниченна в области допустимых решений (Zmax ®+¥); 3) все оценки окажутся неотрицательными, то достигнуто оптимальное решение.

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

1. Просматриваются оценки Z - строки. Если они все неотрицательны, то получено оптимальное решение при решении на максимум целевой функции, если все оценки £ 0, то получено оптимальное решении при решении на минимум целевой функции.

2. Если оптимальное решение не получено, то выбирается разрешающий столбец по наибольшей по абсолютной величине отрицательной оценке Z - строки при решении на максимум и по наибольшей положительной оценке при решении на минимум целевой функции.

3. Составляются симплексные отношения - отношения свободных членов к положительным коэффициентам разрешающего столбца. Минимальное из этих отношений ( min íai 0/ aipý) определит разрешающую строку. Коэффициент, находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.

Если в разрешающем столбце нет ни одного положительного коэффициента, то задача не имеет решения по причине неограниченности целевой функции (Zmax®+¥ ,Zmin®-¥ ).

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

5. Бывший разрешающий элемент заменяется обратным по величине (1/ аqp).

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

Если в бывшем разрешающем столбце в какой-то строке стоял “0”, то эта строка переносится в следующую таблицу без изменений.

7. Все остальные элементы бывшей разрешающей строки делятся на разрешающий элемент.

Если в бывшей разрешающей строке в каком-то столбце стоял “0”, то этот столбец переносится в следующую таблицу без изменений.

8. Остальные элементы таблицы пересчитываются по правилу “прямоугольника”:

9. Осуществляется контроль за правильностью расчетов для элементов Z-строки.

10. Если ошибок нет, то алгоритм повторяется с пункта 1.

Вопрос №4 Пример перехода к новой симплексной таблице.

Таблица 3 – Симплексная таблица (исходное опорное решение)

Базисные переменные Cj Симплексные отношения
Ci ai0 X1 X2 X3
X4 0,1 (0,2) 0,4 5500←
X5 0,05 0,02 0,02 6000
X6 8000
Z   0 -3 -5↑ -4  

Исходное опорное решение записывается по столбцу свободных членов. Та как свободным переменным в указанном столбце не соответствуют свободные члены, то Х1=0, Х2=0, Х3=0. Базисным переменным соответствуют определенные свободные члены Х4=1100, Х5=120, Х6=8000. Следовательно, опорное решение записывается так Хоп.(0,0,0,1100,120,8000). Zmax=0.

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

Для перехода к следующей таблице выбираем разрешающий столбец (при решении на максимум по наибольшей по модулю отрицательной оценке (-5)). Далее считаем симплексные отношения: 1100/0,2 = 5500, 120/0,02 = 6000, 8000/1=8000.

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

Таблица 4 – Вторая симплексная таблица

Б.П. Cj ai0/aip
Ci ai0 X1 X4 X3
X2 5500* 0,5* 5* 2*
X5 10* (0,04)* -0,1* -0,02* 250<
X6 2500* 2,5* -5* 0*
Z   27500* -0,5*­ 25* 6 *  

Во второй симплексной таблице свободная переменная разрешающего столбца (Х2) переходит на место базисной переменной разрешающей строки (Х4), а Х4 – на место Х2. далее в разрешающем столбце на месте бывшего разрешающего элемента записываем обратную величину: 1/(0,2)= 5*. Все остальные элементы бывшего разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком: 0,02/ (0,2) * (-1) = -0,1*, 0,1/(0,02) * (-1) = -5*, 5/(0,02)*(-1) = 25*. Для нахождения остальных элементов разрешающей строки необходимо коэффициенты бывшей разрешающей строки разделить на разрешающий элемент: 5500*=1100/(0,2), 0,5*=0,1/(0,2) и т.д.

Все остальные элементы таблицы находятся по правилу прямоугольника по следующей схеме: бывший коэффициент – (коэффициент разрешающей строки * коэффициент разрешающего столбца)/разрешающий элемент. На пример:

- 0,02*=0,02 – (0,02*0,4)/(0,2), 6*=-4-(-5*0,4)/(0,2)и т.д.

Оценки Z-строки в таблице 4 указывают на неоптимальность плана, так как имеется отрицательный элемент. Он единственный, поэтому в качестве разрешающего столбца выбирается столбец с отрицательным элементом. Далее весь алгоритм повторяется снова. В результате получаем следующую сиплексную таблицу (таблица 5).

 

Таблица 5 – Последняя симплексная таблица

Б.П. Cj ai0/aip
Ci ai0 X5 X4 X3
X2 12,5 6,25 2,25  
X1 -2,5 -0,5  
X6 -62,5 1,25 1,25  
Z   12,5 23,75 5,75  

 

Оптимальный план можно записать так: Х1=250, Х2=5375, Х3=0, Х4=0, Х5=0, Х6=1875 или Хопт.(250, 5375, 0, 0, 0, 1875) ; Zmax=27 625 тыс.руб.

Следовательно, необходимо продавать товаров первой группыХ1= 250 ед., а второй группы Х2= 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27 625 тыс. руб. То­вары группы С не реализуются.

В оптимальном плане среди базисных переменных находится дополнительная переменная Х6. Это указывает на то, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м2, так как переменная Х6 была введена в третье ограниче­ние задачи, характеризующее собой использование складских по­мещений этого ресурса.

 

 





Читайте также:
Восстановление элементов благоустройства после завершения земляных работ: Края асфальтового покрытия перед его восстановлением должны...
Развитие понятия о числе: В программе математики школьного курса теория чисел вводится на примерах...
Группы красителей для волос: В индустрии красоты колористами все красители для волос принято разделять на четыре группы...
ТЕМА: Оборудование профилактического кабинета: При создании кабинетов профилактики в организованных...

Рекомендуемые страницы:


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

©2015-2019 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-11-19 Нарушение авторских прав и Нарушение персональных данных


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

Обратная связь
0.018 с.