Лаб-23. Лабораторная работа 23 Решение задач линейного программирования

• Название: Лабораторная работа 23 Решение задач линейного программирования
• Дата: 27.04.2022
• Размер: 489.5 Kb.
• Имя файла: Лаб-23.doc
• Тип: Лабораторная работа; #501419

Лабораторная работа № 23
Решение задач линейного программирования
Такие задачи, как оптимизация распределения ресурсов, минимизация транспортных затрат доставки товаров относятся к задачам линейного программирования. Задачи линейного программирования описываются системами линейных уравнений и линейными целевыми функциями, для решения которых в Excel предусмотрен инструмент Поиск решения из меню Сервис.
Задание 1
Требуется расфасовать 1400 кг сыпучего материала по контейнерам (каждый вмещает по 270 кг), бочкам (каждая вмещает по 130 кг) и канистрам (90 кг). Требуется определить, сколько контейнеров, бочек и канистр потребуется для расфасовки всего сыпучего материала.

1. Составьте таблицу, заполните её исходными данными (рис.1)

2. В ячейку B4 запишите выражение для расчета объема расфасованного материала по тарам:

=$B$2*$B$3+$C$2*$C$3+$D$2*$D$3. (1)

Выражение представляет сумму произведений вместительности данного типа ёмкости на количество емкостей данного типа.




Рис. 1
3. В ячейку B6 записываем целевую функцию, выраженную как разность между исходным количеством сыпучего материала (ячейка B5) и реально расфасованным количеством (ячейка B4):

=$B$5–$B$4. (2)

В соответствии с поставленной задачей эту разность необходимо свести к минимуму.

4. В меню Сервис выберите Поиск решения. Если указанный инструмент отсутствует, то в меню Сервис выберите пункт Надстройки и в окне установите флажок Поиск решения.

5. В окне Поиск решения выполните следующие действия:

– в поле Установить целевую ячейку запишите B6;

– в группе переключателей Равной: установите переключатель минимальному значению;

– в поле Изменяя ячейки укажите диапазон $B$3:$D$3;

– в поле Ограничения задайте искомые значения как целые $B$3:$D$3=целое и неотрицательное $B$3:$D$3>=0 (так как количество контейнеров и т. д. не может выражаться отрицательным числом) и $B$4<=$B$5 (так как исходное количество сыпучего материала не может быть меньше расфасованного).

6. Щелкните по кнопке Выполнить. Если материал расфасован без остатка, то значение целевой функции будет равно 0. То есть найден-ное решение будет оптималь-ным (рис. 2).

Рис. 2

Задание 2
Перед вами стоит задача расселения постояльцев в гостинице. Допустим, прибыло 125 человек. В гостинице имеются одно-, двух-, и трёхместные номера. Мест в гостинице достаточно для всех прибывших. Определить, какое количество одно-, двух-, и трёхместных номеров потребуется для полного расселения постояльцев.

1. Составьте таблицу, заполните её исходными данными (рис. 3)

2. В ячейку B5 запишите выражение для расчета количества расселённых постояльцев:

=$B$2*$B$3+$C$2*$C$3+$D$2*$D$3. (3)

Выражение представляет сумму произведений вместительности данного типа ёмкости на количество емкостей данного типа.

3. В ячейку B6 записываем целевую функцию, выраженную как разность между количеством прибывших (ячейка B4) и расселенным по номерам (ячейка B5), взятую по модулю (функция ABS):

=ABS($B$4–$B$5). (4)

В соответствии с задачей эту разность необходимо минимизировать.

4. В меню Сервис выберите Поиск решения. Заполните следующие поля:

установить целевую функцию – запишите B6;

переключатель Равной – установите в положение минимальному значению;

изменяя ячейки – запишите диапазон $B$3:$D$3;

ограничения – количество комнат должно быть целым ($B$3:$D$3 целое) и не отрицательное число ($B$3:$D$3>=0).

5. Щелкните по кнопке Выполнить.

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

$B$3:$D$3=целое, $B$3:$D$3>=0, $B$4=$B$5.


Рис. 3
Последнее ограничение требует строгого соответствия количества при-бывших и размещённых людей, что отличается от предыдущего варианта, ког-да разность между указанными количествами только минимизировалась. Полученные результаты будут отличаться от предыдущих. Более жёсткое условие равенства вместо минимизации целевой функции изменяет результаты поиска решения и приводит к излишней точности.
Задание 3
Перед вами стоит задача распределения ресурсов. Предприятие производит два типа изделий: изделие А и изделие В. На производство изделия А расходуется 4 единицы условного сырья, на изделие В расходуется 7 единиц условного сырья. На одну рабочую смену предприятие снабжается 22 единицами условного сырья. Для изготовления изделия А требуется 8 рабочих, для изготовления изделия В требуется 5 рабочих. Общее количество рабочих на предприятии – 30 человек. Транспортные расходы на перевозку изделия А составляют 3 условные единицы, на перевозку изделия Б – 4 условные единицы. Общие транспортные расходы в течении рабочего дня не должны превышать 20 у. е. Прибыль от реализации одного экземпляра продукта А составляет 7 у. е., прибыль от реализации одного экземпляра продукта Б составляет 6 у. е.

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

1. Создайте таблицу с исходными данными (рис. 4).

2. Выражение для целевой функции запишите в ячейку В15:

=В9*В13+С9*С13.




Рис. 4
Здесь количество каждого из изделий умножается на прибыль от реализации изделия.

3. Сформулируйте ограничения. Реальные затраты не должны превышать лимиты на ресурсы. Запишите в ячейки диапазона Е3:Е5 расчётные формулы для расхода ресурсов соответственно по сырью, людям и транспорту:

=B3*B9+C3*C9, (5)

=B4*B9+C4*C9, (6)

=B5*B9+C5*C9. (7)

4. В меню Сервис выбираем Поиск решения (рис. 5). В качестве целевой укажите ячейку B5 и поставьте переключатель Равной максимальному значению. В поле изменяя ячейки запишите ячейки $B$9: $C$9, в которых будут выведены результаты расчёта количества изделий, производимых за смену.

В поле ограничения к ограничениям (5–7) следует добавить требования на неотрицательность и целочисленность результата (так как количество изделий не может быть отрицательным и нецелым):

$B$9:$C$9=целое,

$B$9:$C$9>=0.




Рис. 5
Задание 4
На рис. 6 приведен пример графической интерпретации транспортной задачи при следующих условиях. Количество исходных пунктов – три склада с товарами. Количество пунктов назначения – два магазина. Количество товара на каждом из складов 80, 70 и 120 тонн. Количество товара, которое требуется доставить в каждый из магазинов – 170 и 100 тонн. Расценки на транспортировку товара для каждой пары склад-магазин приведены на рис. 7.

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

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

В общем виде при наличии N исходных пунктов (N строк) и M пунктов назначения (M столбцов) применима следующая схема формирования ограничений (рис. 8).


Рис. 6 Рис.7



Рис. 8
На рис. 8 овалами обозначены ячейки, в которых происходит суммирование, прямоугольниками – ячейки, которые входят в сумму.

1. Создайте таблицу и заполните её в соответствии с рис. 7. В ячейки С3:С5 и Е3:Е5 внесите значения стоимостей перевозок для каждого магазина.

2. В ячейку C7 запишите выражение для целевой функции:

=С3*D3+C4*D4+C5*D5+E3*F3+E4*F4+E5*F5. (8)

Выражение для целевой функции (8) представляет собой сумму транспортных затрат, где стоимость перевозки для каждой пары склад-магазин умножается на количество доставляемого товара. Эти затраты требуется свести к минимуму.

3. Зададим систему ограничений. При любых комбинациях маршрутов перевозок по схеме склад-магазин со всех трёх складов товар должен быть полностью вывезен и доставлен в два магазина. Отсюда следует первая группа ограничений: в ячейку B3 записываем

=$D$3+$F$3; (9)

в ячейку B4 –

=$D$4+$F$4; (10)

в ячейку B5 –

=$D$5+$F$5; (11)

в ячейку B6 – выражение для суммы товара на трёх складах

=$B$3+$B$4+$B$5. (12)

4. Вторая группа ограничений составляется для каждого из магазинов. В ячейку D6 для магазина 1 запишите

=$D$3+$D$4+$D$5; (13)

в ячейку F6 для магазина 2:

=$F$3+$F$4+$F$5. (14)

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

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

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

6. В список Ограничения внесите числовые значения:

$B$3=80, $B$4=70, $B$5=120, $B$6=270, $D$6=170, $F$6=100. (15)

Добавьте требование на неотрицательность результата (количество товара не может выражаться отрицательным числом):

$D$3:$D$5>=0, $F$3:$F$5>=0 (16)

Выражения (9) – (15) ссылаются на одни и те же ячейки, задавая тем самым управляющие ограничения вычислительному процессу. По сути, это разделенные на части выражения:

$D$3+$F$3=80, $D$4+$F$4=70, $D$5+$F$5=120,

$B$3+$B$4+$B$5=270, $D$3+$D$4+$D$5=170, $F$3+$F$4+$F$5=100.

7. В поле Изменяя ячейки введите $D$3:$D$5 и $F$3:$F$5, отведенные под искомые значения доставленного товара в каждый из магазинов. При записи двух диапазонов их следует разделять точкой с запятой $D$3:$D$5;$F$3:$F$5. Щелкните по кнопке выполнить, и проанализируйте решение.

Если транспортная задача решается стороной, заинтересованной в увеличении транспортных затрат (например, фирмой-перевозчиком), то целевую функцию следует устремить к максимальному значению, установив в диалоговом окне Поиск решения переключатель Равной: на максимальное значение.