Решение ЗЛП на основе Ms Excel

Решим задачу, математическая модель которой имеет вид:

max f ()=7, 5X₁+3X₂+6X₃+12X₄ (целевая функция)

> при

2X₁+X₂+0, 5Х₃+4Х₄ ≤ 2400

3X₁+6X₃+Х₄ ≤ 2000

X_{1, 2, 3, 4} ≥ 0

Таблица 2.10

				7, 5
S	i
						0, 5
											-
		∆	-7, 5	-3	-6	-12
				0, 5	0, 25	0, 125		0, 25
			2, 5	-0, 25	5, 875		-0, 25				238, 3
			-1, 5		-4, 5
				0, 4468	0, 2553			0, 2553		-0, 021	570, 213	2233, 3
			-0, 2766	5, 1277			0, 1277		-0, 511	485, 106	94, 606
			0, 4255	-0, 0426			-0, 043		0, 1702	238, 298	-
			0, 4149	-0, 1915			2, 8085		0, 766
				0, 4606				0, 249	-0, 0498	0, 0041	546, 058
			-0, 0539				0, 0249	0, 19502	-0, 1	94, 6058
			0, 4232				-0, 041	0, 0083	0, 166	242, 324
			0, 4046				2, 8133	0, 03734	0, 7469	8290, 46

Решим данную ЗЛП с помощью Ms Excel

Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис»:

Если в версии Excel, установленной на вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения».

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

max f ()=7, 5X₁+3X₂+6X₃+12X₄ (целевая функция)

при

2X₁+X₂+0, 5Х₃+4Х₄ ≤ 2400

X₁+5X₂+3Х₃ ≤ 1200

3X₁+6X₃+Х₄ ≤ 2000

X_{1, 2, 3, 4} ≥ 0

Составим шаблон в редакторе Excel, как показано на шаблоне 1.

Шаблон 1.

Теперь занесем в данную задачу числовую информацию (шаблон 2)

Шаблон 2. Исходные данные задачи

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

Ячейки С4 – F4 называются в Excel изменяемыми (в нашей модели это неизвестные переменные), т.е., изменяя их, Поиск решения будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения)

Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение 7, 5X₁+3X₂+6X₃+12X₄, можно рассматривать как произведение вектора (7, 5, 3, 6, 12) на вектор (Х₁, Х₂, X₃, X₄).

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку H5 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это С5: F5) и ячеек, в которые в результате решения будут помещены значения Х₁, Х₂, X₃, X₄ (ячейки С4: F4) (шаблон 3).

Шаблон 3. Вызов функции СУММПРОИЗВ

Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение 2X₁+X₂+0, 5Х₃+4Х₄ (для первого ограничения 2X₁+X₂+0, 5Х₃+4Х₄≤ 2400) будем рассматривать как произведение вектора коэффициентов (2, 1, 0, 5, 4) и вектора переменных (Х₁, Х₂, X₃, X₄).

В ячейке, отведенной для формулы левой части первого ограничения (G9), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов С9: F9 и адрес значений переменных C4: F4 (шаблон 4).

Шаблон 4.

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

Шаблон 5.

К моменту вызова сервиса «Поиск решения» на рабочем столе с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.

В меню Сервис выбираем Поиск решения. В появившемся окне задаем следующую информацию:

а) в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции H5

б) «флажок» устанавливаем на вариант «максимальному значению», т.к. в данном случае, целевая функция дохода подлежит максимизации;

в) в качестве изменяемых ячеек заносится адрес строки значений переменных С4: F4;

г) справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения (Шаблон 6).

Шаблон 6.

д) в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения G9, выбирается требуемый знак неравенства (в нашем случае, < =), в поле «Ограничение» заносится ссылка на правую часть ограничения I9 (Шаблон 7):

Шаблон 7.

е) аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».

Таким образом, окно «Поиск решения с занесенной информацией выглядит следующим образом (Шаблон 8):

Шаблон 8.

Далее необходимо нажать кнопку Параметры, установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача является ЗЛП, а ограничение 6) требует неотрицательности значений (Шаблон 9).

Шаблон 9. Установка параметров

Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата поиска решения (Шаблон 10).

Шаблон 10. Окно результата решения

Если в результате всех действий получено окно с сообщением «Решение найдено», то Вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи (Шаблон 11)

Шаблон 11. Результат применения «Поиска решения»

Если в результате решения задачи выдано окно с сообщением о невозможности нахождения решения (Шаблон 12), это означает, что при оформлении задачи была допущена ошибка (не заполнены формулы для ограничений, неправильно установлен «флажок», максимизации/минимизации и т.д.).

Шаблон 12. Сообщение об ошибке

В окне «Поиск решения» имеется кнопка «Параметры»:

Установим флажок «Показывать результаты итераций», после нажимаем «ОК»:

Затем нажать кнопку «Выполнить»:

Ms Excel выдаст следующее окно:

На рабочем листе будут показаны результаты первой итерации:

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

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

При следующим нажатии кнопки «Продолжить», программа выдает окно «Результаты поиска решения», где необходимо сохранить найденное решение и выбрать тип отчета: