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

Лабораторная работа №2. Симплексный метод определения оптимального плана

Читайте также:
  1. II. Работа в базе данных Microsoft Access
  2. II. Работа с лексическим составом языка
  3. II. Работа с текстом
  4. IV. Культурно-просветительская работа.
  5. IV. Работа с текстом
  6. V1: Договорная работа с поставщиками и посредниками
  7. Автором опыта выделен алгоритм формирования умения работать с моделями.
  8. Безопасность при погузочно-разгрузочных работах.
  9. Безопасность труда при эксплуатации установок и сосудов работающих под давлением
  10. Бумаги или работа?
  11. В 1. Физическая сущность сварочной дуги. Зажигание дуги. Термоэлектронная и автоэлектронная эмиссии. Работа выхода электрона.
  12. В Казахстане разработали интернет-алфавит казахского языка на латинице

Симплексный метод определения оптимального плана

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

Предприятие реализует n товарных групп, располагая m ограниченными материально-денежными ресурсами bi ≥0 (1 ≤ i ≤ m). Известны расходы ресурсов каждого i- вида на производство и реализацию единицы товара каждой группы, представленные в виде матрицы (a ij) и прибыль, получаемая предприятием от реализации единицы товара j-группы, входящая в целевую функцию Z(X). Метод линейного программирования не отличается от системы (1)-(2):

Z(X) = с1 Х1 + с2 Х2 + с3 Х3 + … +сn Хn →max(min) (1)

 

a11 X1 + a12 X2 +…a1n X n ≤ b1,

а21 X1 + a22 X2 +…a2n X n ≤ b2 (2) ……………………………………..

am1 X1 + am2 X2 +…a mn X n ≤ b m,

 

X1≥0 X2≥0 X3≥0 …X n ≥0

 

 

Этапы решения поставленной задачи симплексным методом включают:

1) Составление нулевого опорного плана. Вводим новые неотрицательные (базисные) переменные, благодаря которым система неравенств (2) становится системой уравнений:

a11 X1 + a12 X2 +…a1n X n + Xn+1 = b1

a21 X1 + a22 X2 +…a2n X n + Xn+2 = b2 (3) ……………………………………..

am1 X1 + am2 X2 +…a mn X n + Xn+m = b m,

 

Если принимать вводимые переменные за векторы-столбцы, то они представляют собой единичные (базисные!) векторы. Отметим, что базисные переменные имеют простой физический смысл – это остаток конкретного ресурса на складе при заданном плане выпуска продукции, поэтому данный базис называют естественным. Решаем систему (3) относительно базисных переменных:

 

Xn+1 = b1, -a11 X1 - a12 X2 -…a1n X n

Xn+2 = b2 - a21 X1 - a22 X2 -…a2n X n (4) ………………………………………..

Xn+m = b m, - am1 X1 + am2 X2 +…a mn X n

 

Целевую функцию перепишем в виде

Z(X)=0-(-с1Х12Х23Х3-…-сnХn) (5) Полагая, что искомые основные переменные Х1= X2=X3=…=Xn =0, получаем нулевой опорный план Х =(0,0, …0,b1,b2,b3…bm), при котором Z(X) = 0 (все ресурсы на складе, ничего не производится!). Заносим план в симплексную таблицу.

 

План Базис Ci/Cj Знач. Xi X1 X2 Xn Xn+1 Xn+2 Xn+3 Qmin
  Xn+1   b1 a11 a12 a13       b1/ a12
Xn+2   b2 a21 a22 a23       b2/ a22
Xn+3   b3 a31 a32 a33       b3/ a32
Z(X) = 0 -C1 - C2 - C3       Индекс. строка

 

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

3) Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса. Сначала заменим в базисе Хj на Хi ведущего столбца. Разделим все элементы ведущей строки на разрешающий элемент (РЭ), в результате чего на месте РЭ в ведущей строке будет 1. Так как Хi стал базисным, то остальные его коэффициенты должны быть равны 0. Новые элементы этого плана находятся по правилу прямоугольника

НЭ=СЭ – (А*В)/РЭ (6)

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

Пример №2.

На приобретение оборудования для производственного участка выделено 20тыс. руб. Оборудование может быть размещено на площади, не превышающей 72 кв.м. Можно заказать оборудование двух типов: типа А, требующие производственную площадь 6кв.м и дающие 6 тыс.ед. продукции в смену (цена 5000 руб.) и типа В, требующие площадь 12 кв.м и дающие 3тыс.ед., (цена 2000 руб.). Каков оптимальный план приобретения оборудования, обеспечивающий максимальную производительность участка?

Обозначим количество приобретаемого оборудования типа А и В через Х1 и Х2 соответственно.

Производительность участка (целевая функция): Z(X) =6Х1+3Х2.

Основные ограничения связаны

с денежными средствами: 5Х1+2Х2 ≤ 20,

с площадью производственного участка: 6Х1+12Х2 ≤ 72.

Вводим новые базисные переменные Х3 (остаток денежных средств после закупки оборудования) и Х4 (остаток площадей после размещения оборудования) и перепишем ограничения в виде системы уравнений:

5X1+2Х2+X3=20 (X3=20 – 5X1 - 2X2)

1+12Х2+X4 = 72 (X4=72 – 6X1 – 12X2)

При этом функция цели: Z(X) =6Х1+3Х2+0Х3+0Х4.

Составляем опорный (0-ой) план: Х= (0, 0, 20, 72), т.е. пока ничего не приобретено (деньги не потрачены, площади пустуют). Составляем симплексную таблицу

План Базис Ci/Cj Знач. Xi X1 X2 X3 X4 Qmin
  X3             20/5=4
X4             72/6=12
Z(X) = 0 - 6 - 3     Индексная строка
  →X1       0,4 0,2   4/0,4=10
X4       9,6 -1,2   48/9,6=5
Z(X) = 6*4=24   -0,6 1,2   Индексная строка
  X1         0,25 -1/24 -
→X2         -1/8 5/48 -
Z(X) =6*2+3*5=27     9/8 1/16 Индексная строка
                       

 

 

Очевидно, что ведущий столбец соответствует Х1, так как имеет самый большой индекс 6. Находим минимальное значение Qmin=4 (самое жесткое ограничение ресурса), определяя ведущую строку, показывающую, что из базисных переменных выводится Х3, а вместо нее вводится Х1. Пересчитываем элементы ведущей строки, разделив их на 5, а по формуле (6) определяем элементы второй и индексной строк. Целевая функция для 1-ого плана равна Z(X) =6*4+3*0=24.Однако, один из коэффициентов индексной строки для столбца Х2 остается отрицательным -0,6, следовательно данный план не оптимален, и требуется еще одна итерация (шаг) для его улучшения. Выбираем ведущим 2-ой столбец и по минимальному значению Qmin=5 определяем ведущую строку с базисной переменной Х4. Выполнив те же преобразования, получаем 2-ой план, который будет оптимальным, так как все индексные коэффициенты положительны. Проанализируем полученные результаты. При оптимальном решении целевая функция имеет максимальное значение 27тыс.руб., при этом оба ресурса выведены из базиса, следовательно израсходованы полностью! Убедимся в этом: 5*2+2*5=20 тыс.руб., 6*2+12*5=72 кв.м. Искомое решение Х= (2; 5;0;0;).Так бывает далеко не всегда.

Пример №3.

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

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

 

В последней строке задан доход от продажи товара каждой группы. Необходимо определить объем и структуру товарооборота, при котором доход предприятия будет максимальным. Математическая модель задачи: определение вектора Х=(Х1; Х2; Х3), где Х – количество проданных изделий А, В,С, который удовлетворяет неравенствам

 

 

0,1X1 + 0,2X2 +0,4 X3 ≤ 1100,

0,05X1 + 0,02X2 +0,02 X3 ≤ 120,

3X1+1X2+2X3≤8000. X1≥0 X2≥0 X3≥0

и обеспечивает максимальное значение целевой функции Z(X)=3Х1+5Х2+4Х3.

Для построения опорного 0-ого плана вводим дополнительно базисные переменные Х4, Х56 (определяем объемы неиспользованных ресурсов), преобразовывая систему неравенств в систему уравнений,

0,1X1 + 0,2X2 +0,4 X34= 1100,

0,05X1 + 0,02X2 +0,02 X35= 120,

3X1+1X2+2X36=8000.

решаем полученную систему относительно базисных переменных Х4, Х5, Х6:

Х4=1100-0,1X1 - 0,2X2 -0,4 X3,

Х5= 120-0,05X1 - 0,02X2 -0,02 X3,

Х6=8000-3X1 -X2-2X3.

Функцию цели запишем в виде Z(X)=0 – (- 3Х1 – 5Х2 – 4Х3) и полагая, что основные переменные Х123=0, получим опорный план Х=(0; 0; 0; 1100; 120; 8000), при котором целевая функция Z(X)=0 (товары не продаются, ресурсы не используются, доход нулевой). Опорный план запишем в симплексную таблицу:

План Базис Ci/Cj Знач. Xi X1 X2 X3 X4 X5 X6 Qmin
  X4     0,1 0,2 0,4        
X5     0,05 0,02 0,02        
X6                  
Z(X) = 0 - 3 - 5 - 4       Индекс строка
  →X2     0,5            
X5     0,04   -0,02 -0,1      
X6     2,5     -5      
Z(X) = 27500 - 0,5           Индекс строка
  X2         2,25 6,25 -12,5   -
→X1         -0,5 -2,5     -
X6         1,25 1,25 -62,5   -
Z(X) = 27625     5,75 23,75 12,5   Индекс строка

 

Естественно, 0-ой план не оптимален, так как коэффициенты в индексной строке отрицательные -3, -5, -4.Ведущий столбец содержит Х2, а ведущая стока содержит Х4, РЭ=0,2 находится на их пересечении. Формируем 1-ый план аналогично предыдущему примеру, в индексной строке только коэффициент при Х1 отрицателен -0,5, поэтому ведущий столбец содержит Х1. Строка, содержащая Х5, становится ведущей, и после итерации получаем 2-ой план, все коэффициенты которого в индексной строке положительны. Это означает, что план Х= (250; 5375; 0; 0; 0; 1875) оптимален, и целевая функция при данных значениях Х имеет максимальное значение Z(X) =27625 тыс.руб.

Проанализируем полученное решение: для получения максимальной прибыли необходимо продать 250 ед. товаров группы А, 5375 ед. товаров группы В, товары группы С вообще не реализуются! В оптимальном плане среди базисных переменных находится Х6. Это указывает на то, что 1875м2 складских помещений не используются, то есть данный ресурс в исходном объеме избыточен, и данная его часть (1875м2) может быть применена в других целях.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

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



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