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

Содержание

 

Задача 1           3

Задача 2           8

Задача 3           12

Список использованных источников      14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1

 

Предприятию необходимо перевезти со склада по железной дороге продукцию трех видов: продукции первого вида не более 624 изделий, продукции второго вида не более 360 изделий и продукции третьего вида не более 220 изделий. Для этой перевозки подразделение железной дороги может выделить специально оборудованные вагоны двух типов A и B. Для полной загрузки вагона в него следует помещать продукцию всех трех видов. При этом в вагон типа A входят 14 изделий первого вида, 12 изделий второго вида и 8 изделий третьего вида. В вагон типа B входят 8 изделий первого вида, 4 изделия второго вида и 2 изделия третьего вида. Экономия от перевозки в вагоне типа A составляет 15 руб., в вагоне типа B – 4 руб.

Требуется:

1. Сформулировать экономико-математическую модель исходной экономической задачи.
2. Определить сколько вагонов каждого типа следует выделить для перевозки, чтобы суммарная экономия от перевозки была наибольшей? Решить задачу линейного программирования графическим методом.
3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.

 

Решение:

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

Переменные: х1 – число вагонов типа А; х2 – число вагонов типа В.

Запишем целевую функцию:

 

Ограничения:

 

2. Первое ограничение (по продукции первого вида)  имеет  вид  . Прямая проходит через точки (44; 1) и (0; 78). Второе ограничение  (по продукции второго вида)  имеет  вид  . Прямая проходит через точки (0; 90) и (30; 0). Третье ограничение (по продукции третьего вида)  имеет  вид  . Прямая проходит через точки (27; 2) и (0;100).

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

На рисунке заштрихована область допустимых решений (ОДР). Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции:

 

Соединяем точку с началом координат О (0; 0) и получаем вектор-градиент.

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

 

 

Далее будем передвигать линию уровня до ее выхода из ОДР. При максимизации целевой функции движение линии уровня осуществляется в направлении градиента. В крайней угловой точке достигается максимум целевой функции. Для нахождения координат этой точки решаем систему из двух уравнений прямых, дающих в пересечении точку максимума:

 

 

 

 

Таким образом, целевая функция принимает при ; минимальное значение, равное

 

Для получения максимальной экономии (420 руб.) необходимо выделить для перевозки 20 вагонов типа А () и 30 вагонов типа В ().

3. сформулируем двойственную задачу.

Переменные:

у1 – двойственная оценка продукции первого вида,

у2 – двойственная оценка продукции второго вида,

у3 – двойственная оценка продукции третьего вида.

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

 

Ограничения:

 

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

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

 

Тогда

 

 

 

Подставим оптимальные значения вектора в полученные выражения:

 

 

 

или

     так как , то    ,

 

 

Воспользуемся следующим соотношением второй теоремы двойственности:

 

В нашей задаче ; , поэтому первое и второе ограничения двойственной задачи обращаются в равенства:

 

Решая полученную систему уравнений находим и :

 

 

 

 

Теневые цены продукции первого, второго, третьего видов соответственно равны

 

Проверим выполнение первой теоремы двойственности:

 

 

Это означает, что оптимальный план двойственной задачи определен верно.

 

Задача 2

 

Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1, А2 и А3 находится груз в количестве соответственно 250, 180, 270 т. В пункты В1, В2, В3, В4 и В5 требуется доставить соответственно 160, 120, 100, 150 и 170 т груза.

Расстояния между пунктами поставки и пунктами потребления приведены в следующей таблице:

 

Пункты поставки	Пункты потребления
	В1	В2	В3	В4	В5
А1	14	11	9	13	18
А2	6	5	14	4	14
А3	7	19	11	6	13

 

Требуется:

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

 

Решение:

Суммарный запас равен

 

Суммарная потребность составляет

 

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

Найдем исходный план методом наименьшего элемента:

Выбираем клетку с наименьшим тарифом. Это клетка А2В4 с тарифом . Так как , то записываем в клетку 150, а потребителя В4 исключаем из рассмотрения. У поставщика А2 осталось еще тонн товара.

Выбираем клетку с наименьшим тарифом. Это клетка А2В2 с тарифом . Так как , то записываем в клетку 30, а поставщика А2 исключаем из рассмотрения. Потребителю В2 требуется еще тонн товара.

Выбираем клетку с наименьшим тарифом. Это клетка А3В1 с тарифом . Так как , то записываем в клетку 160, а потребителя В1 исключаем из рассмотрения. Поставщик А3 располагает тоннами товара.

Выбираем клетку с наименьшим тарифом. Это клетка А1В3 с тарифом . Так как , то записываем в клетку 100, а потребителя В3 исключаем из рассмотрения. Поставщик А1 располагает тоннами товара.

Выбираем клетку с наименьшим тарифом. Это клетка А1В2 с тарифом . Так как , то записываем в клетку 90, а потребителя В2 исключаем из рассмотрения. Поставщик А1 располагает тоннами товара.

Выбираем клетку с наименьшим тарифом. Это клетка А3В5 с тарифом . Так как , то записываем в клетку 110, а поставщика А3 исключаем из рассмотрения. Потребителю В5 требуется еще тонн товара.

Незаполненной осталась клетка А1В5 с тарифом . Направляем потребителю В5 60 тонн товара от поставщика А1. Таблица заполнена.

Число базисных клеток совпадает с числом заполненных клеток.

Затраты на данный план

 

700
			14			11			9			13			18
		–			90			100			–			60
	2									3
			6			5			14			4			14
		–			30			–			150			–
	0						11						2
			7			19			11			6			13
		160			–			–			–			110
				13			7			1
																6270

 

Решим задачу методом потенциалов:

1. Для базисных переменных потенциалы строк ui и столбцов vj удовлетворяют следующему условию

 

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

Остальные потенциалы найдем, решая систему уравнений

 

2. Определим характеристики для свободных неизвестных:

 

и запишем их в левом нижнем углу свободных клеток.

 

 

 

 

 

 

 

 

Так как все характеристики , то план оптимален и .

Получили оптимальный план перевозок. Суммарные транспортные расходы на реализацию плана минимальны и равны

Товар первого поставщика необходимо направить второму, третьему и пятому потребителям в размере 90, 100 и 60 тонн соответственно. Товар второго поставщика направить второму и четвертому потребителям в размере 30 и 150 тонн соответственно. Товар третьего поставщика – первому и пятому потребителям в размере 160 и110 тонн соответственно.

 

 

 

 

 

Задание 3

 

Цветочный магазин использует 600 глиняных цветочных горшков в месяц. Годовая стоимость хранения одного горшка составляет 1 руб. 50 коп. Стоимость одного заказа – 150 руб. Магазин работает 365 дней в году. Доставка заказа осуществляется в течение одного дня.

Определите экономичный объем заказа, годовые расходы на хранение запасов, период поставок и точку заказа.

 

Решение:

Проведем необходимые вычисления по формулам модели наиболее экономичного размера партии (модели Уилсона).

Время (количество рабочих дней в году):

 

Спрос за время :

 

 

Затраты на хранение одного горшка в течение дней:

 

 

Затраты на осуществление одного заказа:

 

 

Стоимость хранения одного горшка в день:

 

 

Оптимальный объем заказа:

 

Период поставок:

 

 

Число партий за время :

 

 

Среднесуточный спрос:

 

 

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

 

 

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

 

 

Для минимизации расходов на оформление заказа, доставку и хранение товара необходимо:

а) в течение года сделать 6 заказов, в каждом из которых поставить 1200 горшков;

б) принять период поставок равным 61 дню;

в) новый заказ делать при уровне запаса в 20 горшков;

г) совокупные издержки заказа и хранения составят 1 800 руб.

 

 

 

 

Список использованных источников

 

1. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие. – М.: Вузовский учебник, 2012.
2. Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование. Учебное пособие. – М.: ВЗФЭИ, Вузовский учебник, 2012.
3. Федосеев В.В., Гармаш А.Н., Орлова И.В. Экономико-математические методы и прикладные модели: учебник для бакалавров. – 3-е изд., перераб. и доп. – М.: Издательство Юрайт, 2012.