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

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

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






 

Лабораторная работа №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; просмотров: 3157. Нарушение авторских прав; Мы поможем в написании вашей работы!



Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

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

ТЕОРИЯ ЗАЩИТНЫХ МЕХАНИЗМОВ ЛИЧНОСТИ В современной психологической литературе встречаются различные термины, касающиеся феноменов защиты...

Этические проблемы проведения экспериментов на человеке и животных В настоящее время четко определены новые подходы и требования к биомедицинским исследованиям...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

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

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

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

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