Главная Обратная связь

Дисциплины:






МЕТОДИЧЕСКОЕ ПОСОБИЕ



к выполнению комплексного И.Д.З.

по дисциплине «оптимизационные методы и модели»

для студентов дневной формы обучения

 

 

Утверджено на заседании

кафедры прикладной математики.

 

Протокол№_______________

 

от “___” __________2012

 

 

Составитель:

к.т.н., доц. Нудный И.П.

 

 

Запоріжжя 2012

 

Задания комплексного И.Д.З.

 

 

Задача 1. Для производства изделий А,В,С используется четыре вида сырья.Каждый из видов сырья может бать использован в количестве.соответственно не большем М1,М234.

Нормы затрат каждого из видов сырья на единицу продукции и цена единицы продукции заданы таблицей.

Вид сырья Нормы затрат на единицу лродукции Колич. сырья
А В С
I М1
II М2
III М3
IV М4
Цена единицы продукции N1 N2 N3  

 

 


 

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

 

 

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

 

 

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

 

 

4.Найти зависимость максимальной стоимости продукции от количества сырья,ислользуемого полностью или с наименьшим остатком. Расчеты произвести на компьютере для значений [Mi / 2, 2Mi ] с интервалом ∆Mi=3Mi/10. Здесь і-номер сырья,используемого максимально.

 

Задача 2. Для производства изделий А и В используется три вида сырья.Каждый из видов сырья может бать использован в количестве.соответственно не большем М1,М23.

Нормы затрат каждого из видов сырья на единицу продукции и цена единицы продукции заданы таблицей.

 

Вид сырья Нормы затрат на единицу лродукции
А В
I
II
III
Цена едницы продукции 5N1 5N2

 

Общие расходы на производство единицы продукции вида А равны х1, а на производство единицы продукции вида В равны 2х2, где х1-количество единиц продукции вида А, х2-количество единиц продукции вида В.

Составить план производства,чтобы получить максимальную прибыль.



 

 

Задача 3. Полагая,что продукція производится в течении восьми месяцев, определить оптимальное количество работников в каждом месяце. Идеальное количество работников в i-ом месяце равно mi (i=1-8). Допускается,что работа i-го месяца может быть выполнена и меньшим числом работников при сверхурочной работе. Затраты, связанные с изменением количества работников при переходе от (i-1)-го месяца к i-му определяются функцией fi(xi-xi-1), где хi – фактическое количество работников в i-м месяце. Отклонение количества работников в i-м месяце от mi приводит к потерям

g (xi-mi). Первоначальное количество работников было m0.

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

 

fi(xi-xi) =

 

 

gi(xi-mi) =

 

Исходные данные задачи 1 и задачи 2

 

 

Вариант М1 М2 М3 М4 N1 N2 N3

 

 

Исходные данные задачи 3.

 

 

вариант a b c d m0 m1 m2 m3 m4 m5 m6 m7 m8

 

Методические указания.

 

 

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

Для нахождения оптимального решения применить симплекс-метод решения задач линейного программирования.

 

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

 

3. Для нахождения целочисленного решения воспользоваться методом отсекающих плоскостей (методом Гомори).

 

4. Для нахождения зависимости максимальной стоимости продукции от количества 1-го сырья необходимо решить 6 задач линейного программирования, которые отличаются друг от друга только количеством 1-го сырья (1- номер сырья,используемого максимально). Если максимально используется несколько видов сырья, то расчеты производить для любого из них.

Задачи решать на компьютере, используя процедуру “ Поиск решения “ .

 

5. Задачу 2 о максимилизации прибыли решать как задачу квадратичного программирования.

 

6. Задачу оптимизации числа работников решить методом динамического программирования. Учитывая,что начальное число работников m0 известно, оптимизацию нужно начинать с последнего месяца.

 

 

МIНIСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ

УКРАЇНИ

 

ЗАПОРІЗЬКИЙ ІНСТИТУТ ЕКОНОМІКИ І ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

 

ОБРАЗЕЦ

 

КОМПЛКСНОЕ И.Д.З.

по дисциплине «оптимизационные методы и модели»

 

Вариант № 0

 

 

Выполнил

ст. гр .ХХХХХ Ф.И.О. ______________

 

Руководитель Ф.И.О _______________

 

 

Запоріжжя 2012

 

Задача 1. Для производства изделий А, В, С используется четыре вида сырья. Каждый из видов сырья может бать использован в количестве.соответственно не большем 130, 80, 90, 70.

Нормы затрат каждого из видов сырья на единицу продукции и цена единицы продукции заданы таблицей.

 

 

Вид сырья Нормы затрат на единицу лродукции
А В С
I
II
III
IV
Цена единицы продукции


 

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

 

 

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

 

 

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

 

 

4.Найти зависимость максимальной стоимости продукции от количества сырья,ислользуемого полностью или с наименьшим остатком. Расчеты произвести на компьютере для значений [Mi / 2, 2Mi ] с интервалом ∆Mi=3Mi/10. Здесь і-номер сырья,используемого максимально.

 

Решение

1. Примем за х1 - количество изделий вида А , за х2 - вида В , за х3 - вида С. Тогда стоимость изделий найдется по формуле:

F= 10x1 + 8x2 + 12x3

По условию задачи она должна быть максимальной , т. е.

F= 10x1 + 8x2 + 12x3→ max

 

Ограничения на каждое из видов сырья:

1 + 4х2 + х3 ≤ 130

1 + 5х2 +3х3 ≤ 80

1 + х2 + 2х3 ≤ 90

1 + 6х2 +4 х3 ≤ 70

 

Кроме того , должно быть: х1 , х2 , х3 ≥ 0.

 

Приводим задачу к каноническому виду:

 

F= 10x1 + 8x2 + 12x3→ maх

1 + 4х2 + х3 + х4 = 130

1 + 5х2 +3х3 + х5 = 80

1 + х2 + 2х3 + х6 = 90

1 + 6х2 +4 х3 + х7 = 70

 

х1 , х2 , х3 , х4 , х5 , х6 , х7 ≥ 0.

Составим таблицу:

Базис Сбаз.  
А7
А5
←А7
    -10 -8 -12 ↑
225 / 2 7 /4 5 / 2 - 1 / 4
А5 55 / 2 --7 / 4 1 / 2 - 3 / 4
3 / 2 -2 - 1 / 2
А3 35 / 2 5 / 4 3 / 2 1 / 4
   

 

Так как все оценки ∆j ≥ 0 ,то имеем оптимальный план производства продукции.

Т.о. для получения максимальной стоимости в размере 210 д.е. нужно производить 17,5

Изделий вида С . Изделия вида А и В не производить.

 

2 . Рассмотрим двойственную задачу линейного программирования. Для этого введем обозначения: у1 – оценка единицы сырья I-го вида , у2 – I I-го вида , , у3 –Ш -го вида ,

у4 – I V-го вида . Тогда двойственная задача линейного программирования будет иметь вид:

 

F' = 130 y1 + 80 y2 + 90 y3 + 70 y4 → min

 

3 y1 + 2 y2 + 4 y3 + 5 y4 ≥ 10

4 y1 + 5 y2 + y3 + 6 y4 ≥ 8

y1 + 3 y2 + 2y3 + 4 y4 ≥ 12

_____

y1 , y3 ≥0 .

 

Выпишем решение прямой задачи:

 

Fmax = 210 . X = (0 , 0 , 35/ 2 ,225/2 , 55/2, 55 , 0 ). Сбаз = (0 , 0 , 0 , 12 ) .

Оптимальное решение двойственной задачи будет:

 

    Ах-1 = ( 1/∆ )     Ax = ( A4 , A5, A6 ,A3 )=

Уоп = Сбаз Ах-1

 

 

 

Ax = ( A4 , A5, A6 ,A3 )=

 

∆= 4

 

 

1 0 3 0 1 2 0 0 4   А12 = 1 0 3 0 1 2 0 0 4     А13 = 1 0 3 0 1 2 0 0 4   А14 = 1 0 3 0 1 2 0 0 4

 

А11 =


1 0 3 0 1 2 0 0 4   А22 = 1 0 3 0 1 2 0 0 4     А23 = 1 0 3 0 1 2 0 0 4   А24 = 1 0 3 0 1 2 0 0 4

 

А21 =

 

 

1 0 3 0 1 2 0 0 4   А32 = 1 0 3 0 1 2 0 0 4     А33 = 1 0 3 0 1 2 0 0 4   А34 = 1 0 3 0 1 2 0 0 4

 

