Задача 1ассортиментная задача Чистоган НА ПЕЧ А..

Задача 1 (Ассортиментная задача).
Составить модель оптимального плана выпуска продукта для цеха кондитерской фабрики. Виды выпускаемой продукции (М), виды основного сырья (П) и его запасы, нормы расхода сырья на единицу, уровни прибыли приведены в таблице.
Рассчитать план и провести его анализ.

Виды сырья
Расход сырья на единицу продукта
Общий запас сырья в ед.


М1
М2
М3


П1
3(а11)
4(а12)
1(а13)
200

П2
2(а21)
1(а22)
3(а23)
303

П3
4(а31)
3(а32)
2(а33)
272

Уровень прибыли на ед. продукта
24(С1)
28(С2)
20(С3)



Для их производства используются основные виды ресурсов (сырья) трёх видов, условное название П1 ,П2, П3 ед.
Расход каждого ресурса, а производство единице является заданной величиной, определяется по рецептуре и обозначается символами а11,а12,.а32,а33. Где а – норма расхода, первая подстрочная 1,2,3 – номер ресурса, вторая подстрочная 1,2,3 – номер ассортиментной группы конфет.
Расход каждого ресурса на производство единицы продукции является задачной величиной, определения на рецептуре и обозначения символами а11 , а12,а32, а33, где а – норма расхода, первая подстрочная 1,2,3 – номер ресурса, номер ресурса, вторая подстрочная 1,2,3 – номер ассортиментной группы конфет.
Наличие каждого ресурса для производства всех групп конфет принимается, как известная величина обозначается символами b1, b2, b3.
Прибыль на продукцию также принимается как известная величина и обозначается символами С1, С2, С3.
Перечисленные параметры являются известными величинами и выражаются в единицах измерения, кроме прибыли. Прибыль или другой какой-либо показатель, являющийся критерием оптимальности, выражается в единицах измерения дохода (например, прибыли), получаемого от производства единицы продукции в денежном или ином выражении.
Поскольку решение задачи заключается в поиске такого плана производства, который обеспечивал бы принятие условия наибольшего дохода, принимаются те величины, которые являются неизвестными и обозначающими количествами каждой группы доходов, принимаются те величины, которые являются неизвестными и обозначающими количество каждой группы конфет, включаемых в план производства:
х1 для М1 ; х2 для М2 ; х3 для М3.


Экономико-математическая модель в символическом виде.

а11 х 1+а12 х2 +а13 х3
·b

· Система ограничений (по сырью): а21 х1 +а22 х2 +а23 х3
·b
а31 х1 +а32 х2 +а32 х3
·b


· Целевая функция (суммарных доходов) F=c 1x 1+c 2x 2+c 3x 3max.
Условия не отрицательности переменных х1
·0,х2
·0,х3
·0.
Символическая модель, наполненная численной информацией, будет иметь следующий вид:
3х1+ 4х2 + х3
·200

· Система ограничений: 4х1+2х2 +3х3
·303
4х1 +3х2 + 2х3
·272

· Целевая функция (суммарных доходов) F=24x1+28x2+20x3max


· Условия не отрицательности переменных х1
·0,х2
·0,х3
·0.

Решение задачи.
200=3х1+4х2+1х3+1 х4
303=2х1+1х2+3х3+1х5
272=4х1+3х2+2х3+1х 6

Для решения задачи симплекс-методом неравенство преобразуются в эквивалентные +1 равенства путем добавления каждого неравенство по одному дополнительному неизвестному с коэффициентом, и получим уравнений прибыли. Для удобства расчетов левые и правые части уравнения меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений приведенных справа.
Коэффициенты при неизвестных записывают в симплексной таблице, в которой выполняются расчеты и отражаются полученные результаты.
В столбцах таблицы записывают:
в первом (Сi)- прибыль единицы продукции, которая вводится в план выпуска;
во втором (P0)- свободные величины, в остальных – коэффициенты при неизвестных уравнений. В верхней части столбцов отображаются коэффициенты неизвестных целевой функции.
В нижней строке (целевой) записываются получаемые расчетным путем показателя: в столбце Х0- суммарная прибыль планового выпуска, в остальных столбцах прибыль единицы продукции с отрицательным знаком.
В последних трех столбцах коэффициенты при дополнительных неизвестных, равны единице, расположены диагонально. Эта часть таблицы, называемая единичной подматрицей, необходима для вычислительных и аналитических целей.
При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой и для удобства расчетов выделяется. В нашем примере таким столбцом будет Х2, имеющий в целевой строке наибольшую модулю величину (-28).
Затем элементы столбцов Х0 (свободной величины) делят на соответствующие коэффициенты ключевого столбца, полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и для удобства выделяется.
В нашем случае:
272/3=90.6 303/1=303 200/4=50

· Наименьшее отношение 50 имеет строка Х4. Она и будет ключевой. Ключевой элемент (4).

Исходная таблица
Сi
P0
X0
24
20
28
0
0
0




X1
X2
X3




0
·
X4
200
3
4
1
1
0
0

0
X5
303
2
1
3
0
1
0

0
X6
272
4
3
2
0
0
1

Zi -Ci
0
-24
-28
-20
0
0
0

1. Далее элементы таблицы преобразуются и записываются в новую таблицу. Первоначально преобразуют элементы ключевой строки путем деления на ключевой элемент (4). Преобразованные элементы записывают в том же самом месте.
В столбцах Р0 и Сi занимают место вводимая в неизвестной Х1 с прибылью 28.
Остальные элементы преобразуются по следующему правилу.

· для преобразуемого элемента в его столбце элемент ключевой строки, а его строке-элемент ключевого столбца.

· соответствующие элементу ключевой строки и ключевого столбца перемножаются, и получается произведение делят на ключевой элемент.

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

Следуя правилу, преобразование элементов столбцов будет:

200/4=50 3/4=3/4 4/4=4/4 1/4=1/4 1/4=1/4
303-(200
·1)/4=253 2-(3
·1)/4=5/4 3- (1
· 1)/4=11/4 0- (1
· 1)/4=1 0- (0
· 1)/4= 0
272-(200
·3)/4=122 4-(3
· 3)/4=7/4 2-(1
· 3)/4=5/4 0-(0
· 3)/4=0 1-(0
· 3)/4=1
0-200(-28)/4=1400 -24-3(-28)/4=-3 -20-1(-28)/4=-13 0-1(-28)/4=7


Итерация 1

С1
Р0
Х0
24
20
28
0
0
0




X1
X2
X3
X4
X5
X6

28
X2
50
3/4
1
1/4
1/4
0
0

0
X5
253
5/4
0
11/4
-1/4
1
0

0
X6
122
7/4
0
5/4
-3/4
0
1

Сi-Zi
1400
-3
0
-13
7
0
0

2. Включение на первой итерации неизвестной Х1 (выпуска продукции) П обеспечит сумму прибыли 1400.

· Решение задачи продолжается, т.к. в целевой строке два отрицательных элемента.
· Наибольший по модулю элемент (-13) находится в столбце Х3, который принимается за разрешающий, а ключевой строкой будет Х5

13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415
13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415
13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415
13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415

Итерация 2
Сi
P0
X0
24
20
28
0
0
0




X1
X2
X3




28
X2
27
7/11
1
0
3/11
-1/11
0

20
X3
92
5/11
0
1
-1/11
4/11
0

0
X6
7
13/11
0
0
-7/11
-5/11
1

Сi-Zi
2596
32/11
0
0
64/11
52/11
0


·В последней таблице целевая строка имеет только положительные элементы. Это значит, что составленный план оптимален и дальнейшее улучшение не возможно.




3
·0 + 4
·27 + 92
·200
2
·0 + 27 + 3
·92
·303
4
·0 + 3
·27 + 2
·92
·272
F=24
·0+28
·27+20
·92=2596

F=2596 X2=27ед Х3=92ед


·На складе останется сырье третьего вида Х6=7. Таким образом найден оптимальный план.

·А продукцию первого вида (Х1=0) производить не надо.

·Выпускаем продукцию только Х2 и Х3.

Условия задачи 2.
( Транспортная задача).

Составить оптимальный план перевозок пищевых продуктов от четырех поставщиков к шести потребителям.
П – поставщик (склад).
М – потребитель (магазин).
Число поставщиков М= 6
Число магазинов П= 4

·Построение исходного плана перевозок с помощью методов:

·а) северо – западного угла.

·б) наименьшего элемента по строке.

·в) наименьшего элемента по столбцу.

·г) наименьшего элемента по матрице.

Построение оптимального плана перевода с помощью метода потанцеала.

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

Xij – количество груза; (Т) доставленного от i – того поставщика к j-тому потребителю.

В качестве неизвестной величины определяется Xij – количество грузов, которое не обходимо доставить i-тому к j-тому, то есть потребителю.










Экономико-математическая модель в символическом виде.

1. Каждый поставщик может отправить потребителю столько продукции сколько он имеет, т.е. сумма поставок по каждый строке должна быть равна запасам по этой строке.
X11 + X12 + . + X1n = a1
X21 + X22 + .. + X2n =a2


Xm1 +Xm2 + +Xmn =amn

2. Каждому потребителю необходимо получить столько продукции, сколько ему требуется. Т.е. сумма поставок по каждому столбцу должна быть равна потребностью по этому столбцу.
Х11 + Х21 + .. +Хm1 = b1
X12 + X22 + .. + Xm2 = b2
..
..
X1n + X2n + +Xmn = bn
m = 6 n = 4

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

F = C11
·X11 + C12
·X12 + C1n
·X1n +..+ Cm1Xm1 +..+CmnXmn = min

В качестве целевой функции вводим F – транспортная работа.

4. Запасы и потребности должны удовлетворять условия не отрицательности.
ai
· 0 (i = 1,2..m)
bj
· 0 (j = 1,2 .. m )

5. Неизвестные величины (количество грузов) должны удовлетворять условие не отрицательности.
Хij
·0






Решение задачи.

1) 8км. 132 – 36 = 96 ост П4
2) 9км. 148 -92 = 56 ост П1
3) 15км. 144 -112 = 32 ост П3
4) 20км. 80 – 76 = 4 ост М3
5) 24км. 84 – 56 = 28 ост М5
6) 30км. 32 – 28 = 4 ост П3
7) 30км. 96 – 96 = 0 ост
8) 39км. 4 – 4 = 0 ост

Система ограничений по поставщикам:

Х11 + Х12 + Х13 + Х14 + Х15 + Х16 = 148
Х21 + Х22 + Х23 + Х24 + Х25 + Х26 =76
Х31 + Х32 + Х33 + Х34 + Х35 + Х36 = 144
Х41 + Х42 + Х43 + Х44 + Х45 + Х46 =132

2.Система ограничений по потребителям:

Х11 +Х12 + Х13 + Х14 = 36
Х21 +Х22 + Х23 + Х24 = 96
Х31 + Х32 + Х33 + Х34 = 80
Х41 + Х42 + Х43 + Х44 = 112
Х51 + Х52 + Х53 + Х54 = 84
Х61 + Х62 + Х63 + Х64 = 92

3. Условие min целевой функции:

F = 8
·36 + 9
·92 + 15
·112 + 20
·76 + 24
·56 + 30
·28 + 30
·96 + 39
·4 = 9536
4. Все аi
· 0; Все bj
· 0

5.Условием не отрицательности удовлетворяют.
Хij
· 0

Все Хij должны быть не отрицательными (для компьютера).










15

Приложенные файлы

  • doc 15561419
    Размер файла: 405 kB Загрузок: 1

Добавить комментарий