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

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

Рис. 4.2

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

Рис. 4.3

Рассмотрим на примере использование данной надстройки. Решим с ее помощью задачу производственного планирования – выпуск продуктов А, В, С, Д из трёх типов ресурсов, математическая модель которой имеет вид:

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, как показано на рис. 4.4.

Рис. 4.4. Шаблон оформления задачи

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

Рис. 4.5. Исходные данные задачи

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

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

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

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

Рис. 4.6. Вызов функции СУММПРОИЗВ

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

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

Рис. 4.7

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

Рис. 4.8

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

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

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

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

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

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

Рис. 4.9

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

Рис. 4.10

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

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

Рис. 4.11

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

Рис. 4.12. Установка параметров

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

Рис. 4.13. Окно результата решения

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

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

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

Рис. 4.15. Сообщение об ошибке

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

Рис. 4.16

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

Рис. 4.17

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

Рис. 4.18

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

Рис. 4.19

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

Рис. 4.20

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

Рис. 4.21

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

Рис. 4.22

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

Рис. 4.23

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

Отчеты выглядят следующим образом:

1. Отчет по результатам

Рис. 4.24

2. Отчет по устойчивости

Рис. 4.25

3. Отчет по пределам

Рис. 4.26

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

а) Допустим, математическая модель имеет следующие ограничения:

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

при

2X₁ + X₂ + 0,5Х₃ + 4Х₄ ≥ 2400 ограничения

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

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

X₁, _{2, 3, 4} ≥ 0

В итоге имеем следующие результаты по отчетам:
Отчет по результатам

Рис. 4.27

Дата добавления: 2014-12-29