МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ ЗАДАНИЙ

Задача о выпуске продукции при ограниченных ресурсах.

Необходимый теоретический материал для выполнения есть в пособии В.Л.Никитенкова, А.А.Холопова [1], а также в любой литературе по линейному программированию.

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

При постановке задачи линейного программирования (ЗЛП) обязательно указать смысл вводимых переменных (например, так: " Пусть x₁ означаетобъем…" ).

Масштабы на осях при решении ЗЛП графическим методом должен быть одинаковыми.

Необходимо четко указать формальное решение рассматриваемой ЗЛП, например, так: " Ответ ЗЛП:

"

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

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

 

Классическая транспортная задача.

Необходимый теоретический материал для решения транспортной задачи также есть в пособии [1], смотри также [2-4].

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

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

При оформлении решения необходимо выписать только последовательность таблиц с необходимыми элементами: потенциалами, значками '+' '-', значения стоимостей очередных планов перевозок. Все остальные выкладки (расчеты потенциалов и др.) необязательны.

Ответ состоит из последней таблицы (с потенциалами и ценами!! ), числа С_min– стоимости оптимального плана и графа оптимального плана

со значениями перевозок на дугах.

 

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

О задачах об аренде оборудования можно прочитать в [1], также в учебниках по исследованию операций. К сожалению, эта литература стала труднодоступной, поэтому постановка задачи и два метода ее решения приводятся в разделе 3.

Задачу достаточно решить одним из предложенных способов (при этом студентам-заочникам следует знать оба метода).

Рекомендуется табличный метод как более простой. Решение при этом собственно будет состоять из таблицы исходных стоимостей, дополненной столбцом потенциалов y_i , набора выделенных клеток (в каждой строке таблицы должна быть хотя одна выделенная клетка! ) и выписанных из таблицы по выделенным клеткам ответов задачи – оптимальных планов аренды. Планы следует писать как в виде путей, то есть возрастающей последовательности номеров, так и в виде набора сроков очередной аренды. Искать планы аренды методом перебора не разрешается!

 

ПРИМЕР РЕШЕНИЯ КЛАССИЧЕСКОЙ ТРАНСПОРТНОЙ ЗАДАЧИ.

Замечание. Это пример решения транспортной задачи одним студентом – заочником. Решение излишне подробное.Достаточно было изображать по одной таблице с потенциалами на каждом шаге.

Кроме того, при изображении оптимального графа перевозок фиктивного потребителя (№ 5) изображать не нужно было, а нужно было указать остатки товара у 3-го склада (остаток равен 145) А.А.Холопов

Исходные данные (запасы, потребности и цены)

Поставщик	Потребитель	Запасы
В1	В2	В3	В4
A1
A2
A3
Потребность

 

Транспортная задача является открытой, так как сумма запасов груза 850=350+200+300 больше суммы потребностей 705=170+140+200+195 на 145 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B₅. Будет 3 склада и 5 потребителей.

Находим начальный базисный план (он содержит 3+5 –1=7 заполненных клеток).

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

Начальный план

		Потребности
		170	140	200	195	145
Запасы	Поставщик	Потребитель
В1	В2	В3	В4	В5
350	A1
200	A2
300	A3

 

Стоимость перевозок = 14*146+…+ 39*195 = 17870.

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

Й этап.

Полагая потенциал U₁ = 0, определяем остальные потенциалы из соотношения

 

,

просматривая все занятые клетки.

Потенциалы:

 

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

.

Значения оценок

	В1	В2	В3	В4	В5
A1
A2		-7			-10
A3					-15

 

Выделенные оценки не являются оптимальными, а именно:

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

Строим для этой клетки цикл, помечая клетки цикла знаками " плюс" и " минус".

План грузоперевозок

Поставщик	Потребитель	Потенциалы Ui
В1	В2	В3	В4	В5
A1					+				–
A2
A3					–				+
Потенциалы Vj

 

Перемещаем по циклу груз величиной в 105 единиц. В результате перемещения по циклу получим новый план.

Новый план грузоперевозок

Поставщик	Потребитель	Запасы
В1	В2	В3	В4	В5
A1
A2
A3
Потребность

 

Стоимость перевозок при этом = 16295.

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

 

Этап.

Полагая потенциал U₁ = 0, определяем остальные потенциалы из соотношения

,

просматривая все занятые клетки.

Потенциалы:

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

.

