Методические указания к лабораторным работам по курсу “Математическое моделирование” (стр. 3 )

Первые блюда – 0 шт.;

Вторые мясные - 3763,70*100 шт.;

Вторые рыбные - 2500*100 шт.;

Вторые молочные - 2029,27*100 шт.;

Вторые прочие - 2602,74*100 шт.;

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

Excel позволяет представить результаты поиска решения в форме отчета. Для этого в диалоговом окне “Результаты поиска решения” следует указать тип отчета из списка «Тип отчета». Выберем опцию «Результаты». Отчет будет создан на отдельном рабочем листе

ТРЕБОВАНИЯ К ОТЧЕТУ

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

1. Цель и порядок выполнения работы.

2. Математическую модель задачи и краткую характеристику математической модели.

3.  Описание и результаты решения задачи линейного программирования в среде MS Excel

4. Краткий анализ решения.

5. Выводы.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.  Каковы основные этапы решения задач линейного программирования в MS Excel?

2.  Какая надстройка MS Excel применяется для решения зада линейного программирования?

3.  Опишите основные этапы работы с надстройкой MS Excel «Поиск решения».

4.  Каким образом в MS Excel задается направление оптимизации целевой функции?

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

Лабораторная работа №4. Решение задач линейного программирования средствами MS Excel: транспортная задача

ЦЕЛЬ РАБОТЫ: овладение методикой решения оптимизационных задач в области технология продукции и организации общественного питания средствами MS Excel.

ОБЩИЕ СВЕДЕНИЯ

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi,…, Аm, в которых сосредоточены запасы однородных продуктов в количестве a1, ..., аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1, ..., Вm, потребность которых в указанных продуктах составляет b1, ..., bn единиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта Ai в пункт Вj, i 1, …, m; j 1, ..., n. Предположим, что,

т. е. общий объем производства равен общему объему потребления.

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

Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью.

ЗАДАНИЕ

Пусть производство продукции осуществляется на 4-х предприятиях А1, А2, А3, А4 а затем развозится в 5 пунктов потребления этой продукции B1, B2, B3, B4, B5. На предприятиях Ai (i = 1, 2, 3, 4) продукция находится соответственно в количествах ai (условных единиц). В пункты Bj (j = 1, 2, 3, 4,5) требуется доставить bj единиц продукции. Стоимость перевозки единицы груза (с учетом расстояний) из Ai в Bj определена матрицей  .

Предприятия могут выпускать в день 235, 175, 185 и 175 единиц продукции. Пункты потребления готовы принимать ежедневно 125, 160, 60, 250 и 175 единиц продукции. Стоимость перевозки единицы продукции (в у. е.) с предприятий в пункты потребления приведена ниже.

Требуется минимизировать суммарные транспортные расходы по перевозке продукции.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Выполним проверку сбалансированности математической модели задачи. Модель является сбалансированной, так как суммарный объем производимой продукции в день равен суммарному объему потребности в ней:

235+175+185+175=125+160+60+250+175

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

2. Приступим к построению математической модели поставленной задачи. Неизвестными будем считать объемы перевозок.
Пусть хij – объем перевозок с i-го пункта поставки в j-й пункт потребления. Суммарные транспортные расходы:

,

где сij – стоимость перевозки единицы продукции с i-го предприятия в j-й пункт потребления.

Неизвестные в этой задаче должны удовлетворять следующим ограничениям:
• Объемы перевозок не могут быть отрицательными, т. е. ;

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

Итак, имеем следующую задачу линейного программирования:

найти минимум функции:

 

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

, , 

3. Приступаем к решению задачи на компьютере.

3.1. Откроем новый рабочий лист Excel.

3.2. В ячейки B3:F6 стоимость перевозок единицы груза.

3.3. В ячейках B16:F16 укажем формулы для расчета суммарной потребности продукции для j-го пункта, в ячейках G12:G15 – формулы суммарного объема производства i-го предприятия.

3.4. В ячейки B18:F18 заносим значения потребности продукции соответствующего пункта потребления, в ячейки H12:H15 заносим значения объема производства соответствующего предприятия.

3.5. В ячейку B20 занесем формулу целевой функции. Результаты выполненных операций представлены на рисунке 3.1.

Рисунок 3.1. – Исходные данные задачи линейного программирования в MS Excel

3.6. Выполним команду «Сервис → Поиск решения». Откроется диалоговое окно «Поиск решения». Если такой команды во вкладке Сервис нет, то следует подключить эту надстройку перейдя по «Сервис → Надстройки», и поставив галочку напротив нужной, т. е. «Поиск решения».

3.7. В поле «Установить целевую ячейку» указываем ячейку, содержащую оптимизируемое значение. Установим переключатель «Равный» в положение «минимальному значению».

3.8. В поле «Изменяя ячейки» мышью зададим диапазон подбираемых параметров $B$12:$F$15.

3.9. В поле «Ограничения» введем необходимые ограничения и нажмем на кнопку «Добавить», затем «Выполнить». Окно «Поиск решения» показано на рисунке 3.2.

Рисунок 3.2. – Окно «Поиск решения»

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

Рисунок 3.2. – Оптимальный набор переменных

Оптимальность решения можно проверить, экспериментируя со значениями ячеек $B$12:$F$15.

ТРЕБОВАНИЯ К ОТЧЕТУ

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

1. Цель и порядок выполнения работы.

2. Математическую модель задачи и краткую характеристику математической модели.

3. Описание и результаты решения задачи линейного программирования в среде MS Excel

4. Краткий анализ решения.

5. Выводы.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дайте определение транспортной задачи линейного программирования.

2. Какие основные отличия между сбалансированной и несбалансированной транспортными задачами?

3. Поясните общий порядок работы с формой «Поиск решения».

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

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

Лабораторная работа №5. Решение задачи нелинейного программирования средствами MS Excel и графическим методом

ОБЩИЕ СВЕДЕНИЯ

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

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

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

Значение ε вводится в окне «Параметры поиска решения» в строке «Относительная погрешность».

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

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