А31 =

 

1 0 3 0 1 2 0 0 4   А42 = 1 0 3 0 1 2 0 0 4     А43 = 1 0 3 0 1 2 0 0 4   А44 = 1 0 3 0 1 2 0 0 4

 

А41 =

 

 

Отсюда:

А11 = 4 А12 = 0 А13 = 0 А14 = 0 А21 = 0 А22 = 4 А23 = 0 А24 = 0

 

А31 = 4 А32 = 0 А33 = 4 А34 = 0 А41 = 0 А42= 0 А43 = 0 А44 = 1

 

 

 

Уоп = (0, 0, 0 , 12) (1/4)


 

 

Так как положительной является двойственная оценка у4 , то для максимального увеличения прибыли необходимо дополнительно приобрести сырье IV-го вида .

 

 

3. Математическая модель целочисленного решения:

 

F= 10x1 + 8x2 + 12x3→ maх

 

 

х1 , х23 ≥0 , є Z.

 

 

Для получения целочисленного решения воспользуемся методом Гомори.

Возьмем последнюю симплекс-таблицу исходной задачи

 

 

225 / 2 7 /4 5 / 2 - 1 / 4  
А5 55 / 2 --7 / 4 1 / 2 - 3 / 4
3 / 2 -2 - 1 / 2
А3 35 / 2 5 / 4 3 / 2 1 / 4
   

Так как х1 = х2 = 0, х3 = 35/2 т.е. дробное, то составим дополнительное условие для х3:

 

( 1 / 4 )х1 + (1/2) х2 + (1 / 4)х7 ≥ 1/2 или

 

х1 + 2 х2 + х7 ≥ 2 *(-1)

 

1 - 2 х2 - х7 ≤ - 2

 

Приведем к равенству:

1 - 2 х2 - х7 + х8 = - 2

 

Припишем это условие к симплекс-таблице и продолжим решение двойственным

симплекс-методом

 

 

  Баз   Сбаз   А0
А1 А2 А3 А4 А5 А6 А7 А8
А4 225 / 2 7 /4 5 / 2 - 1 / 4
А5 55 / 2 --7 / 4 1 / 2 - 3 / 4
А6 3 / 2 -2 - 1 / 2
А3 35 / 2 5 / 4 3 / 2 1 / 4
А8 -2 -1 -2 -1
  -3

 

 

  Баз   Сбаз   А0
А1 А2 А3 А4 А5 А6 А7 А8
А4 - 1 / 4
А5 --1 - 3 / 4
А6 -1 - 1 / 2
А3 1 / 4
А7 -1
 

 

Так как в А0 нет отрицательных значений и все значения неизвестных целые, то имеем оптимальное решение. Т. е. изделие вида С нужно выпускать в количестве 17 шт. , изделия вида А и В не выпускаются. Стоимость продукции будет 204 д.е.

 

 

4.Находим зависимость максимальной стоимости продукции от сырья четвертого вида. Для этого находим решение исходной задачи для значений М4 =35,56,77,98,119,140.

Решение производим на компьютере в Excel.

Вводим исходные данные,полагая начальные значения неизвестных равными нулю.

Записываем формулы для левых частей ограничений (F3 -F6 ), целевой функции F11

 

A B C D E F H

 

1 сырье нормы затрат на ед. прод. колич лев.часть остаток

2 А В С сырья сырья

3 1в 3 4 1 130 В3*B11+C3*C11+D3*D11 F3-E3

4 2в 2 5 3 80 В4*B11+C4*C11+D4*D11 F3-E3

5 3в 4 1 2 90 В5*B11+C5*C11+D5*D11 F3-E3

6 4в 5 6 4 35 В6*B11+C6*C11+D6*D11 F3-E3

8 цен.ед. 10 8 12

9 прод.

10 х1 х2 х3 цел. ф-я

11 0 0 0 B8*B11+C8*C11+D8*D11

 

 

После введения формул для левых частей,целевой функции и остатков сырья (Н36)

на экране получим :

 

сырье номы затрат на ед. прод. колич. лев.часть остаток
  А В С сырья   сырья
             
ц. ед. пр.      
             
  X1 X2 X3 цел. Ф-ия  
     

 

 

Вызываем процедуру « Поиск решения» .Указываем,что целевая функция находится в ячейке F11 и что ее нужно минимизировать.Записываем дополнительные условия :

F3 ≤E3

F4 ≤E4

F5 ≤E5

F6 ≤E6

B11 ≥ 0

C11 ≥ 0

D11 ≥ 0

Поле выполнения вычислений получим:

 

сырье номы затрат на ед. прод. колич. лев. часть остаток
  А В С сырья   сырья
8,75 121,25
26,25 53,75
17,5 72,5
-4E-12
             
ц. ед. пр.      
             
  X1 X2 X3 цел. Ф-ия
  8,75    

 

 

Меняя количество сырья IV – го вида, получим остальные решения:

 

 

 
сырье номы затрат на ед. прод. колич. лев. часть остаток
  А В С сырья   сырья
-2E-12
             
ц. ед. пр.      
             
  X1 X2 X3 цел. Ф-ия
     
             
сырье номы затрат на ед. прод. колич. лев. часть остаток
  А В С сырья   сырья
19,25 110,75
57,75 22,25
38,5 51,5
9E-12
             
ц. ед. пр.      
             
  X1 X2 X3 цел. Ф-ия
  19,25    
               
сырье номы затрат на ед. прод. колич. лев. часть остаток
  А В С сырья   сырья
24,5 105,5
73,5 6,5
-3E-11
             
ц. ед. пр.      
             
  X1 X2 X3 цел. Ф-ия
  24,5    
               
сырье номы затрат на ед. прод. колич. лев. часть остаток
  А В С сырья   сырья
67,42857 22,571
             
ц. ед. пр.      
             
  X1 X2 X3 цел. Ф-ия
  5,2857 23,143   330,5714  
             
сырье номы затрат на ед. прод. колич. лев. часть остаток
  А В С сырья   сырья
58,75 71,25
-1E-09
-2E-09
138,75 1,25
             
ц. ед. пр.      
             
  X1 X2 X3 цел. Ф-ия
  13,75 17,5   347,5  
                 
 
   
   
Таким образом, имеем зависимость стоимости продукции от сырья IV-го вида (наиболее дифицитного):  
   
   
Сырье Х
Стоимость У 330,57 347,5
 
   
   
   

 

 

Задача 2. Для производства изделий А и В используется три вида сырья.Каждый из видов сырья может бать использован в количестве.соответственно не большем 130, 80, 90.

Нормы затрат каждого из видов сырья на единицу продукции и цена единицы продукции заданы таблицей.

 

 

Вид сырья Нормы затрат на единицу лродукции
А В
I
II
III
Цена едницы продукции

 

Общие расходы на производство единицы продукции вида А равны х1, а на производство единицы продукции вида В равны 2х2, где х1-количество единиц продукции вида А, х2-количество единиц продукции вида В.

Составить план производства,чтобы получить максимальную прибыль.

 

Решение :

 

Расходы на всю продукцию будут равны х12 + 2х22. Прибыль равна доходу минус расходы. Таким образом, получим математическую модель задачи :

 

 

f= 50x1 + 40x2 - х12 - 2х22→ mах



х1 , х2 ≥ 0.

 

 

 

Это задача квадратичного программирования.

Решение:

 

Составим функцию Лагранжа:

 

 

L = 50x1 + 40x2 - х12 - 2х22 + λ1 (130 - 3х1 - 4х2 ) + λ2 (80 - 2х1 - 5х2 ) + λ3 (90 - 4х1 - х2 ).

 

Необходимые и достаточные условия существования экстремум

 

 


Вводя дополнительные переменные,неравенства приведем к равенствам. Тогда необходимые и достаточные условия запишутся

 

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

F = -Mz1 – Mz2 → max

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

 

Баз. пер. Сбаз А0
x1 x2
-M -1
-M -1
  -90 M -2 M - 4 M ↑↑ -7 M -7 M -5 M M M

 

Баз. пер. Сбаз А0 -M  
x1 x2 z1  

 

-M -1  
x2 5/4 1/4 -1  
-4 -5 -1  
-5 -25/4 -5/4  
-1 -5/4 -1/4  
  -50 M -2 M -3 M -2 M -4 M ↑ M  

 





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...