кцуыв. Лаб_раб__задачи c лин_прог_2020. Лабораторная работа Моделирование оптимизационных задач

• Название: Лабораторная работа Моделирование оптимизационных задач
• Анкор: кцуыв
• Дата: 23.05.2023
• Размер: 2.26 Mb.
• Имя файла: Лаб_раб__задачи c лин_прог_2020.doc
• Тип: Лабораторная работа; #1153448

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

Моделирование оптимизационных задач

методами линейного программирования

Цель работы: изучить практические методы моделирования типичных экономических задач методами линейного программирования с применением электронных таблиц и математического процессора.
Теоретическая часть

Линейное программирование (ЛП) — это раздел математики, занимающийся решением таких задач на отыскание наибольших и наименьших значений, для которых методы математического анализа оказываются непригодными. Другими словами термин «линейное программирование» характеризует определение программы (плана) работы конкретного экономического объекта на основе выявления линейных связей между его элементами. Задачей линейного программирования является нахождение оптимального, т. е. наилучшего, плана при заданной системе налагаемых на решение ограничений.

К классу задач линейного программирования относится большое количество разнообразных задач планирования и управления, как, например:

1. 
   нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);
   
2. 
   оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);
   
3. 
   определение оптимального рациона (оптимизация состава химической смеси);
   
4. 
   транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);
   
5. 
   задача о размещении производства (планирование с учётом затрат на производство и транспортировку продукции);
   
6. 
   задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.
   

Задачей линейного программирования является задача оптимизации (т. е. максимизации или минимизации) линейной функции

(1)

при наличии линейных ограничений

(2)

,

Другими словами, необходимо найти такое решение системы (2), при котором линейная функция (1) принимает оптимальное значение.

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

Общая формулировка задания

Перед выполнением лабораторной работы изучите теоретическую часть, последовательно выполните все указанные в контрольном примере действия, оформите отчет.
Пример выполнения работы
1 Задача об оптимальном составе смеси (задача составления рациона, задача о диете)
К группе задач о смесях относят задачи по нахождению наиболее экономичного набора из определённых ингредиентов (пищевых продуктов, руды, нефти и др.), обеспечивающих получение смеси с заданными свойствами (ограничения на физический или химический состав смеси и на наличие необходимых материалов). Иными словами, получаемые смеси должны иметь в своём составе различных компонентов в определённых количествах, а сами компоненты являются составными частями исходных материалов.
Задача 1. Для откорма животных на ферме в их ежедневный рацион необходимо включить не менее 33-х единиц питательного вещества , 23-х единиц вещества и 12-ти единиц вещества . Для откорма используется 3 вида кормов. Данные о содержании питательных веществ и стоимости весовой единицы каждого корма даны в таблице 1.

Таблица 1

	(усл. ед.)	(усл. ед.)	(усл. ед.)	Стоимость (руб.)
Весовая единица корма I	4	3	1	20
Весовая единица корма II	3	2	1	20
Весовая единица корма III	2	1	2	10

Требуется составить наиболее дешёвый рацион, при котором каждое животное получило бы необходимые количества питательных веществ , и .

Математическая постановка задачи 1. Пусть , , — количества кормов I, II, III видов, включаемые в ежедневный рацион ( , ). Тогда должно быть:

(3)

При этом линейная функция (стоимость рациона)

(4)

Решение задачи 1 в среде MicrosoftExcel.

В настоящее время одним из наиболее известных способов численного решения задач линейного программирования является использование надстройки «Поиск решения» электронных таблиц Microsoft Excel.

Теоретической основой надстройки «Поиск решения» является симплекс-метод, позволяющий находить оптимальное решение задачи планирования с помощью итерационного процесса перехода к улучшающимся планам. «Поиск решения» является дополнением Excel, т. е. может не входить в стандартный вариант установки электронных таблиц. Для его добавления достаточно воспользоваться командой ФайлПараметрыНадстройкиПоиск решения.

При решении задачи с помощью надстройки Поиск решения необходимо:

1. 
   открыть окно Microsoft Excel и активизировать надстройку;
   
2. 
   заполнить ячейкиA1-А4 таблицы обозначениями , , и min соответственно. В ячейку В4 записать формулу (4) через адреса соответствующих ячеек (адреса ячеек вводятся щелчком мыши по соответствующей ячейке или набираются с клавиатуры) (рисунок 1);
   

Рисунок 1- Ввод целевой функции

3. 
   в диапазон ячеек А7-С9 записать систему (3) через адреса соответствующих ячеек, т. е. в А7 ввести формулу , нажать Enter, в А8 ввести формулу , нажать Enter, в А9 ввести формулу , нажать Enter, в ячейки В7-В9 ввести слова «не менее», в ячейки С7-С9 значения соответственно рисунку 2;
   

Рисунок 2- Ввод ограничений

4. 
   для решения поставленной задачи в меню выбрать пункт Поиск решения… (рисунок 3). В появившемся окне Выбор метода решения установите Поиск решения линейных задач симплекс-методом;
   

Рисунок 3 – Параметры поиска решения

5. 
   в окне Параметры поиска решения в поле Оптимизировать целевую функцию щёлкните по кнопке , затем в ячейке B4 и снова по кнопке ; в поле До установить флажок Минимум, в поле Изменяя ячейки переменных щёлкнуть по кнопке , выделить мышью диапазон ячеек В1В3 и снова щёлкнуть по кнопке ;
   
6. 
   в этом же окне осталось незаполненным поле В соответствии с ограничениями, поэтому надо нажать на копку Добавить: появится новое окно Добавление ограничения, в поле Ссылка на ячейку щёлкнуть по кнопке , затем выделить мышью диапазон ячеек В1В3 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать знак >=, нажав , затем в поле Ограничение ввести 0 (рисунок 4);
   

Рисунок 4 – Добавление первого ограничения

7. 
   в этом же окне Добавление ограничения нажать кнопку Добавить (появится новое окно Добавление ограничения) и ввести новое ограничение: в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек А7А9 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать знак >=, нажав , затем в поле Ограничение надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек C7C9 и снова щёлкнуть по кнопке ( рисунок 5);
   

Рисунок 5 - Добавление ограничения

8. 
   теперь все ограничения учтены: надо нажать ОК, после чего снова откроется диалоговое окно Поиск решения, и надо нажать кнопку Выполнить. В появившемся диалоговом окне Результаты поиска решения (в котором компьютер предлагает по умолчанию сохранить найденное решение) надо нажать кнопку ОК.
   
9. 
   Результат полученных вычислений представлен на рисунке 8.
   

Рисунок 6 - Результат подбора значений
Замечание 1. Если в неравенствах (3) знаки разные ( , , ), то ограничения в пункте 8 вносятся отдельно для каждой строки, а не через диапазон, как в примере.

Замечание 2. Если часть ограничений представляют собой неравенства другого знака (в данном случае ), то все коэффициенты и свободные члены для данных строк умножаются на и знак выставляется одинаковый для всей системы.

Замечание 3. На практике часто требуется, чтобы на переменные , , налагалось условие целочисленности (например, если какой-то продукт нельзя разрезать на части, а можно добавлять в рацион только целыми порциями), в этом случае в окне Добавление ограничения, в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек В1В3 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать условие ЦЕЛ, нажав ( рисунок 7).


Рисунок 7 - Окно Добавление ограничения
Решение задачи 1 в среде MathСad:

1. 
   запустить MathСad;
   
2. 
   задать начальное приближение:
   

3. 
   записать все коэффициенты из (3) и (4) в матричном виде:
   

знак «присваивания» := находится на панели инструментов Вычисления; матрица (вектор) вставляется комбинацией клавиш Ctrl и M (англ.) или выбирается на панели инструментов Матрица, после чего вводятся количество строк и столбцов;

4. 
   ввести целевую функцию (4) в виде:
   

знак «умножить» вставляется комбинацией клавиш Shift и *;

5. 
   записать функцию Given;
   
6. 
   записать ограничения (3) в виде:
   

7. 
   записать функцию минимизации
   

знак равенства вставляется с клавиатуры клавишей =;

после чего получим оптимальный план

8. 
   найти значение целевой функции в точке минимума:
   

Таким образом, оптимальные планы Задачи 1 при решении в средах Microsoft Excel и MathСad получились различные (могут использоваться и те и другие), но целевая функция при этом имеет одинаковое значение.
Задача 2. В баре имеются три компонента: коньяк, шампанское, сок. Цель: подобрать оптимальный состав коктейля из этих трёх компонентов, если известно: стоимости ингредиентов в рублях: , , ; содержание алкоголя в промиллях , , ; вкусовые качества в баллах , , . Крепость коктейля должна быть не меньше 0,2 промилле. Вкус должен иметь не менее 8 баллов.

Математическая постановка задачи 2. Пусть , , — доля каждого компонента в коктейле ( , ).

Тогда должно быть:

_{ } (5)

(третье условие отражает наличие в составе смеси только трёх компонентов, т. е. то, что все три компонента составляют весь коктейль в целом — 1).

При этом линейная функция (стоимость коктейля) будет иметь вид:

(6)

Решение задачи 2 в Microsoft Excel имеет вид, представленный на рисунке 8 и 9.



Рисунок 8 – Окно с поиском решения Рисунок 9- Решение
Замечание 5. Для того, чтобы в решении задачи после запятой отображалось только 2 знака, надо выделить соответствующий диапазон ячеек, щёлкнуть на выделенном правой кнопкой мыши, в появившемся контекстном меню выбрать пункт Формат ячеек и на вкладке Число выбрать Числовой, указав Число десятичных знаков 2.
Решение задачи 2 в среде MathСad:

Получен оптимальный план



Для того чтобы MathСad отображал только 2 десятичных знака, надо выделить значения, для которых необходимо сменить формат вывода, в меню Формат выбрать подменю Результат — появится диалоговое окно Формат результата (рисунок 10) и указать количество десятичных знаков 2:



Рисунок 10 - Диалоговое окно Формат результата
Для вычисления значения целевой функции в точке минимума:



Таким образом, оптимальные планы Задачи 2 при решении в средах Microsoft Excel и MathСad получились одинаковые, а целевая функция при решении в среде MathСad имеет меньшее значение, таким образом, среда MathСad, в данном случае, даёт лучшее решение, чем Microsoft Excel.
3. Задача об оптимальном распределении ресурсов при выпуске продукции на предприятии (об ассортименте)
К группе задач о распределении ресурсов относят задачи, цель которых состоит в том, чтобы организовать доставку материалов от некоторого числа источников к некоторому числу потребителей так, чтобы оказались минимальными либо расходы по этой доставке, либо время, затрачиваемое на неё и др., либо некоторая комбинация вышеперечисленного. В простейшем виде это задача о перевозках (транспортная задача).
Задача 3. На товарных станциях и имеется по 30 комплектов мебели. Известно, что перевозка одного комплекта со станции в магазины , , стоит 1 руб., 3 руб., 5 руб. соответственно, а стоимость перевозки со станции в те же магазины – 2 руб., 5 руб., 4 руб. необходимо доставить в каждый магазин по 20 комплектов мебели. Составить план перевозок так, чтобы затраты на транспортировку мебели были наименьшими.

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

Таблица 2

	В	В	В	Всего отправлено
Из				30
Из				30
Всего получено	20	20	20	60

В соответствии с условием задачи ( , — целые, ). Задача сводится к тому, чтобы найти такое неотрицательное целочисленное решение системы (7)

(7)

при котором линейная функция (стоимость перевозок)

(8)

имеет наименьшее значение.

Решение задачи в MicrosoftExcelпредставлено на рисунке 11.



Рисунок 11 – Решение задачи
Решение задачи 3 в среде MathСad:

1. 
   задать начальное приближение:
   

2. 
   записать все коэффициенты из (1) и (2) в матричном виде:
   

3. 
   ввести целевую функцию (2) в виде:
   

4. 
   записать функцию Given;
   
5. 
   записать ограничения (1) в виде:
   

знак «жирное равно» выбирается на панели инструментов Логический или вставляется комбинацией клавиш Ctrl и =;

6. 
   записать функцию минимизации
   

после чего получим оптимальный план

7. 
   найти значение целевой функции в точке минимума:
   

Полученные результаты совпали.
4.Задача производства

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

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

Таблица 3

	Древесина,	Стекло,	Зеркала,	Трудозатраты, чел.-дней
«Стенка»	4	4	3	10
«Шкаф»	2	0	2	7
«Гарнитур»	2	5	1	8

Запасы сырья на складе обновляются ежемесячно и составляют 70  древесины, 90  стекла и 45  зеркал. Трудозатраты в месяц не должны превышать 200 человеко-дней. Чистая прибыль от продажи одной «стенки», «шкафа» и «гарнитура» составляет соответственно 2000 руб., 1250 руб. и 1500 руб. Найти оптимальный ассортимент продукции, максимизирующий общую прибыль за месяц.

Математическая постановка задачи. Пусть , , — месячный выпуск продукции соответственно: «стенок», «шкафов» и «гарнитуров» ( , — целые, ). Тогда должно быть:

(3)

При этом линейная функция (стоимость рациона)

(4)

Решите задачу в среде Microsoft Excel(должно получиться 37500 руб).

Решение задачи 2 в среде MathСad (с применением функции максимизации Maximize(f,x)):

:



Сделайте вывод по полученным результатам.
Замечание. В классическом наборе функций в среде MathСad (без установки надстройки MathСad Solving and Optimization Extension Pack) могут отсутствовать функции нахождения целочисленного решения.

5. Изучите примеры задач книги Solvsamp.xls, постройте математические модели для них, выполните задачи книги Solvsamp.xls.

Книга Solvsamp.xls, входящая в состав Excel, в папке Examples\Solver содержит более сложные примеры использования средств процедуры Поиска решения (файл с книгой скопирован в папку, где находится методичка).

Листы с примерами расчетов из этой книги можно использовать как образцы решения различных задач оптимизации. Чтобы изучить листы с задачами линейного программирования "Перевозка грузов", "График работы" и "Оборотный капитал", откройте книгу, перейдите на нужный лист, затем выполните команду Поиск решения. Целевые ячейки, влияющие ячейки и ограничения на листах уже заданы. Книга Solverex.xls, входящая в состав Excel, содержит пример решения типичной задачи маркетинга: определения затрат на рекламу, при которых прибыль от реализации товара будет максимальной. Решение этой задачи позволяет определить: "Стоит ли вкладывать дополнительные средства в рекламу, чтобы увеличить прибыль?". Задачи, подобные приведенной, демонстрируют использование процедуры Поиска решения для подбора таких значений параметров, которые максимизируют значение нелинейной функции.

Варианты индивидуальных заданий:

Взять индивидуальное задание у преподавателя

Требования к оформлению и порядку выполнения

Отчет должен содержать:

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

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