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

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

Задача №4-5.





Решить задачу линейного программирования двумя способами (графическим и симплекс-методом).

Для изготовления двух видов продукции используется три вида сырья. При производстве единицы продукции первого вида затрачивается А1 кг сырья первого вида, А2 кг сырья второго вида и А3 кг сырья третьего вида. При производстве единицы продукции второго вида затрачивается Б1 кг сырья первого вида, Б2 кг сырья второго вида и Б3 кг сырья третьего вида. Запасы сырья первого вида составляют Запасы1 кг, второго – Запасы2 кг, третьего – Запасы3 кг. Прибыль от реализации единицы продукции первого вида составляет С1 ден. ед., прибыль от реализации единицы продукции второго вида составляет С2 ден. ед.

Определить оптимальный план выпуска продукции(количество выпускаемой продукции округлить до целого числа), чтобы прибыль от реализации была максимальной.

 

А1=9, А2=6, А3=5, В1=3, В2=12, В3=8,

Запасы1=230, Запасы2=210, Запасы3=250, C1=18, C2=20.

 

ГРАФИЧЕСКИЙ СПОСОБ РЕШЕНИЯ

Пусть количество выпускаемой первой продукции – x1, а количество второй – x2, тогда прибыль от продажи всей продукции:

F=18x1 + 20x2 → max

при условиях:

9x1 + 3x2 ≤ 230;

6x1 + 12x2 ≤ 210;

5x1 + 8x2 ≤ 250;

x1 ≥ 0; x2 ≥ 0.

 

Неравенства заменяем на равенства, x2 заменяем на y. Строим линии ограничений.

1) 9x + 3y1 = 230

y1 = 76,7 - 3x

x y1
  76,7
25,6  

 

2) 6x + 12y2 = 210

y2 = 17,5 - 0,5x

x y2
  17,5
   

 

3) 5x + 8y3 = 250

y3 = 31,25 - 0,625x

x y3
  31,25
   

 

4) x = 0

y = 0

Область допустимых значений - выпуклый многоугольник OACD.

Строится направляющий вектор C.

Строится перпендикуляр к вектору С через начало координат.

Точка С является точкой оптимума. Находим координаты точки оптимума. Приравниваем уравнения 1 и 2.

76,7 - 3x = 17,5 - 0,5x

x = 23,68

подставляем x в уравнение:

y = 76,7 - 3x

y = 5,66

Координаты точки С (23,68; 5,66).

Находим значение целевой функции точки оптимума.

F(C) = 18*23,68 + 20*5,66 = 426,24 + 113,2 = 539,44

Округлённые результаты (округление в меньшую сторону):

F(C) = 18*23 + 20*5 = 514

Ответ: необходимо выпускать 23 единицы первого вида продукции, 5 единиц второго вида продукции, при этом прибыль будет максимальной, и будет равна 514 денежных единиц.


 

РЕШЕНИЕ СИМПЛЕКС-МЕТОДОМ

Ресурсы Пункты назначения Запасы
   
А1      
А2      
А3      
Прибыль    

 

Пусть количество выпускаемой первой продукции - x1, а количество второй - x2, тогда прибыль от продажи всей продукции

F=18x1 + 20x2 → max

при условиях:

9x1 + 3x2 ≤ 230;

6x1 + 12x2 ≤ 210;

5x1 + 8x2 ≤ 250;

x1 ≥ 0; x2 ≥ 0.

Неравенства заменяем на равенства, вводим искусственные переменные.

9x1 + 3x2 + x3= 230

6x1 + 12x2 + x4= 210

5x1 + 8x2 + x5= 250

Строится исходная симплекс-таблица.

Базисные решения Свободные члены x1 x2 x3 x4 x5
x3            
x4     12      
x5            
Оценки коэффициентов целевой функции          

 

Первая итерация.

Ищем генеральный столбец:

max (18, 20) = 20 => второй столбец генеральный.

Ищем генеральную строку:

min = = 17,5 => вторая строка генеральная.

Генеральный элемент находится на пересечении второго столбца и второй строки = 12 => заменим x4 на x2.

Все элементы генеральной строки(включая свободные члены) делятся на генеральный элемент.

Базисные решения Свободные члены x1 x2 x3 x4 x5
x2 17,5
x3 177,5 7,5 0   -0,25  
x5          
Оценки коэффициентов целевой функции          

 

Преобразование строки x3: 230 – 17,5*3 = 177,5 9 – *3 = 7,5 3 – 1*3 = 1 1 – 0*3 = 1 0 – *3 = = –0,25 0 – 0*3 = 0   Преобразование строки x5: 250 – 17,5*8 = 110 5 – *8 = 1 8 – 1*8 = 0 0 – 0*8 = 0 0 – *8 = 1 – 0*8 = 1  

 

Преобразование строки "Оценки коэффициентов целевой функции":

18 – *20 = 8

20 – 1*20 = 0

0 – 0*20 = 0

0 – *20 =

0 – 0*20 = 0

F = 18*0 + 20*17,5 = 350

Базисное решение неоптимально, т.к. имеется положительное значение в строке "Оценки коэффициентов целевой функции".

Вторая итерация.

Ищем генеральный столбец:

max (8, ) = 8 => первый столбец генеральный.

Ищем генеральную строку:

min = = 23,67 => вторая строка генеральная.

Генеральный элемент находится на пересечении первого столбца и второй строки = 7,5 => заменим x3 на x1.

Все элементы генеральной строки(включая свободные члены) делятся на генеральный элемент.

 

Базисные решения Свободные члены x1 x2 x3 x4 x5
x1
x2 5,665 0 1 – 0,1  
x5 86,33     – 0,7  
Оценки коэффициентов целевой функции 539,36     – 1,6  

 

Преобразование строки x2: 17,5 – 23,67*0,5 = 5,665 0,5 – 1*0,5 = 0 1 – 0*0,5 = 1 0 *0,5 = + *0,5 = + = = = 0,1 0 – 0*0,5 = 0 Преобразование строки x5: 110 – 23,67*1 = 86,33 1 – 1*1= 0 0 – 0*1 = 0 0 *1 = *1 = = = = –0,7 1 – 0*1 = 1

Преобразование строки "Оценки коэффициентов целевой функции":

8 – 1*8 = 0

0 – 0*8 = 0

0 *8 = =

*8 = = = –1,6

0 – 0*8 = 0

F = 23,67*18+5,665*20 = 426,06 + 113,3 = 539,36

Округлённые результаты (округление в меньшую сторону):

F(C) = 23*18 + 5*20 = 514

Ответ: необходимо выпускать 23 единицы первой продукции, 5 единиц второй продукции, при этом прибыль будет максимальной, и будет равна 514 денежных единиц.

 







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




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


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


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


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

Философские школы эпохи эллинизма (неоплатонизм, эпикуреизм, стоицизм, скептицизм). Эпоха эллинизма со времени походов Александра Македонского, в результате которых была образована гигантская империя от Индии на востоке до Греции и Македонии на западе...

Демографияда "Демографиялық жарылыс" дегеніміз не? Демография (грекше демос — халық) — халықтың құрылымын...

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

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

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

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

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