Методы оптимизации ПИ 202з Тихонов РГР v2

II курс ПИ202(з) Тихонов Е. методы оптимизации РГР.

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

Факультет информатики и робототехники

Кафедра АСУ

РАСЧЕТНО − ГРАФИЧЕСКАЯ РАБОТА

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

Вариант №19

Выполнил : ст. гр. ПИ 202 з Тихонов Е.В.

Проверил : асс . каф . АСУ Кондратьева О.В.

УФА -2014

Задание для расчетно-графической работы

Задача №№ 1-3.

Три предприятия данного экономического района могут производить некоторую

однородную продукцию в количествах соответственно равных А1, А2, А3 единиц . Эта

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

равных В1, В2, В3, В4, В5 единиц . Затраты связанные с производством и доставкой

единицы продукции , задаются матрицей С.

Составить план прикрепления потребителей к поставщикам , решить задачу

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

оптимальным .

Вариант	A1	A2	A3	B1	B2	B3	B4	B5
19	120	60	70	40	60	20	80	50

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

симплекс-методом) методами.

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

Вариант	A1	A2	A3	Б1	Б2	Б3	Запасы1	Запасы2	Запасы3	С1	С2
19	15	22,5	25	7,5	30	20	575	525	625	45	50

Задача №5.

Пусть функция полезности имеет вид U. Даны коэффициенты а0, а1, а2, бюджет

B и цены P1, P2, P3. Составить математическую модель и найти оптимальный набор

благ и его полезность с помощью метода множителей Лагранжа .

Вариант	U	a0	a1	a2	B	P1	P2	P3
19	a0x1a1 x2a2	1,25	0,61	0,46	320	21	26	-

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

Задача№1-3

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

2. Ограничения наложены в задаче на ресурсы производителей(А1-А3) и потребности потребителей (B1-B5)при этом должна быть перевезена вся произведенная продукция и должны быть удовлетворены все потребители. Проверим на корректность задачу – сумма произведенной продукции должна быть равна сумме требуемой:

120+60+70 = 40+60+20+80+50

250 = 250

Задача корректна.

Обозначим каждую искомую величину за X_ij , получится таблица:

	B1 40	B2 60	B3 20	B4 80	B5 50
A1 120	X11	X12	X13	X14	X15
A2 60	X21	X22	X23	X24	X25
A3 70	X31	X32	X33	X34	X35

Выявляются ограничения (требования):

X11+x12+x13+x14+x15=120

X21+x22+x23+x24+x25=60

X31+x32+x33+x34+x35=70

X11+x21+x31=40

X12+x22+x32=60

X13+x23+x33=20

X14+x24+x34=80

X15+x25+x35=50

3. Цель задачи состоит в нахождении оптимального плана, то есть нахождение значений перевезенной продукции от каждого производителя до каждого потребителя с суммарной наименьшей затратностью C:

	B1 40	B2 60	B3 20	B4 80	B5 50
A1 120	X11 7	X12 9	X13 10	X14 6	X15 5
A2 60	X21 12	X22 8	X23 6	X24 5	X25 13
A3 70	X31 6	X32 2	X33 8	X34 2	X35 4

То есть целевая функция выглядит так:

Исходный план выглядит так:

	B1 40	B2 60	B3 20	B4 80	B5 50
A1 120	X11 7	X12 9	X13 10	X14 6	X15 5
A2 60	X21 12	X22 8	X23 6	X24 5	X25 13
A3 70	X31 6	X32 2	X33 8	X34 2	X35 4

Где

A1 120

у производителя «А1» имеется 120 единиц нераспределенных ресурсов.

B1 40

у потребителя B1 имеется 40 ед. неудовлетворенной потребности в ресурсе.

X11 7

наименование маршрута Х11 от производителя А1 до потребителя B1; кол-во ед. ресурсов определены – в данный момент в плане пусто, поскольку план еще не начали заполнять – ячейка считается незаполненной; стоимость перевозки по маршруту X11 составляет 7 ед.

Заполним план методом северо-западного угла.

Шаг1. Самая северо-западная незанятая ячейка это X₁₁. По данному методу можно раскидывать первоначально как ресурсы, так и удовлетворять потребности; что первично? – я решаю сначала удовлетворять потребности. Удовлетворим полностью потребность B1 ресурсами из поставщика A1:

	B1 40 0	B2 60	B3 20	B4 80	B5 50
A1 120 80	X11 40 7	X12 9	X13 10	X14 6	X15 5
A2 60	X21 0 12	X22 8	X23 6	X24 5	X25 13
A3 70	X31 0 6	X32 2	X33 8	X34 2	X35 4

Требования B1 обнуляются, а ресурс А1 уменьшается с 120 до 80, поскольку 40 ед. увезли в B1. Значения X₂₁ X₃₁ обнуляем, поскольку определили все требования B1 были удовлетворены переменной X₁₁. Таблица после первого шага имеет вид:

	B1 0	B2 60	B3 20	B4 80	B5 50
A1 80	X11 40 7	X12 9	X13 10	X14 6	X15 5
A2 60	X21 0 12	X22 8	X23 6	X24 5	X25 13
A3 70	X31 0 6	X32 2	X33 8	X34 2	X35 4

