Применение надстройки «Поиск решения» MS Excel

Цель: Приобретение навыков решения задач линейного программирования в табличном редакторе MS Excel

Задачи: освоить решение задачи линейного программирования использую программную надстройку «Поиск решения» симплекс-методом

 

Пример 1

В ресторане готовятся фирменные блюда трех видов (блюдо А, блюдо В и блюдо С) с использованием при приготовлении ингредиентов трех видов (ингредиент 1, ингредиент 2 и ингредиент 3). Расход ингредиентов в граммах на блюдо задается следующей таблицей:

Вид ингредиента	Блюдо А	Блюдо В	Блюдо С
Ингредиент 1
Ингредиент 2
Ингредиент 3

Стоимость приготовления блюд одинакова (100 руб.).

Ежедневно в ресторан поступает 5 кг ингредиента 1 и по 4 кг ингредиентов видов 2 и 3. Каково оптимальное соотношение дневного производства блюд различного вида, если производственные мощности ресторана позволяют использовать весь запас поступивших продуктов?

 

Решение. Для решения задачи введем обозначения: пусть x₁ – дневной выпуск блюда А; х₂ – дневной выпуск блюда В; х₃ – дневной выпуск блюда С.

Составим целевую функцию – она заключается в стоимости выпущенных рестораном блюд:

Z= 100 * x₁ + 100 * х₂ + 100 * х₃.

 

Определим имеющиеся ограничения (руководствуясь таблицей):

 

1. 20 * x₁ + 50 * х₂ + 10 * х₃ £ 5000;

2. 20 * х₁, + 0 * х₂ + 40 * х₃ £ 4000;

3. 20 * х₁ + 10 * х₂ + 10 * х₃ £ 4000.

 

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

 

3. х₁ ³ 0;

4. х₂ ³ 0;

5. х₃ ³ 0;

6. х₁ – целое;

7. х₂ – целое;

8. х₃ – целое.

 

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

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

2. В ячейки А2, АЗ и А4 занесем дневной запас продуктов — числа 5000, 4000 и 4000 соответственно.

3. В ячейки С1, D1 и Е1 занесем начальные значения неизвестных х_1, х₂ и х₃ (нули) – в дальнейшем значения этих ячеек будут подобраны автоматически.

4. В ячейках диапазона С2: Е4 разместим таблицу расхода ингредиентов.

5. В ячейках В2: В4 укажем формулы для расчета расхода ингредиентов по видам. В ячейке В2 формула будет иметь вид =$С$1*С2 + $D$1*D2 + $Е$1*Е2, а ос­тальные формулы можно получить методом автозаполнения (копирования).

В ячейку F1 занесем формулу целевой функции =100*(С1 + D1 + Е1). Резуль­тат ввода данных в рабочую таблицу представлен на рис. 1.

Рис. 1.Результат ввода данных из примера 1

6. Дадим команду Поиск решения – откроется диалоговое окно Поиск решения.

В поле Установить целевую ячейку мышью укажем ячейку, содержащую оптимизируемое значение (F1) (рис. 2). Установим переключатель Равной в положение максимальному значению (требуется максимальный объем производства).

Рис. 2.Пример заполнения диалогового окна Поиск решения

9. В поле Изменяя ячейки мышью зададим диапазон подбираемых параметров (неизвестных х_i) — С1: Е1.

10. Чтобы определить набор ограничений, щелкнем на кнопке Добавить. В диа­логовом окне Добавление ограничения в поле Ссылка на ячейку мышью ука­жем диапазон В2: В4. В качестве условия зададим < =. В поле Ограничение мышью зададим диапазон А2: А4 (рис. 3). Это условие указывает, что дневной расход ингредиентов не должен превосходить запасов. Щелкнем на кнопке ОК.

Рис. 3.Пример заполнения диалогового окна Добавление ограничения

 

11. Снова щелкнем на кнопке Добавить. В поле Ссылка на ячейку укажем диапазон С1: Е1. В качестве условия зададим > =. В поле Ограничение зададим число 0. Это условие указывает, что число приготавливаемых блюд неотрицательно. Щелкнем на кнопке ОК.

12. Снова щелкнем на кнопке Добавить. В поле Ссылка на ячейку укажем диапазон С1: Е1. В качестве условия выберем пункт цел. Это условие не позволяет производить доли блюд. Щелкнем на кнопке ОК.

13. Щелкнем на кнопке Выполнить. По завершении оптимизации откроется диалоговое окно Результаты поиска решения.

14. Установим переключатель Значения параметров в положение Сохранить найденное решение, после чего щелкнем на кнопке ОК.

В результате получится оптимальный набор переменных (оптимальное количество приготавливаемых фирменных блюд) при данных ограничениях (при данном количестве ингредиентов): блюда А – 184 порции (х₁), блюда В – 24 порции (х₂) и блюда С – 8 порций (х₃). При этом общая стоимость блюд (Z) будет максимальной и равной 21 600 руб. При этом останутся неизрасходованными 40 г первого ингредиента (рис. 4).

Рис. 4. Результат вычислений из примера 1

 

Проанализируем полученное решение. Проверить его оптимальность можно, экспериментируя со значениями ячеек С1: Е1. Например, допустим, что решили приготовить количества блюд, соответственно 184, 23, 9. Тогда при той же общей стоимости блюд будет перерасход второго ингредиента на 40 г, что, естественно, недопустимо. Можно рассмотреть и другие варианты. Чтобы восстановить оптимальные значения, можно в любой момент повторить операцию поиска решения.

 

Пример 2

Туристская фирма заключила контракт с двумя турбазами: в г. Сухуми и в окрестных городах, рассчитанных, соответственно, на 200 и 150 человек.

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

– обезьяний питомник принимает в день 70 человек, ботанический сад – 180 че ловек, а в горы в один день могут пойти 110 человек;

– стоимость одного посещения выражается таблицей:

Турбаза	ОП	БС	Поход

 

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

пусть x₁ – число туристов из турбазы в Сухуми, посещающих обезьяний питомник;

х₂ – число туристов из турбазы в Сухуми, посещающих ботанический сад;

х₃ – число туристов из турбазы в Сухуми, отправляющихся в поход;

х₄– число туристов из окрестной турбазы, посещающих обезьяний питомник;

х₅ – число туристов из окрестной турбазы, посещающих ботанический сад;

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

 

Составим целевую функцию – она заключается в минимизации стоимости дневных мероприятий турфирмы:

 

Z= 5 * х₁ + 6 * х₂ + 20 * х₃ + 10 * x₄ + 12 * х₅ + 5 * х₆.

Определим имеющиеся ограничения (руководствуясь условиями задачи):

 

1. х₁ + х₄ £ 70

2. х₂ + х₅ £ 180;

3. х₃ + х₆ £ 110;

4. х₁ + х₂ + х₃ = 200;

5. х₄ + х₅ + х₆= 150.

 

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

1. х₁ ³ 0;

2. х₂ ³ 0;

3. х₃ ³ 0;

4. х₄ ³ 0;

5. х₅ ³ 0;

6. х₆ ³ 0;

7. х₁ – целое;

8. х₂ – целое;

9. х₃ – целое;

10. х₄ – целое;

11. х₅ – целое;

12. х₆ – целое.

 

Теперь можно приступить к решению задачи на компьютере

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

2. В ячейки А2, АЗ и А4 занесите дневное количество посетителей различных мероприятий – числа 70, 180 и 110, соответственно.

3. В ячейки А5 и Аб занесите количество туристов в обеих гостиницах – числа 200, и 150, соответственно.

4. В ячейки С1: Н1 занесите начальные значения неизвестных х_1, х_{2, ….} х₆ –нули) – в дальнейшем значения этих ячеек будут подобраны автоматически

5. В ячейках диапазона С2: Н6 разместите таблицу коэффициентов основных ограничений:

• 1, 0, 0, 1, 0, 0;

• 0, 1, 0, 0, 1, 0;

• 0, 0, 1, 0, 0, 1;

• 1, 1, 1, 0, 0, 0;

• 0, 0, 0, 1, 1, 1.

6. В ячейках В2: В6 укажите формулы для расчета ограничений. В ячейке В2 формула будет иметь вид

=$С$1*С2 + $D$1*D2 + $Е$1*Е2 + $F$1*F2+ $G1$*G2 + $Н$1*Н2,

а остальные формулы можно получить методом автозаполнения (копирования).

7. В ячейку I1 занесите формулу целевой функции

=5*C1+6*D1+20*E1 + 10*F1 + 12*G1 + 5*Н1.

8. Дайте команду Поиск решения – откроется диалоговое окно Поиск решения.

9. В поле Установить целевую ячейку укажите ячейку, содержащую оптимизируемое значение (I1). Установите переключатель Равной в положение минимальному значению (требуется минимальный объем затрат).

10. В поле Изменяя ячейки задайте диапазон подбираемых параметров (неизвестных х_i, ) – С1: Н1.

11. Чтобы начать определять набор ограничений, щелкните на кнопке Добавить. В диалоговом окне Добавление ограничения в поле Ссылка на ячейку укажите диапазон В2: В4. В качестве условия задайте < =. В поле Ограничение задайте диапазон А2: А4. Это условие указывает, что дневное количество посетителей мероприятий не должно превосходить их возможностей. Щелкните на кнопке ОК.

12. Для продолжения определения набора ограничений щелкните на кнопке Добавить. В диалоговом окне Добавление ограничения в поле Ссылка на ячейку укажите диапазон В5: В6. В качестве условия задайте =. В поле Ограничение задайте диапазон А5: А6. Это условие указывает, что дневное количество посетителей мероприятий должно быть равно количеству туристов. Щелкните на кнопке ОК.

13. Снова щелкните на кнопке Добавить. В поле Ссылка на ячейку укажите диапазон С1: Н1. В качестве условия задайте > =. В поле Ограничение задайте число 0. Это условие указывает, что число участников мероприятий неотрицательно. Щелкните на кнопке ОК.

14. Снова щелкните на кнопке Добавить. В поле Ссылка на ячейку укажите диапазон С1: Н1. В качестве условия выберите пункт цел. Это условие указывает, что турист неделим. Щелкните на кнопке ОК.

15. Щелкните на кнопке Выполнить. По завершении оптимизации откроется диалоговое окно Результаты поиска решения.

16. Установите переключатель Сохранить найденное решение, после чего щелкните на кнопке ОК.

В результате получится оптимальный набор переменных (оптимальное количество туристов для участия в каждом мероприятии из каждой гостиницы) при данных ограничениях (при заданных возможностях мероприятий): число туристов из турбазы в Сухуми, посещающих обезьяний питомник (х₁ = 30), ботанический сад (х₂ = 170) и отправляющихся в поход (х₃ = 0); число туристов из окрестной турбазы, посещающих обезьяний питомник (х₄ = 40), посещающих ботанический сад (х₅ = 0) и отправляющихся в поход (х₆= 110). При этом суммарные расходы турфирмы (Z) составят 2120 руб. и будут минимальными.

Можно проанализировать полученное решение. Его оптимальность проверяется путем эксперимента со значениями ячеек С1: Н1. Чтобы восстановить оптимальные значения, можно в любой момент повторить операцию поиска решения.

 

Упражнения для самостоятельного выполнения

1. Каждому животному нужно ежедневно выдать не менее 6 единиц белков, 8 единиц жиров и 12 единиц углеводов. Есть два вида корма. Одна единица перво­го корма содержит 21 единицу белка, 2 единицы жира. 4 единицы углеводов и стоит 3 руб. Для второго корма соответствующие цифры следующие: 3, 2, 2 и 2. Составьте математическую модель и найдите оптимальный рацион питания.

2. Продукцию, производимую на предприятиях А и В. надо развезти по магазинам № 1, № 2 и № 3. Предприятие А производит 320 единиц продукции, предприятие В – 380. Магазин № 1 реализует за сутки 200 кг., № 2 –280 кг, № 3 – 220 кг. Составьте план перевозок продукции, при котором их стоимость будет наименьшей, если стоимость перевозки 1 кг продукции задана таблицей:

Предприятие	Магазин № 1	Магазин № 2	Магазин № 3
А
В

 

3. Пошивочная мастерская планирует выпуск двух видов костюмов: мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм – 3, 5 м шерсти, 0, 5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти и 240 м лавсана. 150 человеко-дней трудозатрат. Предусматривается выпуск не менее 110 костюмов, причем необходимо обеспечить прибыль не менее 1400 руб. Определите оптимальное количество костюмов каждого вида, если прибыль от реализации женского костюма составляет 10 руб., а мужского – 20 руб.

4. Составьте оптимальный план производства продукции, чтобы стоимость всего объема произведенного была максимальной, если: цена 1 единицы каждой продукции по 20 денежных единиц. На каждую единицу первой продукции расхо­дуется 2 единицы сырья; 4 единицы материалов и 1 человеко-день: второй про­дукции – соответственно, 2, 3 и 3. Общие объемы ресурсов:

1. фонд рабочего времени – 12;

2. фонд сырья – 16;

3. фонд материалов – 9;

4. цена 1 единицы сырья –1 денежная единица;

5. цена материалов – 3 денежных единицы.

Проанализируйте математическую постановку этой задачи; как увеличить стоимость всей продукции, если можно привлечь дополнительные ресурсы, лиш­ние продавать?

5. Составьте оптимальный план производства, чтобы стоимость всей продукции была максимальной, если:

Продукция	Стоимость 1 ед.продукции	Норма расходов ресурсов
		Трудовых	Сырьевых	Материалов

Общие объемы ресурсов:

1. трудовых – 48;

2. сырьевых – 56;

3. материалов – 72;

4. цена одной единицы сырья – 2 денежные единицы;

5. материалов – 1, 5 денежные единицы.

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

 

 

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

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: