Найдем цикл перераспределения груза для этой клетки

1. Найдем цикл перераспределения груза для этой клетки.

– объем перепоставки.

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план (таб. 3) является невырожденным.

	31		52		17		20		45
35		5		4		3		1		0	0
			18		17
40		2		3		5		8		0	–1
	31		9
40		6		8		7		10		0	2
									40
50		5		6		7		2		0	2
			25				20		5
	3		4		3		0		–2		Таб.3

Транспортные затраты, соответствующие опорному плану:

 (ден. ед.).

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

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

, , ,, , , , , .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: .

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

Наименьшие транспортные затраты .

Ответ: ; оптимальный план распределения поставок расположен в таб. 3.

Задания для самостоятельной работы.

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

 

а)

б)

Решение оптимизационных задач с помощью Excel

При решении оптимизационных экономических задач необходимо пройти через следующие этапы:

·          Составить математическую модель экономической задачи;

·          Решить полученную экстремальную математическую задачу;

·          Дать экономическую интерпретацию ответу.

Рассмотрим прохождение этих этапов на примере задачи об использовании ресурсов.

Пример. Для изготовления изделий двух видов А и В на заводе используют сырье четырех типов (І, ІІ, ІІІ, IV). Для выпуска изделия А необходимо 2 единицы сырья І типа; 1 ед. сырья ІІ типа; 2 ед. сырья ІІІ типа; 1 ед. сырья IV типа. Для изготовления изделия В требуется 3 единицы сырья І типа; 1 ед. сырья ІІ типа; 1 ед. сырья ІІІ типа. Запасы сырья составляют: І типа – 21 ед., ІІ типа – 8 ед., ІІІ типа – 12 ед., IV типа – 5 ед. Выпуск одного изделия типа А приносит 3 грн. прибыли, а одного изделия типа В – 2 грн. прибыли. Составить план производства, обеспечивающий наибольшую прибыль.

Решение.

·          Составление математической модели.

Вопрос задачи, сформулированный в виде «составить план производства, обеспечивающий наибольшую прибыль», означает, что необходимо определить, какое количество изделий А и В нужно производить (для достижения наибольшей прибыли).

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

– количество изделий А, планируемое к выпуску;

– количество изделий В, планируемое к выпуску;

Z (целевая функция задачи) по своему экономическому смыслу – это прибыль. (Т.к. из условия задачи мы видим, что слово «наибольшая», связанное с экстремумом, соответствует прибыли).

Получим:

 – математическая модель задачи.

·          Решение полученной экстремальной задачи:

Для решения задачи воспользуемся возможностями Microsoft Excel.

§   Откройте Microsoft Excel.

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

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

В ячейку А4 введите обозначение целевой функции Z=.

§   В ячейку В4 введите формулу вычисления целевой функции из математической модели задачи

(), подставляя вместо  и , соответствующие им значения из ячеек А2 и В2. (Вспомните, что введение формулы начинается со знака =)

После нажатия кнопки Enter на экране монитора должно быть следующее. (Продумайте, как изменится картинка, если ввести иные значения  и , к примеру, не 1, а 2. А теперь поэкспериментируйте. Оправдался ваш прогноз?)

В ячейки А5 и В5 введите соответственно слова: А5 – Ограничение, В5 – Правая часть ограничения.

§   В ячейку А6 введите формулу вычисления левой части первого ограничения , подставляя вместо  и , соответствующие им значения из ячеек А2 и В2.

§   В ячейку В6 введите свободный член первого ограничения – 21. После нажатия кнопки Enter на экране монитора должно быть следующее.

§   Аналогично в ячейку А7 введите формулу вычисления левой части второго ограничения , а в В7 его свободный член – 8; в ячейку А8 введите формулу вычисления левой части третьего ограничения , а в В8 его свободный член – 12; в ячейку А9 введите формулу вычисления левой части четвертого ограничения , а в В9 его свободный член – 5;

§   После нажатия кнопки Enter на экране монитора должно быть следующее.

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

§   В меню Сервис выберите команду Поиск решения (именно она является инструментом для поиска решений задач оптимизации)

§   В этой команде вам будет предложено установить целевую ячейку. Именно слово «целевую» поможет вам в дальнейшем вспомнить, о чем идет речь. Конечно же, о значении целевой функции. Введите это значение, щелкнув левой кнопкой мышки на ячейке В4 (содержащей в данном случае числовое значение целевой функции). Получите:

§   Т.к. в данной задаче функция Z исследуется на максимум, то оставляем Равной: • максимальному значению.

Если решаем задачу на минимум, то нужно поставить метку • перед словами минимальному значению.

§   Далее нажмите на стрелку, расположенную в правой части пространства ячейки Изменяя ячейки:, в результате чего на экране должно появиться следующее

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

Т.е. заполненная ячейка должна принять вид:

§   После этого заполняют пространство ячейки Ограничения: Для чего нужно щелкнуть по кнопке Добавить, в результате чего на экране появится новое окно:

В Ссылка на ячейку: введите номер ячейки, содержащей левую часть ограничения (в данном случае для первого ограничения – это ячейка А6).

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

В Ограничение: введите номер ячейки, содержащей свободный член ограничения (в данном случае для первого ограничения – это ячейка В6).

Т.о. перед вами на экране должна быть следующая картинка:

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

§   Но после того, как все ограничения системы введены, еще рано нажимать ОК, т. к. в математической модели имеется условие неотрицательности переменных (), а в описании задачи для компьютера оно еще не упоминалось.

Поэтому после введения последнего ограничения вновь нажмите кнопку Добавить и в Ссылка на ячейку: введите номер ячейки, содержащей числовое значение ; выберите знак >=; а в Ограничение: введите 0.

Еще раз нажмите Добавить и аналогичным образом создайте условие неотрицательности для .

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

Появилось? Если ДА, то нажимайте Выполнить.

И согласитесь на то, чтобы Сохранить найденное решение. Т.е. в появившемся окне нажмите ОК.

§   Обратите внимание на то, какие теперь значения принимают ,  и Z.

 = 4;  = 4; Z = 20 – Это и есть найденное оптимальное решение задачи () и соответствующее

экстремальное значение целевой функции ().

Математически задача решена. Осталось дать экономическую

интерпретацию полученному.

·          Дадим экономическую интерпретацию ответу.

Для достижения наибольшей прибыли 20 грн. необходимо производить 4 изделия А и 4 изделия В.

Литература

1.   Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування. – К.: КНЕУ, 2001.

2.   Исследование операций в экономике/ Под ред. проф. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 2000.

3.   Конюховский П.В. Математические методы исследования операций в экономике: учебное пособие. – СПб. – Москва – Харьков – Минск, 2005.

4.   Кулян В.Р. и др. Математическое программирование. – К.: МАУП, 2005.

5.   Таха, Хемди. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2001.