Построение математических моделей задач ЛП

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

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

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

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

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

Задачи, решаемые методами ЛП очень разнообразны по содержанию, но их математические модели схожи и их условно можно объединить в три большие группы задач:

- транспортные задачи;

- задачи о составлении плана;

- задачи о раскрое, смесях.

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

Задача 1 (сбалансированная транспортная задача).

На двух вокзалах А и В имеются 30 групп туристов, по 15 на каждом. Их требуется доставить в две гостиницы С и Д, причем в С надо доставить 10 групп, а в Д – 20 . Известно, что доставка одной группы с вокзала А в гостиницу С обходится в 1 д.е, в Д – в 3 д.е., с вокзала В в гостиницы С и Д соответственно, 2 и 5 д.е. Составить план перевозок так, чтобы стоимость всех перевозок была наименьшей.

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

Таблица 2.1

Гостиницы Вокзалы С Д Необходимо отправить
А
В
Необходимо принять

Составим математическую модель задачи.

Необходимо ввести переменные. В формулировке вопроса говорится, что необходимо составить план перевозок. Обозначим через Построение математических моделей задач ЛП - student2.ru количество групп, перевозимых с вокзала А в гостиницы С и Д соответственно, а через Построение математических моделей задач ЛП - student2.ru – количество групп, перевозимых с вокзала В в гостиницы С и Д соответственно. Тогда количество групп, вывозимое с вокзала А, равно Построение математических моделей задач ЛП - student2.ru , а с вокзала В: Построение математических моделей задач ЛП - student2.ru . Потребность гостиницы С равна 10 группам и в нее привезли Построение математических моделей задач ЛП - student2.ru т. е. Построение математических моделей задач ЛП - student2.ru . Аналогично, для гостиницы Д, имеем Построение математических моделей задач ЛП - student2.ru . Заметим, что потребности гостиниц в точности равны количеству вывозимых групп, поэтому Построение математических моделей задач ЛП - student2.ru и Построение математических моделей задач ЛП - student2.ru .

Итак, заметим, что переменные Построение математических моделей задач ЛП - student2.ru по смыслу задачи неотрицательны и удовлетворяют системе ограничений:

Построение математических моделей задач ЛП - student2.ru (1)

Обозначив, через целевую функцию F – транспортные расходы, посчитаем их. На перевозку одной группы туристов из А в С тратится 1 д.ед., на перевозку x1 групп – x1 д.ед. Аналогично, на перевозку x2 групп из А в Д тратится 3x2 д.ед.; из В в С: 2y1 д.ед., из В в Д: 5y2 д.ед. Мы хотим, чтобы общая стоимость перевозок была минимальной. Итак,

Построение математических моделей задач ЛП - student2.ru . (2)

Сформулируем задачу математически: на множестве решений системы ограничений (1) необходимо найти такое решение, которое обращает в минимум целевую функцию F (2); или найти оптимальный план Построение математических моделей задач ЛП - student2.ru , определяемый системой ограничений (1) и целевой функцией (2).

Задача, которую мы рассмотрели, может быть представлена в более общем виде, с любым числом поставщиков и потребителей.

В рассмотренной нами задаче наличие груза у поставщиков (15+15) равно общей потребности потребителей (10+20). Такая модель называется закрытой, а соответствующая задача – сбалансированной транспортной задачей.

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

Рассмотрим пример несбалансированной транспортной задачи.

Задача 2 (несбалансированная транспортная задача).

В пунктах А и В расположены текстильные комбинаты по производству тканей, а в С и Д склады, обеспечивающие эти комбинаты сырьем. Потребность этих комбинатов в сырье меньше, чем возможности складов. Известно, сколько сырья нужно каждому из комбинатов и какова возможность складов. Также известна стоимость перевозки 1 тонны сырья из каждого склада к комбинату (числа на стрелочках). Нужно так спланировать снабжение комбинатов сырьём, чтобы затраты на перевозку были наименьшими. Данные задачи изображены на схеме.

Построение математических моделей задач ЛП - student2.ru Построим математическую модель задачи. Введем переменные:

Построение математических моделей задач ЛП - student2.ru количество сырья, перевозимого со склада С на комбинат А;

Построение математических моделей задач ЛП - student2.ru со склада С на комбинат В;

Построение математических моделей задач ЛП - student2.ru из Д в А;

Построение математических моделей задач ЛП - student2.ru из Д в В.

На комбинат А должно быть поставлено 40 тонн с обоих складов, значит, Построение математических моделей задач ЛП - student2.ru на комбинат В должно быть доставлено 50 тонн, значит, Построение математических моделей задач ЛП - student2.ru Задача не сбалансирована, т.к. 40+50<70+30. Со склада С должно быть вывезено не более 70 тонн, т.е. Построение математических моделей задач ЛП - student2.ru аналогично из Д: Построение математических моделей задач ЛП - student2.ru Имеем систему ограничений:

Построение математических моделей задач ЛП - student2.ru (3)

Целевая функция F, выражающая стоимость перевозок, имеет вид

Построение математических моделей задач ЛП - student2.ru (4)

Задача 3 (о составлении плана выпуска при определенной загрузке оборудования).

Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. за изделие II вида. Составить план выпуска этих изделий так, чтобы от реализации их завод получил наибольшую прибыль. В таблице 2.2 указано время, необходимое для обработки каждого из двух видов изделий на оборудовании всех четырех видов.

Таблица 2.2

Изделия Виды машин
I 0,5
II
Возможное время работы машин

Построим математическую модель. Построение математических моделей задач ЛП - student2.ru

В задаче необходимо определить план выпуска изделий, обозначим за Построение математических моделей задач ЛП - student2.ru количество изделий I вида, за Построение математических моделей задач ЛП - student2.ru количество изделий II вида. Тогда определим, сколько времени затратит 1-я машина на обработку всех изделий. Она тратит 1 ед. времени на 1 изделие типа I, значит, на Построение математических моделей задач ЛП - student2.ru штук изделий потратит Построение математических моделей задач ЛП - student2.ru ед. времени, на обработку Построение математических моделей задач ЛП - student2.ru изделий типа II затратится Построение математических моделей задач ЛП - student2.ru ед. времени. Всего резерв времени работы 1-й машины 18 ед. времени. Значит, Построение математических моделей задач ЛП - student2.ru Аналогичные рассуждения со 2-й машиной, 3-й и 4-й дадут систему ограничений:

Построение математических моделей задач ЛП - student2.ru (5)

Общая прибыль будет выражена целевой функцией:

Построение математических моделей задач ЛП - student2.ru . (6)

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

Еще одна распространенная задача ЛП – задача о составлении смеси. Примером таких задач может быть задача о составлении таких смесей нефтепродуктов, которые бы удовлетворяли определенным техническим требованиям и были наиболее дешевыми по стоимости. Задача о раскрое, в которой решается вопрос о способах получения определенного количества заготовок нескольких видов из имеющихся однородных листов, с целью минимизации количества этих листов или отходов при раскрое, тоже имеет модель этого типа. Рассмотрим задачу о рационе, когда известны потребность в определенных веществах и содержание этих веществ в различных продуктах. Необходимо составить рацион так, чтобы удовлетворить потребности в необходимых веществах и при этом продуктовая корзина имела бы минимальную стоимость при заданных ценах на продукты.

Задача 4 (о рационе).

Необходимо составить рацион, включающий не менее 33 единиц вещества А, не менее 23 единиц питательного вещества В, не менее 12 единиц С. Для этого используются 3 вида продуктов. Данные о содержании питательных веществ в каждом виде продукта заданы таблицей 2.3. Также известны стоимости одной единицы каждого продукта. Нужно составить наиболее дешевый рацион.

Таблица 2.3

продукты Вещества Стоимость 1 ед. продукта
А В С
I
II
III

Для понимания задачи можете представить себе, что вещества А, В, С – это жиры, белки, углеводы, а продукты I, II, III. Тогда первая строка таблицы показывает содержание в 1 ед. продукта I: 4 ед. белка, 3 ед. жиров, 1 ед. углеводов; вторая строка содержание белков, жиров, углеводов в 1 ед. продукта II и т. д.

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

Обозначим за Построение математических моделей задач ЛП - student2.ru количество продуктов вида I в рационе, за Построение математических моделей задач ЛП - student2.ru количество продуктов вида II, и соответственно Построение математических моделей задач ЛП - student2.ru количество III-го вида продукта в рационе. Тогда, вещества А при потреблении продуктов типа I получается Построение математических моделей задач ЛП - student2.ru , при потреблении II вида продукта – Построение математических моделей задач ЛП - student2.ru , при потреблении III – Построение математических моделей задач ЛП - student2.ru Всего вещества А необходимо употребить по условию задачи не менее 33 единиц, следовательно: Построение математических моделей задач ЛП - student2.ru . Аналогично рассуждая с веществом В, имеем: Построение математических моделей задач ЛП - student2.ru и Построение математических моделей задач ЛП - student2.ru для С.

Таким образом, получим систему ограничений:

Построение математических моделей задач ЛП - student2.ru (7)

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

Построение математических моделей задач ЛП - student2.ru т. к. 20, 20, 10 – стоимость одной единицы продуктов I, II, III типов соответственно, а в рационе их содержится Построение математических моделей задач ЛП - student2.ru единиц.

Система ограничений (7) и целевая функция составляют математическую модель исходной задачи. Решить ее, значит, найти такие Построение математических моделей задач ЛП - student2.ru , удовлетворяющие системе ограничений и обращающие значение функции F в минимальное.

Задача 5 (о раскрое).

Пусть из заготовок для замков-молний длиной 1 метр выпускаются замочки размером 12 см, 18 см и 35 см. Известны различные варианты раскроя метровых заготовок на замочки и остатки для каждого варианта. Также заданы минимальные потребности в замочках каждой длины. Необходимо определить: сколько заготовок нужно раскроить по каждому возможному варианту раскроя, чтобы получить необходимое количество замочков, при этом количество отходов должно быть минимальным.

Рассмотрим несколько возможных вариантов раскроя (в таблице 2.4 указано три), заметьте, что перечислены не все.

Таблица 2.4

Типы замков-молний Варианты раскроя Потребности в замках
12 см
18 см
35 см
отходы  

Построение модели.

Обозначим за Построение математических моделей задач ЛП - student2.ru – количество метровых заготовок, раскраиваемых по 1-му варианту, за Построение математических моделей задач ЛП - student2.ru – количество метровых заготовок, раскраиваемых по 2-му варианту, за Построение математических моделей задач ЛП - student2.ru – количество метровых заготовок, раскраиваемых по 3-му варианту.

Тогда посчитаем количество замков:
длиной 12 см: Построение математических моделей задач ЛП - student2.ru
длиной 18 см: Построение математических моделей задач ЛП - student2.ru (8)
длиной 35 см: Построение математических моделей задач ЛП - student2.ru

Общее количество отходов определяет целевую функцию:

Построение математических моделей задач ЛП - student2.ru

Система ограничений (8) вместе с целевой функцией составляют математическую модель задачи о раскрое.

Наши рекомендации