Методы оптимальных решений (6 задач) ОГУ

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

Задание 1

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

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

Время обработки и цена изделий

Изделия Цена за единицу Время обработки на станке, ч

№1 №2 №3 №4

А 6 2 4 3 1

В 4 0,25 2 1 4

Возможное время использования станков, ч 45 100 300 50

В каком соотношении следует производить изделия А и В, чтобы получить максимальную прибыль?

Задание 2

Составить задачу, двойственную задаче задания 1.

Задание 3

На трех заводах производится однородная продукции в количестве 800, 300, 500 единиц. Четырем потребителям требуется соответственно 450, 250, 350, 550 единиц продукции. Расходы cij по перевозке единицы продукции с i-го завода j-му потребителю известны (см. Транспортную таблицу).

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

Транспортная таблица

Заводы Потребители Запас продукции, ед.

В1 В2 В3 В4

А1 3 8 5 4 800

А2 9 3 7 6 300

А3 4 8 7 5 500

Потребности в продукции, ед. 450 250 350 550  

1) Записать математическую модель транспортной задачи.

2) Найти опорное решение методом наименьшей стоимости. Опорное решение проверить методом потенциалов, получить оптимальное решение.

Целочисленное программирование

Решите задачу коммивояжера

Коммивояжер должен объехать 5 городов. Выезжая из одного города, коммивояжер должен объехать все города и вернуться в исходный город. В каждый город он может только 1 раз въехать и только 1 раз выехать. При известных расстояниях между городами (км) составить экономико-математическую модель задачи и решить задачу методом ветвей и границ.

Расстояние между городами

  1 2 3 4 5

1 350 200 450 300

2 350 180 370 525

3 200 180 380 230

4 450 370 380 320

5 300 525 230 320

Нелинейное программирование

Методом множителей Лагранжа решить задачу: 

Пусть у потребителя имеются финансовые средства в объеме S = 820 условных единиц, которые он готов потратить на приобретение двух видов продуктов. Известно, что цена единицы продукции первого вида – Р1 = 32, цена единицы продукции второго вида – Р2 = 45. 

Найти, какое количество продукции каждого вида будет приобретать потребитель располагая средствами в размере S = 820, чтобы максимизировать свою полезность 

U = x^(2/3)*x^(1/3) , где

 x1 - количество продукта первого вида, которое готов приобрести потребитель; 

х2 – количество продукта второго вида, которое готов приобрести потребитель.

Многокритериальная задача

Четыре нефтеперерабатывающих завода с ежедневной производительностью 4, 6, 10 и 10 млн. тонн бензина снабжают пять бензохранилищ, ежедневная потребность которых составляет 7, 7, 7, 7 и 2 млн. тонн бензина соответственно. Стоимость транспортировки составляет 0,3 руб. за 1000 тонн на один км между заводами и хранилищами. Расстояние между заводами и хранилищами в кмприведено в следующей таблице.

Заводы Хранилища Объем

1 2 3 4 5

1 160 300 170 100 160 4

2 300 270 260 90 230 6

3 130 40 220 30 100 10

4 30 100 50 40 240 10

Вместимость

хранилища 7 7 7 7 2 30

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

Заводы Хранилища

1 2 3 4 5

1 3 5 1 8 2

2 4 5 3 7 2

3 4 9 3 6 4

4 1 2 1 5 7

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

Критерий 1. Минимизация стоимости транспортировки бензина.

Критерий 2. Минимизация максимального времени, затрачиваемого на транспортировку бензина из всех заводов во все хранилища.

Содержание

Линейное программирование 4

Задание 1 4

Задание 2 16

Задание 3 19

Целочисленное программирование 25

Нелинейное программирование 31

Многокритериальная задача 33

Список использованной литературы 39