Методы оптимизации при принятии реш-ий.

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

Группы методов:

1. Линейное программирование – позволяет найти самый точный рез-ат, применяется к большинству производственных задач. Способы реш-я:

   • Сис-ма линейных ур-ей.

   • Метод цепных подстановок.

   • Симплекс метод.

2. Целочисленное программирование – искомый рез-ат целое число. Методы:

• Простой перебор.

• Пошаговый перебор.

• Симплекс метод.

3. Теория графов – сетевые графики, кот позволяют найти оптимальные маршруты движ-я, как правило с экономией затрат, времени и денег. Методы:

• Графические.

• Аналитические.

Типовые задачи оптимизации:

1. Линейного программирования

   • Производственная задача.

   • Двойственная задача.

   • Планирование номенклатуры и объемов выпуска.

   • Задача о диете.

2. Целочисленного программирования:

• Задача о выборе оборудования.

• Задача о ранце.

1. Теории графов:

• Задача коммивояжера.

• Задача о кротчайшем пути.

• Задача о максимальном потоке.

• Транспортная задача.

16.05.12Г продолжение Производственная задача.

Производятся столы (y) и стулья (х), 400 ед материала, 450 человеко-часов живого труда. На произв-во 1 стула тратиться 5 ед материала и 10 чел-часов. На произв-во 1 стола тратиться 20 ед материала и 15 чел-часов. Прибыли от 1 стула 45 ден ед, от 1 стола 80 ден ед.

Задача оптимизации имеет вид: (требуется максимизировать прибыль произведя такой выпуск продукции, чтобы все рес-сы были израсходованы, т.е. найти оптимал выпуск).

45х + 80y -> мах

Задаем ограничения:

1. 5х + 20y ≤ 400

2. 10х + 15y ≤ 450

3. х, y ≥ 0 – условия не отрицательности

5х + 20y ≤ 400

10х + 15y ≤ 450

Ответ: х = 24, y = 14

Подставляет данное знач-е в целевую ф-ю:

45*24 + 80*14 = 2200 ден ед

Ответ: оптимал выпуск составит 24 стула и 14 столов, при этом исп весь материал и все труд рес-сы, а прибыль = 2200 ден ед

Двойственная задача.

В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, вместо мах ищется мин и наоборот.

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

W1 – стоимость ед рес-ов (материалы).

W2 – чел\ч

400W1 + 450W2 -> мин

Стул 5W1 + 10W2 ≤ 45

Стол 20W1 + 15W2 ≤ 80

W1, W2 ≥ 0

W1 = 1, W2 = 4 ден ед

400*1 + 450*4 = 2200 ден ед

Ответ: аналогично (см выше).

Планирование номенклатуры и объемов выпуска.

Данные о производственных мощностях

	Кухни	Кофеварки	Самовары
Штамповка	20 000	30 000	1 2 000
Отделка	30 000	12 000	1 0 000
Сборка	20 000 (N1)	12 000 (N2)	8 000 (N3)
Объем выпуска, шт	Х1	Х2	Х3
Удельная прибыль, ден ед.	15	12	14

1 станок

Штамповка, отделка проводится на одном и том же оборудовании, сборка – на отдел участках. Какую номенклатуру выпуска выбрать?

Производственная мощность = 100%

15х1 + 12х2 + 14х3 -> мах

Штамповка 1. х1\200 + х2\300 + х3\120 100

Отделка 2. х1\300 + х2\120 + х3\100 100

Сб\кух 3. х1\200 ≤ 100

4. х2\120 ≤ 100

5. х3\80 ≤ 100

6. х1, х2, х3 ≥ 100

1. х1\200 + х2\300 + х3\120 = 100

2. х1\300 + х2\120 + х3\100 = 100

3. х1\200 = 100

4. х2\120 = 100

5. х3\80 = 100

6. х1, х2, х3 = 100

При реш-и этой сис-мы получим х1 = 6 000 ед, х3 = 8 000, х2 = отрицательное число и оно убирается из ограничений и из оптимал выпуска.

Вывод: в оптимал плане кофеварки выпускать не выгодно, оптимал выпуск сост 6 000 кухонь и 8 000 самоваров.