Студопедия — Симплекс-метод решения задач линейного программирования
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






 

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

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

Коммерческое предприятие реализует “n” товарных групп, располагая “m” ограниченными материально-денежными ресурсами вi 0 (i = 1, 2, …..m). Известны расходы ресурсов каждого i –го вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А=(а ij), и прибыль “C j ”, получаемая предприятием от реализации единицы товара “j” группы. Надо определить объем и структуру товарооборота “хj” (j = 1, 2, …,n), при которых прибыль коммерческого предприятия была бы максимальной.

Математическую модель задачи запишем следующим образом. Определить вектор Х =(х1, х2, …хn), который удовлетворяет ограничениям вида:

 

a ij * хj вi, i = 1,2 …m (1)

хj 0, j = 1,2 …..n (2)

 

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

f(х) = Сj * Хj mах (3)

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

 


 

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

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

Переменные:

х1 – количество товаров группы А, ед.

х2 – количество товаров группы В, ед.

х3 – количество товаров группы С, ед.

Ограничения:

1) По использованию рабочего времени продавцов, чел-ч. 0,1х1+0,2х2+0,4х3 1100

2) По использованию площадей торговых залов, м2 0,05х1+0,02х2+0,02х3 120

3) По использованию площадей складских помещений, м2 12+2х3 8000

4) Условие не отрицательности переменных х1 0, х2 0, х3 0.

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

Максимальное значение целевой функции, тыс. руб.

f(х) = 3х1+5х2+4х3 mах

 

Алгоритм симплексного метода включает следующие этапы:

1.Составление первого опорного плана

 

Система ограничений задачи, решаемой симплексным методом задана в виде неравенств смысла “ ”, правые части которых вi 0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных х4; х5; х6; которые образуют базис и называются базисными переменными и определяют объемы неиспользованных ресурсов:

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

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

12+2х36 = 8000

 

Матрица коэффициентов А=(а ij) этой системы уравнений имеет вид:

А =
0,1

0,2 0,4      
0,05 0,02 0,02      
           

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

х4 = 1100 – (0,1х1+0,2х2+0,4х3)

х5 = 120 – (0,05х1+0,02х2+0,02х3)

х6 = 8000 – (3х12+3х3)

Функцию цели запишем в виде уравнения f(х) = 0 – (-3х1 – 5х2 – 4х3). Полагая что основные переменные х1=0 х2=0 х3=0, получим первый опорный план, х4= в 1; х5= в 2; х6= в 3 f(x) =0; который заносим в симплексную таблицу № 1. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком:

План Базисные переменные Свободные члены Основн. перемен. Допол.перем. i
х1 х2 х3 х6 х5 х6
I х4   0,1 0,2 0,4        
х5   0,05 0,02 0,02        
х6                
Индексная строка f(x)   -3 -5 -4        

 

2. Проверка плана на оптимальность

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

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

Первый опорный план, представленный в первой симплексной таблице неоптимальный, т.к. в индексной строке находятся отрицательные коэффициенты: -3; -5; -4.

Полагая что основные переменные х1=0; х2=0;х3=0, а дополнительные переменные х4=1100; х5=120; х6=800; f(x)=0. Следовательно, товары не продаются, а ресурсы не используются, доход равен нулю. В этом случае переходим к следующему этапу алгоритма.

3. Определение ведущих столбца и строки

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

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

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

За ведущий столбец выберем столбец, соответствующий переменной х2, т.к. сравнивания по модулю [-5] >[-3]; [-4].

Вычислим значения i по строкам и выберем наименование 1100/0,2 = 5500(min); 120/0,02=6000; 8000/1=8000; следовательно, строка х4 является ведущей.

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

4. Построение нового плана.

Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо (х i) (х4) в базис войдет переменная (х j) (х2) соответствующая ведущему столбцу.

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

2) 1100/0,2=5500; 0,1/0,2=0,5; 0,2/0,2=1;0,4/0,2=2;1/0,2=5.

2. Все остальные других строк определяются по формуле:

нов.коэфф.=соотв.коэфф.пред.табл. – (коэфф.ведущ.столбца х коэфф.нач.строки нов. плана)

Выполняя последовательно все этапы алгоритма, составляем план 2:

План Базисные переменные Свободные члены Основн. перемен. Допол.перем. 2
х1 х2 х3 х4 х5 х6
II х2   0,5            
х5   0,04   -0,02 -0,1      
х6   2,5     -5      
Индексная строка f(x2) 27 500 -0,5            

Анализ второго плана: План не оптимальный т.к. в индексной строке имеется отрицательный коэффициент (-0,5). Максимальный доход в размере 25.500 руб. торговое предприятие получит от продажи товаров второй группы В 5500 ед. (х2). Среди базисных переменных находится дополнительные переменные х5и х6. Это указывает на то, что ресурсы второго вида (площадь торговых залов) недоиспользована на 10 м2 и ресурсы третьего вида (площадь складских помещений) недоиспользованы на 2500 м2 .

На третьей итерации получаем план 3, который является оптимальным т.к. все коэффициенты в индексной строке 0.

 

План Базисные переменные Свободные члены Основн. перемен. Допол.перем. 2
х1 х2 х3 х4 х5 х6
III х2       2.25 6,25 12,5    
х1       0,5 -2,5      
х6       1,25 1,25 62,5    
Индексная строка F(x3) 27 625     5,75 23,75 12,5    

 

Анализ третьего плана: Необходимо продавать товаров первой группы А 250 ед., а второй группы В 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27625 тыс. руб. Товары группы С не реализуются.

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








Дата добавления: 2015-10-15; просмотров: 1149. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

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

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

Условия приобретения статуса индивидуального предпринимателя. В соответствии с п. 1 ст. 23 ГК РФ гражданин вправе заниматься предпринимательской деятельностью без образования юридического лица с момента государственной регистрации в качестве индивидуального предпринимателя. Каковы же условия такой регистрации и...

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

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

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

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

КОНСТРУКЦИЯ КОЛЕСНОЙ ПАРЫ ВАГОНА Тип колёсной пары определяется типом оси и диаметром колес. Согласно ГОСТ 4835-2006* устанавливаются типы колесных пар для грузовых вагонов с осями РУ1Ш и РВ2Ш и колесами диаметром по кругу катания 957 мм. Номинальный диаметр колеса – 950 мм...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия