Решение задач нелинейного программирования средствами табличного процессора EXCEL

Решение задач нелинейного программирования в Excel в основном аналогично решению задач линейного программирования.

Рассмотрим решение примера 4.3 средствами Excel.

Предположим, что желательно получить результаты (значения переменных Х₁ и Х₂) в ячейках В2 и С2. В ячейке ВЗ введем формулу целевой функции:

=5∙В2–0,2∙В2^2+2∙С2–0,2∙С2^2

В ячейке В4 введем формулу первого ограничения (на расход платины):

=13∙В2+6∙С2

В ячейке D4 введем правую часть этого ограничения: 90.

Аналогично в ячейках В5 введем формулу ограничения на расход палладия:

(=8∙В2+11∙С2), в ячейке D5 - правую часть этого ограничения (88).

Укажем также некоторые поясняющие надписи и обозначения (хотя это и необязательно).

Рабочий лист будет иметь примерно такой вид, как показано на рис. 4.1.

Примечание. Значения 0 в ячейках В3 – В5 получены автоматически для начальных значений переменных, равных нулю.

Для решения задачи из меню «Сервис» выберем элемент «Поиск решения». В поле «Установить целевую ячейку» указывается ячейка В3, где находится формула целевой функции. Используя переключатели, необходимо указать, что требуется установить ячейку В3 «равной максимальному значению» (так как целевая функция в этой задаче подлежит максимизации). В поле «Изменяя ячейки» указываются ячейки, в которых должны находиться значения переменных: В2:С2.

В области «Ограничения» указываются ограничения. Необходимо ввести ограничения на расход платины и палладия, заданные на рабочем листе, а также ограничение на неотрицательность всех переменных (В2:С2 >=0) и ограничение на их целочисленность (в поле «Ссылка на ячейку» указать В2:С2, а в поле знака ограничения выбрать отметку «цел»).

Для решения задачи следует нажать кнопку «Выполнить». Рабочий лист с результатами решения показан на рис. 4.2.

 

Рис. 4.1. Рабочий лист Ехсеl для решения примера 6.3

Рис. 4.2. Рабочий лист Ехсеl с результатами решения примера 6.3

 

В ячейках В2 и С2 получены оптимальные значения переменных, в ячейке ВЗ - оптимальное значение целевой функции. Эти величины совпадают с результатами, полученными по методу Франка-Вульфа.

В ячейках В4 и В5 находятся значения левых частей ограничений. Видно, что на выпуск изделий будет израсходовано 90г платины и 70г палладия.

Примечания:

1. В табличном процессоре Excel для решения задач оптимизации (элемент меню «Поиск решения») используются именно градиентные методы.

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

 

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

1. Изучить теоретическую часть.

2. Решить задачу оптимизации методом нелинейного программирования.

3. Для решения использовать редактор EXCEL

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

1. При каких условиях оптимизационная задача может быть отнесена к классу нелинейных?

2. Приведите пример экономической модели, сводящейся к задаче нелинейного программирования.

 

 

Варианты заданий.

Найти условный экстремум функции Z = f (x₁,x₂), если переменные связаны условием j(x₁,x₂) = 0.

1. Z = 6 ‑ 4x₁ ‑ 3x₂;

;

 

2. Z = x₁ × x₂;

x₁ +x₂ = 1;

 

3.

 

4.

 

5.

 

6.

 

7.

 

8.

 

9.

 

10.

 

11. Z = 6 ‑ 2x₁ ‑ x₂;

;

 

12. Z = x₁ × x₂;

x₁² +x₂² = 1;

 

13.

 

14.

 

15.

 

16.

 

17.

 

 

18.

 

19.

 

20.

 

Лабораторная работа №5

Задачи теории графов

Обзор задач теории графов

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

Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.

Типовые задачи теории графов:

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

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

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

4. Управление проектами (Управление проектами – раздел теории управления, изучающий методы и механизмы управления изменениями (проектом называется целенаправленное изменение некоторой системы, осуществляемое в рамках ограничений на время и используемые ресурсы; характерной чертой любого проекта является его уникальность, то есть нерегулярность соответствующих изменений)). С точки зрения теории графов проект – совокупность операций и зависимостей между ними (сетевой график). Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

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

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