Построение математической модели

Критерий оптимальности задается функцией:

F=2x₁₁+5x₁₂+6x₁₃+3x₁₄+7x₂₁+2x₂₂+x₂₃+8x₂₄+2x₃₁+4x₃₂+5x₃₃+x₃₄+8x₄₁+6x₄₂+5x₄₃+8x₄₄ min

Система ограничений записывается как:

x₁₁+x₁₂+x₁₃+x₁₄=1

x₂₁+x₂₂+x₂₃+x₂₄=1

x₃₁+x₃₂+x₃₃+x₃₄=1

x₄₁+x₄₂+x₄₃+x₄₄=1

x₁₁+x₂₁+x₃₁+x₄₁=1

x₁₂+x₂₂+x₃₂+x₄₂=1

x₁₃+x₂₃+x₃₃+x₄₃=1

x₁₄+x₂₄+x₃₄+x₄₄=1

Решение с использованием ms excel

1. Откройте новый рабочий лист и внесите на него исходные данные так, как это показано на Рис.3. 1.

Рис.3. 1. Исходные данные задачи о назначениях

2. Подготовьте таблицу для решения задачи, задайте целевую функцию и ограничения (см. Рис.3. 1).

• В диапазоне (B12:E15) будет получено решение (таблица назначений).

• В ячейку С17 записывается формула для вычисления значений целевой функции - =СУММПРОИЗВ(B4:E7; B12:E15).

• В ячейки B19-B26 записываются левые части ограничений (3.2) и (3.3).

• В ячейки D19-D26 записываются правые части ограничений (3.2) и (3.3).

Рис.3. 2. Целевая функция и ограничения

3. Вызовите подпрограмму Сервис-Поиск решения. В открывшемся окне «Поиск решения» задайте:

• В поле Установить целевую ячейку задайте адрес C17.

• Установите переключатель в положение Минимальному значению.

• В поле Изменяя ячейки задайте адрес диапазона таблицы назначений B12:E15.

• В окне Ограничения удалите все ограничения, оставшиеся от решения предыдущей задачи (выделите и удалите по одному с помощью кнопки Удалить). После этого добавляйте ограничения по одному с помощью кнопки Добавить.

  • Нажмите кнопку Добавить.

  • В открывшемся окне «Добавление ограничения» в поле Ссылка на ячейку задайте ячейку, содержащую формулу левой части ограничения (например, B19). В списке выберите знак «=». В поле Ограничение задайте ячейку, содержащую правую часть ограничения (например, D19).

  • Нажмите кнопку ОК.

• Для задания допустимых значений переменной x, в окне «Добавление ограничения» в поле Ссылка на ячейку задайте диапазон B12:E15, выберите из списка условий «Целое».

• После добавления всех ограничений нажмите кнопку Параметры и перейдите к окну «Параметры поиска решения». Установите флажок в поле Неотрицательные значения (для выполнения ограничения (3.3)). Установите флажок в поле Линейная модель.

• Нажмите кнопку ОК в окне «Параметры поиска решения».

• Нажмите кнопку Выполнить в окне «Поиск решения».

• Результаты работы подпрограммы Поиск решения отображаются в окне «Результаты поиска решения». Сообщение «Решение найдено. Все ограничения и условия оптимальности выполнены» свидетельствует о корректном завершении задачи. В этом случае нажмите кнопку ОК и проанализируйте полученный в диапазоне (B12:E15) оптимальный план назначений. Если появляется сообщение «Поиск не может найти подходящего значения», нажмите кнопку Отмена и проверьте правильность исходных данных и ограничений.

Рис.3. 3. Описание математической модели в окне «Поиск решения»

4. Проанализируйте полученное решение (см. Рис.3. 4).

• Оптимальный план назначений содержится в диапазоне B12:E15.

• Все ограничения условиям выполнения работ выполнены.

• Минимальные затраты составляют 10.

Рис.3. 4. Оптимальное решение задачи о назначениях