Значения оценок

	В1	В2	В3	В4	В5
A1				-11
A2		-7		-13	-10
A3

 

Выделенные оценки не являются оптимальными, а именно:

Максимальной по модулю отрицательной оценкой является , т.к..

Строим для этой клетки цикл, помечая клетки цикла знаками " плюс" и " минус".

План грузоперевозок

Поставщик	Потребитель	Потенциалы Ui
В1		В3	В4	В5
A1					+				–
A2					–		+
A3							–		+
Потенциалы Vj

 

Перемещаем по циклу груз величиной в 30 единиц. В результате перемещения по циклу получим новый план.

Новый план грузоперевозок

Поставщик	Потребитель	Запасы
В1	В2	В3	В4	В5
A1
A2
A3
Потребность

 

Стоимость перевозок при этом = 15905.

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

 

Этап.

Полагая потенциал U₁ = 0, определяем остальные потенциалы из соотношения

 

,

 

просматривая все занятые клетки.

Потенциалы:

 

 

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

.

 

Значения оценок

	В1	В2	В3	В4	В5
A1				-11
A2
A3

 

Выделенные оценки не являются оптимальными, а именно:

 

Наиболее неоптимальной оценкой, является оценка .

Строим для этой клетки цикл, помечая клетки цикла знаками " плюс" и " минус".

 

План грузоперевозок

Поставщик	Потребитель	Потенциалы Ui
В1		В3	В4	В5
A1							+		–
A2											-3
A3							–		+
Потенциалы Vj

 

Перемещаем по циклу груз величиной в 10 единиц. В результате перемещения по циклу получим новый план.

 

Новый план грузоперевозок

Поставщик	Потребитель	Запасы
В1	В2	В3	В4	В5
A1
A2
A3
Потребность

 

Стоимость перевозок при этом = 15795.

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

 

Этап.

Полагая потенциал U₁ = 0, определяем остальные потенциалы из соотношения

 

,

просматривая все занятые клетки.

Потенциалы:

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

.

Значения оценок

	В1	В2	В3	В4	В5
A1
A2		-5
A3

 

Выделенные оценки не являются оптимальными, а именно:

 

 

Наиболее неоптимальной оценкой, является оценка .

Строим для этой клетки цикл, помечая клетки цикла знаками " плюс" и " минус".

 

План грузоперевозок

Поставщик	Потребитель	Запасы
В1	В2	В3	В4	В5
A1			–				+
A2			+				–
A3
Потенциалы Vj					-11

 

Перемещаем по циклу груз величиной в 30 единиц. В результате перемещения по циклу получим новый план.

Новый план грузоперевозок

Поставщик	Потребитель	Потенциалы Ui
В1		В3	В4	В5
A1
A2		-3
A3
Потребность

 

Стоимость перевозок при этом = 15645.

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

 

Этап.

Полагая потенциал U₁ = 0, определяем остальные потенциалы из соотношения

 

,

 

просматривая все занятые клетки.

Потенциалы:

 

 

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

.

Значения оценок

	В1	В2	В3	В4	В5
A1
A2
A3

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

 

Оптимальный план грузоперевозок

Поставщик

Потребитель

Запасы

В1

В2

В3

В4

В5

A1

A2

A3

Потребность

-11

 

Стоимость перевозок при этом = 15645.

 

145 единиц груза из хранилища A₃ осталось нераспределенным.

Графически оптимальный план грузоперевозок можно представить в виде графа со значения перевозок на дугах (Рис. 1).

Рис. 1. Граф оптимального плана грузоперевозок.

⇐ Предыдущая123Следующая ⇒

Поделиться:

Популярное:

1. I. ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ
2. III. ТЕМАТИКА КОНТРОЛЬНЫХ РАБОТ
3. V. Методические указания к выполнению контрольной работы.
4. В чем специфика заданий на классификацию?
5. Выполнению домашней контрольной работы
6. Две разновидности заданий-задач: что общего? Каковы различия?
7. ДЛЯ ВЫПОЛНЕНИЯ контрольных работ
8. Документация баз и контрольных постов ГДЗС
9. Е. ТОВАРНЫЕ ЗНАКИ, ФИРМЕННЫЕ НАИМЕНОВАНИЯ И ГЕОГРАФИЧЕСКИЕ УКАЗАНИЯ
10. И выполнению дипломных работ
11. И выполнению контрольной работы
12. И методические указания к изучению раздела