Задачи по исследованию операций с решениями

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

Контрольная работа

по дисциплине «Методы оптимальных решений»

Выполнила:

Дедова О.П.

Екатеринбург 2016

Задача 1) Для изготовления сапог и ботинок используется сырье трех видов. Запасы сырья известны и равны соответственно: 350, 392 и 408 т. Количество сырья каждого вида, необходимое для производства одной партии сапог, соответственно равны: 14, 14 и 6 т. Для одной партии ботинок: 5 , 8 и 12 т. Прибыль от реализации сапог составляет 10 тыс. $ , от ботинок - 5 тыс. $ на одну партию. Составить оптимальный план, обеспечивающий наибольшую прибыль производству:

а) записать математическую модель;

б) решить задачу графическим методом.

Решение:

Построение математической модели

X1 -изделие первого вида

X2 -изделие второго вида

14Х1+5Х2? 350

14Х1+8Х2? 392

6Х1+12Х2?408

x1 ? 0, x2 ? 0

Целевая функция:

10x1 + 5x2 > max

б) решим задачу графическим методом;

Необходимо найти максимальное значение целевой функции F = 10x1+5x2 > max, при системе ограничений:

14x1+5x2?350,

14x1+8x2?392,

6x1+12x2?408,

x1 ? 0,

x2 ? 0,

Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Шаг №2. Границы области допустимых решений.

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

Обозначим границы области многоугольника решений.

Шаг №3. Рассмотрим целевую функцию задачи F = 10x1+5x2 > max.

Построим прямую, отвечающую значению функции F = 0: F = 10x1+5x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (10; 5). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

14x1+5x2=350

14x1+8x2=392

Решив систему уравнений, получим: x1 = 20, x2 = 14

Откуда найдем максимальное значение целевой функции:

F(X) = 10*20 + 5*14 = 270

Задача 2) На трёх станциях ( Ai ) сосредоточен однородный груз, который следует перевезти в четыре пункта назначения ( Bj ), имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.

Решить транспортную задачу методом потенциалов.

Решение:

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 180 + 220 + 100 = 500

?b = 120 + 80 + 175 + 125 = 500

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

Этап I. Поиск первого опорного плана.

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

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

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

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

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

Значение целевой функции для этого опорного плана равно:

F(x) = 7*55 + 4*125 + 7*120 + 10*100 + 2*80 + 18*20 = 3245

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

u2 + v3 = 10; 7 + u2 = 10; u2 = 3

u2 + v1 = 7; 3 + v1 = 7; v1 = 4

u3 + v3 = 18; 7 + u3 = 18; u3 = 11

u3 + v2 = 2; 11 + v2 = 2; v2 = -9

u1 + v4 = 4; 0 + v4 = 4; v4 = 4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

11 + 4 > 9; ?34 = 11 + 4 - 9 = 6

Выбираем максимальную оценку свободной клетки (3;4): 9

Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (3,4 > 3,3 > 1,3 > 1,4).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

u2 + v3 = 10; 7 + u2 = 10; u2 = 3

u2 + v1 = 7; 3 + v1 = 7; v1 = 4

u1 + v4 = 4; 0 + v4 = 4; v4 = 4

u3 + v4 = 9; 4 + u3 = 9; u3 = 5

u3 + v2 = 2; 5 + v2 = 2; v2 = -3

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ? cij.

Минимальные затраты составят:

F(x) = 7*75 + 4*105 + 7*120 + 10*100 + 2*80 + 9*20 = 3125

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 3-й магазин (75), в 4-й магазин (105)

Из 2-го склада необходимо груз направить в 1-й магазин (120), в 3-й магазин (100)

Из 3-го склада необходимо груз направить в 2-й магазин (80), в 4-й магазин (20)

Список литературы

1. АстафуровВ.Г., Колодникова Н. - Компьютерное учебное пособие, раздел "Анализ на чувствительность с помощью двойственной задачи", Томск-2002.

2. Алесинская Т.В. - Задачи по исследованию операций с решениями.

3. Ашманов С. А. Линейное программирование. -- М.: Наука. Главная редакция физико-математической литературы, 1981.-- 340 с.

4. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов.-- М.: Высш. шк., 1986.-- 319 с

5. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. -- М.: ИНФРА-М, 2003. -- 444 с. -- (Серия "Высшее образование").

6. Булдаев А.С. Прямые методы решения задачи линейного программирования. - Иркутск, 2000. - 25 с.

7. Булдаев А.С. Двойственные методы решения задачи линейного программирования. - Иркутск, 2000. - 28 с.

8. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. -- 2-е изд., перераб. и доп. -- М.: Финансы и статистика, 2006. - 432 с: ил.

Размещено на Allbest.ru