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

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

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ИЖЕВСКАЯ ГОСУДАРСТВЕННАЯ СЕЛЬСКОХОЗЯЙСТВЕННАЯ АКАДЕМИЯ»

Контрольная работа по предмету:

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

Проверил М.В.Миронова

Выполнил Прокофьева Е.А.

Ижевск 2022



Вариант 9.

Блок №1 Методы построения транспортной задачи

Построение опорного плана транспортной задачи

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:

	1	…	n
1		…
…	…	…	…	…
m		…
		…		=

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

сумма перевозок в каждой строке равна запасу в данной строке;

сумма перевозок в каждом столбце равна соответствующему спросу

Опорный план транспортной задачи содержит не более отличных от нуля перевозок.

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

Метод северо-западного угла

Рассмотрим «северо-западный угол» незаполненной таблицы, т.е. клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая:

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

Если , то, т.е. спрос первого потребителя полностью удовлетворен и поэтому, а остаток продукта в первом пункте производства равен.

В случае из рассмотрения можно исключить и поставщика и потребителя. Однако при этом план получается вырожденным, поэтому считается, что выбывает только поставщик, а спрос потребителя остается неудовлетворенным и равным нулю.

После этого рассматриваем северо-западный угол оставшейся незаполненной части таблицы и повторяем те же действия. В результате через шагов получим опорный план.

Пример

Найти опорный план транспортной задачи.

	1	2	3
1	15	20		35	20	0	0
2		0	30	30	30	30
	15	20	30	=
	0	20	30
	0	0	30
	0	0	0

В таблице, обведенной снизу и справа двойной чертой, указаны объемы перевозок полученные методом северо-западного угла. При этом небазисные нулевые перевозки не проставлены. Справа и внизу таблицы содержатся объемы возможных запасов и спросов. В число базисных перевозок вошла перевозка , так как на предыдущем шаге и по п.3 метода считается выбывшим только поставщик, а неудовлетворенный спрос второго потребителя равен.

Метод минимальной стоимости

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

Пример

Опорный план, построенный по методу минимальной стоимости.

	1	2	3
1	9	57	301	35	5	5	5
2	152	153	8	30	30	15	0
	15	20	30	=
	15	20	0
	0	20	0
	0	5	0

Метод потенциалов

Цикломв транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке цикла совершает поворот на. Знаком «+» отмечают те вершины, в которых перевозки увеличиваются, а знаком «-« - те вершины цикла, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым, а стоимость плана может меняться.

Ценой цикланазывается изменение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком «+», а в отрицательных со знаком «-«.

Идея метода потенциалов состоит в следующем [1,3]. Для любой свободной клетки транспортной таблицы всегда существует единственный цикл, положительная вершина которого лежит в этой свободной клетке, а все остальные в базисных. Если цена такого цикла отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза, которое можно переместить определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить больше единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план найден.

Для нахождения циклов с отрицательной ценой вводится система платежей , и определяются величины, называемые «псевдостоимостями» перевозок единицы груза из пунктаiв пунктj. При этом цена цикла пересчета для каждой свободной клетки равна, если платежи , определять из условия:

для всех базисных клеток (i,j).

Вычислительная схема метода потенциалов

Шаг 1.Строим опорный план (методом северо-западного угла или методом минимальной стоимости) сбазисными клетками.

Шаг 2.Определяем платежи, из условий:для всех базисных клеток (ij). Один из платежей (в строке или столбце которого максимальное число базисных клеток) полагаем равным нулю.

Шаг 3.Считаем псевдостоимости для всех свободных клеток. Еслидля всех клеток, то план оптимален. Вычисляем значение целевой функциина этом плане и исследование прекращаем.

Шаг 4.Если есть свободная клетка, для которой, то улучшаем план, перебрасывая перевозки по циклу этой свободной клетки.

Шаг 5.Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.

Пример

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



	1	2	3
1	3	8	2	35
2	7	4	8	30
	15	20	30	=

Опорный план этой задачи найден методом северо-западного угла.

Приписываем к таблице строку для платежей , и столбец для платежей. Псевдостоимости записываем в левом углу клетки, а стоимости - в правом.

Из условий в базисных клетках получаем систему уравнений:

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

	1	2	3
1	15 3	[-] 20 8	12[+] 2	35	0
2	-1 7	[+] 0 4	[-] 30 8	30	-4
	15	20	30	=
	3	8	12

Стоимость перевозок по плану этой таблицы

Так как клетка (1,3) имеет отрицательную цену , то план не является оптимальным. Строим для клетки (1,3) цикл. Цена цикла. По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1,2) не стали отрицательными). При этом стоимость плана изменяется на. Для нового плана вычисляем новые значения платежей и псевдостоимостей:

	1	2	3
1	[-]15 3	-2 8	[+] 20 2	35	0
2	9 [+] 7	20 4	[-] 10 8	30	6
	15	20	30	=
	3	-2	2

Стоимость перевозок по плану этой таблицы

Полученная таблица имеет клетку (2,1) с отрицательной ценой . По циклу этой клетки переносим 10 единиц груза, при этом стоимость плана уменьшается наединиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:

	1	2	3
1	5 3	0 8	30 2	35	0
2	10 7	20 4	5 8	30	4
	15	20	30	=
	3	0	2

Стоимость перевозок по плану этой таблицы

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

Блок №2 Управление запасами

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

- товарно-материальные запасы (сырье и материалы);

- незавершенное производство;

- готовую продукцию на складе.

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

Цель системы управления запасами- обеспечение бесперебойного производства продукции в нужном количестве и в установленные сроки и достижение на основе этого полной реализации выпуска при минимальных расходах на содержание запасов.

Анализ состояния и эффективности управления запасами проводится по следующим показателям:

- Удельный вес величины запасов в общей сумме оборотных активов;

- Оборачиваемость запасов;

- Продолжительность 1 оборота запасов;

- Величина расходов, связанных с содержанием запасов;

- Сезонность.

Эффективное управление товарно-материальными запасами (ТМЗ) позволяет:

- уменьшить производственные потери из-за дефицита материалов;

- ускорить оборачиваемость этой категории оборотных средств;

- свести к минимуму излишки товарно-материальных запасов, которые увеличивают стоимость операций и "замораживают" дефицитные денежные средства; транспортный вычислительный стоимость перевозка

- снизить риск старения и порчи товаров;

- снизить затраты на хранение товарно-материальных запасов.

Для управления запасами используется метод АВС. Согласно данному методу запасы сырья и материалов делятся на 3 категории по степени важности отдельных видов в зависимости от их удельной стоимости:

- Категория А - включает ограниченное количество наиболее ценных видов ресурсов, которые требуют постоянного и скрупулезного учета и контроля (возможно даже ежедневного). Для этих ресурсов обязателен расчет оптимального размера заказа.

- Категория В - составлена из тех видов ТМЗ, которые в меньшей степени важны для предприятия и которые оцениваются и проверяются при ежемесячной инвентаризации, для ТМЗ этой категории, как и категории А, приемлемы методики определения оптимального размера заказа.

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

При оптимальном размере заказа общие издержки управления запасами являются минимальными. Последние состоят из издержек выполнения заказа и издержек хранения запасов.

С одной стороны, предприятию выгодно завозить товары как можно более высокими партиями. Чем выше размер партии поставки товаров, тем ниже совокупный размер операционных затрат по размещению заказов в определенном периоде (оформлению заказов, доставке заказанных товаров на предприятие и их приемке).



Сумма совокупных операционных затрат по размещению заказов при этом определяется по следующей формуле:

ОЗрз =	Р	Х Срз
РПП

где ОЗрз-- сумма совокупных операционных затрат по размещению заказов;

Р-- объем товарооборота предприятия в рассматриваемом периоде;

РПП -- средний размер одной партии поставки товаров;

Ср3 -- средняя стоимость размещения одного заказа.

Из приведенной формулы видно, что при неизменном объеме товарооборота предприятия и средней стоимости размещения одного заказа общая сумма операционных затрат по размещению заказов минимизируется с ростом среднего размера одной партии поставки товаров. С другой стороны, высокий размер одной партии поставки товаров вызывает соответствующий рост операционных затрат по хранению товаров на предприятии, так как при этом увеличивается средний размер запаса в днях оборота (период их хранения).

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

ОЗхр =	РПП	Х СХ

где ОЗХР -- сумма операционных затрат по хранению запасов товаров на предприятии;

РПП -- средний размер одной партии поставки товаров;

Сх -- стоимость хранения единицы товара в рассматриваемом периоде.

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

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

Математически Модель ЕОQ выражается следующей принципиальной формулой:

ЗАДАЧА НАХОЖДЕНИЕ ОПТИМАЛЬНОГО ПЛАНА

9. Чаеразвесочная фабрика выпускает чай сорта А и В, смешивая 3 ингредиента: индийский, грузинский и краснодарский чай.

Ингредиенты	Нормы расхода (т/т)	Объем запасов (т)
	А	В
Индийский чай Грузинский чай Краснодарский чай	0,5 0,2 0,3	0,2 0,6 0,2	600 870 430
Прибыль от реализации 1 т продукции	320	290

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

Решение

х1 - количество чая А,

х2 - количество чая В.

Ограничения: 0,5х1+ 0,2х2 ? 600 - Индийский чай;

0,2х1+ 0,6х2 ? 870 - Грузинский чай;

0,3х1+ 0,2х2 ? 430 - Краснодарский чай.

х1? 0, х2 ?0 - условие неотрицательности.

Функция цели: f (x) = 320 х1 + 290 х2 > MAX.

1. 0,5х1+ 0,2х2 = 600 2. 0,2х1+ 0,6х2 = 870 3. 0,3х1+ 0,2х2 = 430

х1 = 0, х2 = 3000; х1 = 0, х2 = 1450; х1 = 0, х2 = 2150;

х1 =1200, х2 = 0. х1 = 4350, х2 = 0. х1 = 1433, х2 = 0.

Точка МАХ - пересечение прямых 2 и 3.

0,2х1+ 0,6х2 = 870

0,3х1+ 0,2х2 = 430

0,2х1+ 0,6х2 = 870

- 0,9х1+ 0,6 х2 = - 1290

-0,7 х1 = -420

х1= 600 (т).

х2=1250 (т).

Точка МАХ (600;1250).

f (x) = 320*600+290*1250 = 192 000+362500 = 554 500 (руб.).



Ответ: Чаеразвесочная фабрика получит максимальную прибыль в размере 554 500 рублей при производстве 600 т. Чая А и 1250 т. чая В.



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

1. Бережная Е.В. Математические методы моделирования экономических систем: Учеб. пособие для вузов/ Е.В. Бережная, В.И. Бережной. - М.: Финансы и статистика, 2003. - 364с.: табл.

2. Лихтенштейн В.Е. Экономико-математическое моделирование: Учеб. пособие/ В.Е. Лихтенштейн, В.И. Павлов; Ин-т экономики, управления и права. Фак. управления. - М.: ПРИОР, 2001. - 448с.: ил, табл.

3. Хазанова Л.Э. Математические методы в экономике: Учеб. пособие/ Л.Э.Хазанова. - 2-е изд., испр. и перераб. - М.: БЕК, 2002. - 131с.: табл., ил.

4. Шуликовская В.В. Теория игр. - Ижевск: ООО Информационно-издательский центр «Бон Анца», 2009. - 304с.

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

...