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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.1

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

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

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

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

( 1)

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

. (2)

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

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

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

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

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

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

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

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

количество сырья, перевозимого со склада С на комбинат А;

со склада С на комбинат В;

из Д в А;

из Д в В.

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

(3)

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

(4)

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

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

Таблица 2.2

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

Построим математическую модель.

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

(5)

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

. (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 и т. д.

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

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

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

(7)

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

т. к. 20, 20, 10 – стоимость одной единицы продуктов I, II, III типов соответственно, а в рационе их содержится единиц.

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

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

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

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

Таблица 2.4

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

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

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

Тогда посчитаем количество замков:
длиной 12 см:
длиной 18 см: (8)
длиной 35 см:

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

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