Последовательность выполнения

1. Оформить исходные данные на листе1:

 

 

· В ячейки B2 и C2 вводятся коэффициенты при переменных из ограничения баланс сырья. В ячейки В3 и C3 вводятся коэффициенты при переменных из ограничения баланс времени. В ячейки B4 и C4 вводятся коэффициенты целевой функции.

· В ячейку D2 вводится формула расчета левой части ограничения «баланс сырья»: Вставка – Функция – Математические – СУММПРОИЗВ -ОК – массив1-В2: С2-массив2 –В5: С5 – ОК.

В ячейку Е2 вводится числовое значение правой части ограничения (константы), т.е. 1700.

· В ячейку D3 вводится формула расчета левой части ограничения «баланс времени». В ячейку Е3 вводится числовое значение константы ограничения, т.е. 160.

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

2. Сервис – Надстройки – Поиск решения

3. Сервис – Поиск решения. В диалоговом окне «Поиск решения»

· в поле Установить целевую поставим ячейку D4

Ø выполняем щелчок левой клавишей мыши в поле

Ø выполняем щелчок левой клавишей мыши по ячейке D4

Ø проверяем правильность заполнения

· включаем по максимальному значению, что соответствует выбранной целевой функции(max прибыли).

· в поле Изменяя ячейки указываем ячейки, соответствующие значению переменных по решению, т.е. в нашем случае В5: C5. Это выполняется методом выделения блока ячеек В5: С5 путем протягивания левой клавишей мыши.

4. В поле Ограничения:

· нажать кнопку Добавить

· в поле Ссылка на ячейку вводим D2

· Выбрать тип < =

· В поле Ограничение вводим Е2

· Нажать кнопку Добавить

· Аналогично повторить для ограничения «баланс времени» ОК

5. Параметры. Выполнить настройку. ОК

6. Нажать кнопку Выполнить

7. В диалоговом окне Результаты поиска решения

· включить сохранить найденное решение

· тип отчета - Результаты. ОК.

8. Результаты решения выводятся на лист Отчет по результатам. На листе1(исходные данные) в строке 5 (значения по решению) выводятся значения соответствующих переменных, в ячейке D4 - значение целевой функции, в ячейках D2 и D3 – значения выполнения ограничения. Так баланс сырья задавался < =1700, выполняется ограничение как =1700. Аналогично по балансу времени.

Задача 2

Последовательность выполнения:

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

2. Дать команду Сервис-Поиск решения.

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

Если в задаче все ограничения одного типа, то их можно задать выделением группы ячеек.

 

4. В диалоговом окне Поиск решения нажать кнопку Выполнить.

Замечание. В различных версиях MS Excel (95, 97, 2000, XP) наименования управляющих элементов диалоговых окон Поиск решения и Параметры поиска решения могут быть неодинаковыми, но расположение и назначение их остаются неизменными.

5. В диалоговом окне Результаты поиска решения установить переключатель Сохранить найденное решение, выбрать все 3 типа отчетов, щелкая по их названиям левой кнопкой мыши, и нажать кнопку ОК.

6. Проанализировать полученные отчеты .

Результаты решения выводятся на лист 1 (Отчет по результатам.)

 

Лист 1 Отчет по результатам

 

На листе 2 (исходные данные) в строке 8 (значения по решению) выводятся значения соответствующих переменных, в ячейке E8 - значение целевой функции, в ячейках E3: E6 – значения выполнения ограничений.

Лист 2 Исходные данные

 

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

Если принять во внимание вышеизложенные факторы, то модель может быть расширена за счет них ограничениями по:

· трудовым затратам;

· упаковке в расчете на сутки;

· учету возможных каналов реализации;

· степени задержки поставки молока партнером в пределах (суток, недели).

Контрольные вопросы

1. Для чего используется процедура «Поиск решения»?

2. Какие задачи могут решаться «Поиском решения» наиболее эффективно?

3. В виде каких отчетов оформляются результаты оптимизации при использовании средства «Поиск решения»?

4. Из скольких зон состоит таблица для процедуры «Поиск решения»?

5. Как ввести векторное ограничение при использовании поиска решения?

6. Как выбирать начальные значения переменных при решении модели с помощью средства «Поиск решения»?

Лабораторная работа № 14 «Метод искусственного базиса или
М- метод»

Теоретическая часть

Правила перехода к М-задаче от исходной (основной) задачи

1. В ограничения типа меньше или равно (£ ) вводим неотрицательные дополнительные переменные с коэффициентом плюс единица.

2. В ограничения типа больше или равно (³ ) вводим неотрицательные дополнительные переменные с коэффициентом минус единица.

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

4. В целевую функцию дополнительные переменные вводятся с нулевым коэффициентом.

5. В целевую функцию искусственные базисные переменные при решении задачи на максимум целевой функции вводятся с коэффициентом " -М", а при решении задачи на минимум целевой функции вводятся с коэффициентом " +М", где " М" большое положительное число: М ³ 10⁴.

Алгоритм М-метода решения задачи на максимум целевой функции

1. М-задача записывается в симплексную таблицу.

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

3. Подсчитываются оценки по формуле оценок:

, j=0, 1,..., n

и записываются в последнюю строку таблицы.

4. Проверка решения на оптимальность по признаку: решение задачи на максимум целевой функции оптимально, если все оценки при переменных неотрицательные. Если критерий выполняется, то переход к пункту 12, если нет, то переход к пункту 5.

5. Разрешающий столбец выбирается по минимальной отрицательной оценке.

6. Если в разрешающем столбце есть хотя бы один положительный элемент, то переходим к пункту 7. Если нет, то целевая функция М-задачи не ограничена, переход к пункту 14.

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

8. По наименьшему симплексному отношению находится разрешающая строка.

9. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.

10. Пересчет таблицы по общим правилам и заполнение новой таблицы.

11. Переход к пункту 4.

12. Запись оптимального решения М-задачи и значения целевой функции.

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

14. Если целевая функция М-задачи не ограничена, то необходимо в М-задачу ввести дополнительное ограничение:

х₁+ х₂+…+ х_n£ М и решить новую М-задачу. Если после решения новая М-задача

а) будет иметь оптимальное решение с нулевыми искусственными переменными, то целевая функция основной задачи не ограничена;

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

Пример выполнения работы

Пример

 

Каноническая форма записи:

 

В системе ограничений канонической формы нет единичного базиса. Необходимо ввести в 1-е и 3-е ограничения искусственные базисные переменные и перейти к М-задаче. Получим:

 

 

 

№1	Cj							-M	-M	7-2M	со сс
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
-M	Y1					-1
	X5		2								4 i*
-M	Y2
Z	Dj	-23M	-4M - - 4 j*	-3M -2	-2M --1	M				-31M -7	X

 

№2	Cj							-M	-M	7-2M	со C0
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
-M	Y1			1/2	1/2	-1	-1/2			9/2
	X1			1/2	1/2		1/2			13/2
-M	Y2			1/2	-1/2		-3/2			5/2	6 i*
Z	Dj	-7М+16	0	-М j*		M	2М+2			-5М+19	X

 

№3	Cj							-M	-M	7-2M	со C0
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
-M	Y1				1	-1			-1		1 i*
	X1								-1
	Х2				-1		-3				-
	Dj	-М+16	0		-М+1 j*	М	-М+2		2М		X

 

№4	Cj							-M	-M	7-2M
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
	Х3					-1			-1
	X1							-1
	Х2					-1	-2
Z	Dj		0					М-1	М+1	2М+17

Так как все оценки при переменных неотрицательные, то решение М-задачи оптимальное. Так как все оценки при свободных переменных не равны нулю, то оптимальное решение единственное. Х_м^*(0, 7, 1, 0, 0, 0, 0), max Z_м = 15.

Искусственные переменные в оптимальном решении равны нулю, поэтому их можно отбросить и получить соответствующее оптимальное решение основной задачи: Х^*(0, 7, 1, 0, 0), max Z = 15. Базисная переменная Х₁ равна нулю, поэтому оптимальное решение – вырожденное.

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

Поделиться: