Технология решения задач линейного программирования с помощью поиска решений

 

Поиск решения – это надстройка Excel, которая позволяет решать оптимизационные задачи. Если в меню Данные отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Кнопа «Office» - Параметры Excel – Надстройки – Поиск решения – Перейти и активизируйте надстройку Поиск решения.

Для решения задачи необходимо:

1. Создать форму для ввода условий задачи.

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

3. Ввести исходные данные.

4. Ввести зависимость для целевой функции.

5. Ввести зависимости для ограничений.

6. Указать назначение целевой функции (установить целевую ячейку).

7. Ввести ограничения.

8. Ввести параметры для решения ЗЛП.

 

Рассмотрим на примере задачи 2.1.2 технологию решения Задачи оптимального использования ресурсов.

1. Для задачи 2.1.2 подготовим форму для ввода условий ( см. рис.1).

 

Рис.1. Введена форма для ввода данных.

 

2. В нашей задаче оптимальные значения вектора Х=(Х1, Х2, Х3, Х4) будут помещены в ячейках В3:Е3, оптимальное значение целевой функции – в ячейке F4.

3. Введём исходные данные в созданную форму. Получим результат, показанный на рис. 2.

 

Рис.2. Данные введены.

 

4. Введём зависимость для целевой функции:

§ Курсор в F4

§ Нажать кнопку Мастер функций fx в строке формул.

5. На экране появится диалоговое окно Мастер функций шаг 1 из 2.

§ Выбрать категорию Математические.

§ Выбрать функцию СУММПРОИЗВ.

§ В массив 1 ввести B$3:E$3.

§ В массив 2 ввести B4:E4.

§ Готово. На экране: в F4 введена функция, как показано на рис. 3.

5. Введём зависимость для левых частей ограничений:

§ Курсор в F4.

§ Копировать в буфер.

§ Выделить блок F7:F9.

§ Вставить из буфера.

На этом ввод зависимостей закончен.

Рис.3. Вводится функция для вычисления целевой функции.

 

Запуск Поиска решения

 

После выбора команд Данные Поиск решения появится диалоговое окно Поиск решения.

В диалоговом окне Поиск решения есть три основных параметра:

§ Установить целевую ячейку

§ Изменяя ячейки

§ Ограничения

Сначала нужно заполнить поле «Установить целевую ячейку». Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить конкретное значение.

Второй важный параметр средства Поиск решения – это параметр Изменяя ячейки. Изменяемые ячейки – это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования: они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.

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

6. Назначение целевой функции (установить целевую ячейку).

§ Курсор в поле «Установить целевую ячейку».

§ Ввести адрес $F$4.

§ Ввести направление целевой функции: Максимальному значению.

Ввести адреса искомых переменных:

§ Курсор в поле «Изменяя ячейки».

§ Ввести адреса B$3:E$3.

7. Ввод ограничений.

§ Курсор в поле «Добавить» . Появится диалоговое окно Добавление ограничения (рис. 4).

Рис. 4. Ввод правых и левых частей ограничений.

 

§ В поле «Ссылка на ячейку» ввести адрес $F$7.

§ Ввести знак ограничения £.

§ Курсор в правое окно.

§ Ввести адрес $H$7.

§ Добавить. На экране опять диалоговое окно Добавление ограничения.

§ Ввести остальные ограничения.

§ После ввода последнего ограничения ввести Ок.

На экране появится диалоговое окно Поиск решения с введёнными условиями (рис.5).

Рис. 5. Введены все условия для решения задачи.

 

8. Ввод параметров для решения ЗЛП (рис. 6).

· Открыть окно Параметры поиска решения.

· Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.

 

Рис. 6. Ввод параметров.

 

§ Установить флажок Неотрицательные значения.

§ ОК. (На экране диалоговое окно Поиска решения).

§ Выполнить. (На экране диалоговое окно Результаты поиска решения – рис.7).

 

Рис. 7. Решение найдено.

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы труд и оборудование будут использованы полностью, а из 480 кг пряжи (ресурс сырьё) будет использовано 280 кг.

 

Создание отчёта по результатам поиска решения

Excel позволяет представить результаты поиска решения в форме отчёта. Существует три типа таких отчётов:

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

Устойчивость (Sensitivity). Отчёт, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.

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

 

 

В отчёте по результатам содержатся оптимальные значения переменных X1, X2, X3, X4, которые соответственно равны 0, 30, 10, 0, значение целевой функции – 150, а также левые части ограничений.

 

Транспортная задача

 

Транспортная задача является одной из наиболее распространённых задач линейного программирования и находит широкое практическое приложение.

Постановка транспортной задачи. Некоторый однородный продукт, сосредоточенный у k поставщиков Аi в количестве аi (i = 1,…,k) единиц, необходимо доставить n потребителям Bj в количестве bj (j=1, …, n) ед. Известна стоимость сij перевозки единицы груза от i-го поставщика к j-му потребителю.

Необходимо составить план перевозок, позволяющий вывести все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.

Сформулируем экономико-математическую модель транспортной задачи. Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки составит сij xij .

Стоимость всего плана выразится двойной суммой

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т.е.

,

б) все потребности должны быть удовлетворены, т.е.

 

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

при ограничениях

(*)

 

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

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие (2.4.5), называется закрытой моделью; в противном случае – открытой. Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности

б) суммарные потребности превышают суммарные запасы

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции

при ограничениях

(случай а)

 

(случай б)

 

Открытая модель решается приведением к закрытой модели.

В случай а , когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребность которого

В случае б , когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Ak+1, запасы которого

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

Транспортная задача имеет n+k уравнений с kn неизвестными.

Матрицу Х=(xij)k,n, удовлетворяющую условиям (*) называют планом перевозок транспортной задачи (xij – перевозками).

План Х* , при котором целевая функция обращается в минимум, называется оптимальным.