VIII Международная студенческая научная конференция Студенческий научный форум - 2016

 

Цель: овладеть навыками составления математической модели задачи нахождения оптимального плана выпуска продукции и ее решения в среде ЭТ MS Excel с помощью надстройки «Поиск решения» и в среде математического пакета MathCad c помощью блока Given … Maximize (Given … Minimize).

Краткая теория

Пусть некоторое предприятие обладает ресурсами S₁,S₂,…,Snв количествах соответственно b₁,b₂,…,bnединиц. Используя данные ресурсы предприятие может изготовить изделия И₁,И₂,…,И_m , при этом известны величины a_ij, – количество i-го ресурса, идущего на изготовление одного изделия j-го вида (i = 1,2,…,n, j = 1,2,…,m). Кроме того, известны величины c_j –прибыль, получаемая предприятием от реализации одного изделия j-го вида.

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

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

Вид ресурса	Запас ресурса		Расход ресурса на изготовления одного изделия
			И1		И2	…	Иm
S1 S2 …	b1 b2 …		а11 а21 … an1		a12 a22 … an2	… … … …	a1m a2m … anm
Прибыль от реализации одного изделия		c1		c2		…	сm

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

Математическая модель задачи распределения неоднородных ресурсов. Для построения математической модели задачи:

1. Определим неизвестные и их количество.

Введем следующие обозначения: пусть х₁,x₂,…,x_m – количество изделий И₁,И₂,…,И_m, которые может производить предприятие. Поэтому количество рассматриваемых переменных – m штук.

2. Запишем целевую функцию, зависящую от х₁,x₂,…,x_mи что с ней необходимо сделать (максимизировать или минимизировать).

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

3. Сформулируем ограничения рассматриваемой задачи.

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

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

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

(3)

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

3.3 Условие целочисленности переменных. На переменные можно накладывать дополнительное условие целочисленности, которое “запрещает” выпуск не целых изделий:

(4)

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

Пример выполнения

Постановка задачи. Пусть предприятие располагает запасами сырья трех видов – цемент, щебень и арматура в количествах b₁=18, b₂=120 и b₃=42 условных единиц соответственно. Из этого сырья может быть изготовлено два вида изделий – плиты перекрытия и фундаментные блоки. Известны так же значения а_ij – количество единиц i-го вида сырья, идущего на изготовление единицы j-го изделия и с_j – доход, получаемый от реализации одной единицы изделия каждого вида (i=1,2,3; j=1,2). Все указанные величины представлены в табл. 1.

Таблица 1. Данные к задаче составления оптимального плана

Вид сырья	Запассырья (усл. единиц)	Расход сырья на единицу продукции (усл. единиц)
		Плита перекрытия	Фундаментный блок
Цемент	b1 = 18	a11 = 3	a12 =1
Щебень	b2 = 120	a21 = 25	a22 = 3
Арматура	b3 = 42	a31 = 0	a32 = 3
Прибыль от продажи единицы изделия (усл.ден. единиц)		с1= 3	с2 = 2

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

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

Математическая модель задачи распределения неоднородных ресурсов. Для построения математической модели задачи:

1. Определим неизвестные и их количество.

Введем следующие обозначения: х₁ – количество плит перекрытия, х₂ – количество фундаментных блоков, которые может выпускать предприятие.

2. Запишем целевую функцию.

Суммарная прибыль, получаемая предприятием от реализации х₁ единиц плит перекрытия и х₂ единиц фундаментных блоков, может быть записана в виде

F(х₁,х₂ ) = 3 * x₁ + 2 * x₂ max. (1´)

3. Сформулируем ограничения рассматриваемой задачи.

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

 

(2´)

 

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

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

х₁  0, х₂  0 (3´)

(х₁ и х₂ равны нулю, если соответствующий вид изделия не выпускается).

3.3 Условие целочисленности переменных. На переменные х₁ и х₂ можно накладывать дополнительное условие целочисленности, которое “запрещает” выпуск не целых изделий:

х₁ и х₂ – целые (4´)

Таким образом, целевая функция (1´) и ограничения (2´− 4´) образуют математическую модель задачи распределения неоднородных ресурсов.

Решение задачи в среде ЭТ MSExcel. Для решения задачи с помощью надстройки Поиск решения в среде ЭТ MS Excel необходимо:

1. Cоздайте таблицу. В столбец «Расход ресурса» будут занесены левые части ограничений по запасам сырья (см. пункт 3.1) и в результате решения рассматриваемой задачи будут найдены фактические расходы сырья каждого вида. Создаем в ней столбец «Остаток изделия» для занесения в ячейки столбца формулы для расчета остатка нашего изделия исходя из данных «Количество ресурса» и «Расход ресурса».2. Создаём вторую таблицу, указав в ней выпускаемые изделия и переменные математической модели. В ячейках Е10:I10 поместили нулевые (начальные) значения искомых переменных х₁..х₅.

4. В ячейку E12 вводим формулу целевой функции, которая для решаемой задачи имеет вид =E3*E10+F3*F10+G3*G10+H3*H10+I3*I10. Завершив ввод нажатием клавиши Enter, получим в ячейке F12 нулевое значение, т.к. пока равны нулю значения переменные х₁..х₅.

5. Введите формулу =E3*E10+F3*F10+G3*G10+H3*H10+I3*I10 для ограничения по ресурсу «S1» в ячейку С3. Завершив ввод нажатием клавиши Enter, получим в ячейке С3 нулевое значение, т.к. пока равны нулю переменные х₁ и х₂. Скопируйте эту формулу, автозаполнением, в ячейки С4 и С5, предварительно заменив относительную ссылку на ячейки Е10 и F10 на абсолютную при помощи клавиши F4. При этом формула примет вид ==E3*$E$10+F3*$F$10+G3*$G$10+H3*$H$10+I3*$I$10, а в ячейках С4 и С5 снова получим нулевые значения. В ячейку D3 занесите формулу вычисления остатков сырья первого вида =B3−C3 и скопируйте ее автозаполнением в ячейки D4 и D5.

6. Наберите команду Данные → Поиск решения. В появившемся диалоговом окне надстройки Поиск решения необходимо выполнить три основные установки:

6.1. Заполните поле «Установить целевую ячейку». В зависимости от решаемой задачи, можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить в ней конкретное числовое значение. Для рассматриваемой задачи выполните ссылку на ячейку F12, где записана формула целевой функции.(см. таблицу в Пункт №4)

6.2.1 Установите радиокнопку «Равной максимальному значению».

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

зависима от изменяемых.

6.3. Введём ограничения по запасам сырья и естественные условия неотрицательности переменных х₁..х₅, для этого:

а) щелкним по кнопке «Добавить» диалогового окна и в появившемся окне «Добавление ограничения» выполните следующие установки:

Задание таких ограничений означает, что расход сырья каждого вида на выполнение производственной программы не должен превышать его запаса на предприятии. Щелчок по кнопке ОК приводит к закрытию диалогового окна «Изменение ограничения», при этом само условие заносится в раздел «Ограничения:» диалогового окна надстройки Поиск решения.

б) ещё раз щелкните по кнопке «Добавить» диалогового окна Поиск решения и в появившемся окне «Добавление ограничения» выполните следующие установки:

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

7. Щелкните по кнопке «Найти решение». Если решение найдено, то появится диалоговое окно:

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

Если для переменных х₁…х₅ добавить условие целочисленности, “запрещающее” выпуск не целых изделий в виде еще одного «Ограничения» в «Поиск решения», то в строке 2ой таблицы «Кол-во выпускаемых изделий» у нас будут прописываться только целые изделия:Также можно установить ограничение на минимальное количество изделий, например не меньше 3ёх изделий:И в итоге получим подобную таблицу:

Решение задачи с помощью пакета MathCad.

Код для цитирования: Скопировать