Студопедия Главная Случайная страница Обратная связь

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

Решение исходной задачи симплексным методом





 

Лабораторная работа №1. Построение информационной модели

Построить иерархическую информационную модель на примере своего генеалогического древа. Построение модели осуществить в следующих программах:

1. Word.

2. Power Paint

3. Visio.

 

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

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

Имеется производство по изготовлению двух видов продукции А и В при имеющемся объеме материалов трех сортов, из которых производится продукция. Исходные данные приведены в таблице.

Вариант 1

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 2

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 3

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 4

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 5

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 6

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 7

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 8

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 9

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

Вариант 10

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

 

Пример выполнения:

Предположим, что для производства двух видов продукции А и В можно использовать только материал трех сортов. При этом на изготовление единицы изделия вида А расходуется а1 кг материала первого сорта, а2 кг материала второго сорта и а3 кг материала третьего сорта. На изготовление единицы вида В расходуется b1 кг материала первого сорта, b2 кг материала второго сорта, b3 кг материала третьего сорта. На складе фабрики имеется всего материала первого сорта С1 кг, второго сорта – С2 кг, третьего – С3 кг. От реализации единицы продукции вида А фабрика имеет прибыль m тысяч рублей, а от реализации вида В прибыль составляет n тысяч рублей.

Исходные данные представлены в таблице:

 

Виды продукции Норма расхода материала на единицу продукции Прибыль на единицу продукции
     
А        
В        
Запасы сырья       ?

 

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

Пусть x1 количество продукции вида А, x2 количество продукции вида В. Тогда количество материала первого сорта требуемого на изготовление продукции 1 будет 3x1 +2х2 .По условию данной задачи это число не должно превышать 32, следовательно получим первое ограничение 3x1 +2х2 ≤ 32 (1)

4x1 + 5х2 - количество материала второго сорта, требуемое на изготовление продукции 2, которое не должно превышать 48. исходя из этого, получим второе ограничение

4x1 + 5х2 ≤ 48 (2)

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

x1 + 6х2, которое по условию данной задачи не должно превышать 40, таким образом получим третье ограничение x1 + 6х2 ≤ 40 (3)

Поскольку х1 и х2 выражают количество выпускаемой продукции, то они не должны быть отрицательными (требования не отрицательности переменных), следовательно

x1≥0, x2≥0. (4)

Задача состоит в том, чтобы найти такие значения х1 и х2, при которых прибыль будет максимальной. Таким образом, 6х1 – прибыль, полученная от реализации продукции вида А, а 11х2 – прибыль, полученная от реализации продукции вида В. Следовательно, прибыль на единицу продукции, которая должна быть максимальной будет иметь следующий вид

F= 6x1 + 11х2 (целевая функция задачи)

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

3x1 +2х2 ≤ 32 (1)

4x1 + 5х2 ≤ 48 (2)

x1 + 6х2 ≤ 40 (3)

x1≥0, x2≥0. (4)

F= 6x1 + 11х2 →max

 

 

Решение исходной задачи симплексным методом

 

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

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

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

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

3x1 +2х23 = 32

4x1 + 5х24= 48

x1 + 6х25= 40

хi≥0, i=1..5.

F= 6x1 + 11х2 →max.

Запишем данную задачу в исходную симплексную таблицу:

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5
               
  х3            
  х4            
  х5            
  F   -6 -11      

Первые три строки этой таблицы содержат в условной форме систему ограничений, а именно в столбце ai 0 - записываются свободные члены уравнений. В столбцах х1, х2, х3, х4, х5 – записываются коэффициенты при соответствующих переменных этой системы.

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

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

а00 = 0∙32+0∙48+0∙40=0

Остальные значения обозначаются а0k, получаются в результате скалярного умножения вектора столбца Сi на вектор столбец коэффициента при неизвестном xk c последующим вычитанием соответствующего элемента верхней строки, например: а01=(0∙3+0∙4+0∙1)-6 = -6

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

1. выбираем в исходной таблице разрешающий столбец- p. Этот столбец соответствует наибольшей по абсолютной величине отрицательной оценке. В данной задаче это будет столбец х2 (т.к |-6| < |-11|).

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

, т.е. 32/2=16, 48/5=9,6, 40/6=6,66(min)

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

 

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5  
           
                 
  х3            
  х4    
 
5

       
  х5             q
  F   -6 -11        
        p        

3. В новой симплексной таблице элементы разрешающей строки пересчитываем по формуле:

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

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

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5
         
  х3      
  х4      
  х2      
  F      

 

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

: =7

: = (min)

: = 40

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

 

Составляем новую таблицу - на месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы пересчитываем по формуле прямоугольников.

Получим таблицу

 

Сi Базис (xi) Ai0 х1 х2 х3 х4 х5
         
  х3      
  х1      
  х2      
  F      

 

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

Оптимальное решение получаем в виде вектора

xопт = (х1, х2, х3, х4, х5)

Fmax = 92,63

Оптимальное решение к исходной задаче получается отбрасыванием из xопт компонент, связанными с балансовыми переменными х3, х4, х5, т.е

xопт =(, )

Fmax = ∙6-11∙ = =92,63

Следовательно, фабрике необходимо выпускать единицы продукции вида А и единицы продукции вида В, при этом максимальная прибыль составляет 92,63 тысячи рублей.

 







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




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


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


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


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

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

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

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

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

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

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

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