Линейное программирование пример задачи о диете

2.1. Задача о диете

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

Постановка задачи – первый и наиболее важный этап построения модели,
способный обеспечить правильное решение проблемы.

Даме необходимо похудеть, за помощью обратилась к подруге.

Построение модели – рассмотрение этого этапа и является главной целью.

Подруга посоветовала перейти на рациональное питание, состоящее из двух
продуктов P и Q.

Суточное питание этими продуктами должно давать не более 14 единиц жира
(чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р
написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150
калорий, а на упаковке с продуктом Q – 4
единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта
Р равна 15 руб., а 1 кг продукта Q – 25
руб.

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

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

Обозначим через х количество продукта Р и
через у количество продукта Q, требуемые
для выполнения условий диеты.

Количество единиц жира, содержащегося в х кг продукта
Р и в у кг продукта Q, равно
15х + 4 и по условию диеты не должно превосходить 14:

В свою очередь, количество калорий, содержащихся в х
кг продукта Р и в у кг продукта Q,
равно 150х + 200у и по условию диеты должно быть не меньше 300:

Теперь о стоимости z продуктов.
Она равна

и в соответствии с высказанными пожеланиями должна быть минимальной.

Последнее записывается так:

Тем самым мы получили систему формул:

которую решим графическим способом.

Нас интересует только та ее часть, которая лежит над треугольником
BDE. Вычисляя значения z
во всех трех вершинах этого треугольника

и сравнивая полученные результаты, замечаем, что наименьшее значение (35)
достигается в вершине Е. Таким образом,

и искомая пропорция – 2 : 3.

2.2. Задача о выпуске продукции

Фирма выпускает два вида древесно-стружечных плит – обычные и
улучшенные. При этом производится две основные операции – прессование и отделка.
Требуется указать, какое количество плит каждого типа можно изготовить в течение
месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на
ресурсы (материал, время, затраты):

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

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

Тогда ожидаемую прибыль можно записать так:

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

для которых

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

а затем, используя точку начала отсчета О(0, 0),
определить соответствующие полуплоскости. Пересечением полученных полуплоскостей
будет четырехугольник ОВМЕ.

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

Нам необходимо найти координаты точки М – точки
пересечения прямых EF и АВ, для этого надо
решить систему уравнений

Вычислить значения z в точках
В(0, 100), Е(150, 0), М(100, 50):

Из полученных значений выберем наибольшее и получим ответ:

2.3. Общая задача линейного программирования

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

Стандартная математическая формулировка общей задачи
линейного программирования выглядит так: требуется найти экстремальное значение
показателя эффективности (целевой функции)

(линейной функции элементов решения
) при линейных ограничительных
условиях, накладываемых на элементы решения:

где – заданные числа.

Что касается существующих методов решения этой задачи с
числом переменных, больших двух, то в их основе лежат те же идеи, на которые мы
опирались при разработке графического подхода. Конечно, в случае сильного
увеличения числа переменных и ограничений техника получения решения заметно
усложняется, но она опирается на совершенно стандартные, хорошо разработанные
алгоритмы (возникающие трудности связаны лишь с ростом объема необходимых
вычислений).

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

Правило сокращенного суммирования. Для обозначения
суммы чисел :

принята такая запись:

где ∑ – знак суммирования, а
k – индекс суммирования.

Это обозначение очень удобно:

А вот как выглядит запись общей задачи линейного
программирования:

2.4. Транспортная задача

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

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

Пример 1. Рассмотрим транспортную задачу, заданную таблицей

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

при условии, что

Положим и выразим через
t остальные переменные:
из первого уравнения: ,
из второго уравнения: ,
из третьего уравнения:

Тогда

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

Тем самым, мы получили условие .

Не трудно заметить, что при
t = 16.

Ответ:

Пример 2. Компания имеет два товарных склада и трех оптовых
покупателей. Известно, что общий объем запасов на складах составляет 300 тыс.
единиц продукции и совпадает с общим объемом заказов покупателей.

Обозначим через количество товара,
поставляемого со склада покупателю
.

Тогда соответствующая транспортная задача может быть
сформулирована следующим образом.

Минимизировать общую стоимость перевозок:

при условии, что

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

Положим и
выразим через u и
v остальные переменные. Имеем

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

которую можно решить графическим методом.

Выписанные неравенства определяют на плоскости (u,
v) пятиугольник с вершинами (30, 0), (70, 0), (70, 50), (0,
120), (0, 30).

Ответ:

В начало

МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ

КИРОВСКИЙ ФИЛИАЛ

Методы анализа данных

Методическое пособие и контрольные задания по темам

«Математическое программирование» c использованием табличного процессора Microsoft Excel

для студентов заочной формы обучения направления «Экономика»

Киров 2014г.

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

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

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

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

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

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

1) нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);

2) оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);

3) определение оптимального рациона (оптимизация состава химической смеси);

4) транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);

5) задача о размещении производства (планирование с учётом затрат на производство и транспортировку продукции);

6) задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.

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

                                       (1)

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

                             (2)

,

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

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

Задача об оптимальном составе смеси (задача составления рациона, задача о диете)

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

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

Таблица 1

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

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

                                (3)

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

                           (4)

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

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

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

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

1. открыть окно Microsoft Excel;

2. заполнить ячейкиA1-А4 таблицы обозначениями , ,  и min соответственно (см. рисунок 1);

Рисунок 1

3. в ячейку В4 записать формулу (4) через адреса соответствующих ячеек  (адреса ячеек вводятся щелчком мыши по соответствующей ячейке или набираются с клавиатуры на английской раскладке) (см. рисунок 2), нажать Enter;

Рисунок 2

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

Рисунок 3

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

Рисунок 4

6. в появившемся окне Поиск решения в поле Установить целевую ячейку надо щёлкнуть по кнопке , затем в ячейке B4 и снова по кнопке ; в поле Равной установить флажок (щёлкнуть левой кнопкой мыши в соответствующем кружке) минимальному значению, в поле Изменяя ячейки щёлкнуть по кнопке , выделить мышью диапазон ячеек В1¸В3 и снова щёлкнуть по кнопке  (см. рисунок 5);

Рисунок 5

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

Рисунок 6

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

Рисунок 7

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

Рисунок 8

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

Рисунок 9

11. Результат полученных вычислений представлен на рисунке 10.

Рисунок 10

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

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

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

Рисунок 11

Задача 2. В баре имеются три компонента: коньяк, шампанское, сок. Цель: подобрать оптимальный состав коктейля из этих трёх компонентов, если известно: 1. стоимости ингредиентов в рублях: , , ; 2. содержание алкоголя в промиллях , , ; 3. вкусовые качества в баллах , , . Крепость коктейля должна быть не меньше 0,2 промилле. Вкус должен иметь не менее 8 баллов.

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

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

                                              (5)

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

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

                                      (6)

Решим задачу 2 в программе Microsoft Excel. Для этого:

1. надо заполнить ячейки А1-А3 таблицы обозначениями , ,  и min соответственно (см. рисунок 12);

Рисунок 12

2. выполнить действия, аналогичные действиям, описанным в пунктах 3–9 (с учётом Замечания 1) Задачи 1, изменяться только ссылки на ячейки (см. рисунки 13-14):

                              Рисунок 13                          Рисунок 14

(в ячейку А7 введена формула: , в ячейку А8 введена формула: ), в результате чего окно Поиск решения будет выглядеть так, как представлено на рисунке 15, а решение задачи — на рисунке 16.

                             Рисунок 15                                    Рисунок 16

Замечание 5. Для того чтобы в решении задачи после запятой отображалось только 2 знака, надо выделить соответствующий диапазон ячеек, щёлкнуть на выделенном правой кнопкой мыши, в появившемся контекстном меню выбрать пункт Формат ячеек и на вкладке Число выбрать Числовой, указав Число десятичных знаков 2 (см. рисунок 17).

Рисунок 17

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

Решить задачу в Microsoft Excel.

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

Таблица 2