Шаг2. Самая северо-западная незанятная ячейка это X₁₂. Удовлетворяем все потребности B2:

	B1 0	B2 60 0	B3 20	B4 80	B5 50
A1 80 20	X11 40 7	X12 60 9	X13 10	X14 6	X15 5
A2 60	X21 0 12	X22 0 8	X23 6	X24 5	X25 13
A3 70	X31 0 6	X32 0 2	X33 8	X34 2	X35 4

Потребность B2 удовлетворена и обнулена, ресурс А1 равный 80 ед. израсходует 60 ед и останется А1 = 20 ед. Значения X₂₂ X₃₂ обнуляем, поскольку определили все требования B1 были удовлетворены переменной X₁₁. По результату второго шага план имеет вид:

	B1 0	B2 0	B3 20	B4 80	B5 50
A1 20	X11 40 7	X12 60 9	X13 10	X14 6	X15 5
A2 60	X21 0 12	X22 0 8	X23 6	X24 5	X25 13
A3 70	X31 0 6	X32 0 2	X33 8	X34 2	X35 4

Шаг3. Самая северо-западная незанятая ячейка это X₁₄. Удовлетворяем потребности B3:

	B1 0	B2 0	B3 20 0	B4 80	B5 50
A1 20 0	X11 40 7	X12 60 9	X13 20 10	X14 0 6	X15 0 5
A2 60	X21 0 12	X22 0 8	X23 0 6	X24 5	X25 13
A3 70	X31 0 6	X32 0 2	X33 0 8	X34 2	X35 4

Потребность B3 удовлетворена и обнулена значением X₁₃ полностью. Значения X₂₃ и X₃₃ обнулены, поскольку уже не требуется ресурса для B3. Ресурс А1 исчерпан, поэтому значения X₁₄ и X₁₅ обнуляем. Таблица после третьего шага имеет вид:

	B1 0	B2 0	B3 0	B4 80	B5 50
A1 0	X11 40 7	X12 60 9	X13 20 10	X14 0 6	X15 0 5
A2 60	X21 0 12	X22 0 8	X23 0 6	X24 5	X25 13
A3 70	X31 0 6	X32 0 2	X33 0 8	X34 2	X35 4

Шаг4. Самая северо-западная незанятая ячейка это X₂₄. Удовлетворяем потребности B3: нам не хватит ресурсов из А2 (60 ед) для удовлетворения B3 (80шт), поэтому возьмем все с ресурса А2 (60 ед.) и 20 ед. из А3:

	B1 0	B2 0	B3 0	B4 80 0	B5 50
A1 0	X11 40 7	X12 60 9	X13 20 10	X14 0 6	X15 0 5
A2 60 0	X21 0 12	X22 0 8	X23 0 6	X24 60 5	X25 0 13
A3 70 50	X31 0 6	X32 0 2	X33 0 8	X34 20 2	X35 4

Потребность B4 удовлетворена, Поставщик А2 истощён, поставщик А3 имеет на 20 ед. ресурсов меньше. После выполнения четвертого шага таблица имеет вид:

	B1 0	B2 0	B3 0	B4 0	B5 50
A1 0	X11 40 7	X12 60 9	X13 20 10	X14 0 6	X15 0 5
A2 0	X21 0 12	X22 0 8	X23 0 6	X24 60 5	X25 0 13
A3 50	X31 0 6	X32 0 2	X33 0 8	X34 20 2	X35 4

Шаг5. Самая северо-западная незанятая ячейка это X₃₅. Удовлетворяем потребности B5 остатками с поставщика A3:

	B1 0	B2 0	B3 0	B4 0	B5 50 0
A1 0	X11 40 7	X12 60 9	X13 20 10	X14 0 6	X15 0 5
A2 0	X21 0 12	X22 0 8	X23 0 6	X24 60 5	X25 0 13
A3 50 0	X31 0 6	X32 0 2	X33 0 8	X34 20 2	X35 50 4

Потребность B5 удовлетворена, поставщик A3 истощен. Все потребности удовлетворены, все поставщики истощены. Задача решена.

	B1 0	B2 0	B3 0	B4 0	B5 0
A1 0	X11 40 7	X12 60 9	X13 20 10	X14 0 6	X15 0 5
A2 0	X21 0 12	X22 0 8	X23 0 6	X24 60 5	X25 0 13
A3 0	X31 0 6	X32 0 2	X33 0 8	X34 20 2	X35 50 4

Вычислим получившиеся затраты по данному плану:

ед

Метод минимального элемента.

Шаг1. Находим самый дешевый маршрут. Их тут два (X₃₂ и X₃₄), я выбираю первый попавшийся – это X₃₂. Теперь по этому маршруту я заполняю по максимому кол-во перевозимых ед:

	B1 40	B2 60 0	B3 20	B4 80	B5 50
A1 120	X11 7	X12 0 9	X13 10	X14 6	X15 5
A2 60	X21 12	X22 0 8	X23 6	X24 5	X25 13
A3 70 10	X31 6	X32 60 2	X33 8	X34 2	X35 4

Потребность B2 полностью удовлетворена, поэтому X12 и X22 обнулены. У производителя осталось нераспределено 10 ед. ресурсов. Таблица после шага №1 имеет вид: