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

↑

⇐ ПредыдущаяСтр 6 из 28Следующая ⇒

Отметим, что существует путь из каждого узла i (i = 1, 2, 3, 4)

в любой другой узел / при условии, если j > i. Этот путь (или мар-

шрут) может проходить либо по одной дуге, непосредственно соеди-

няющей рассматриваемые узлы, либо по ряду дуг через промежуточ-

ные узлы, если j— i > 1. Допустим, что с перемещением вдоль каждой дуг(i, j) связаны соответственно затраты Cij . Представим себе фирму, занимающуюся перевозкой грузов. Предположим, что данной фирме необходимо взять в аренду на четыре года определенное количество транспортных средств. Фирма может удовлетворить свои потребности, взяв нужное количество транспортных средств в аренду ровно на четыре года

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

Затраты, связанные с использованием наиболее дешевого маршрута. Пусть Yi — затраты, связанные с использованием наиболее дешевого маршрута от узла i до узла 5, где i принимает одно из значений i = 1, 2, 3, 4. Можно определить Yi, подсчитав затраты для прямого маршрута от узла 1 до узла j(j> i) и прибавив к ним затраты для оптимального маршрута от узла j до узла 5. Наименьшие из всех производимых при этом затрат определяют значение Yi. Математически это можно сформулировать следующим образом:

Таким образом, затраты в случае выбора наиболее дешевого маршру-

та от узла 1 до узла 5 можно определить, если известны затраты,

связанные с использованием наиболее дешевых маршрутов от узла 2

до узла 5, от узла 3 до узла 5 и от узла 4 до узла 5. Следовательно,

в этом случае задача сводится к сравнению затрат, связанных с исполь-

зованием прямого маршрута от узла 1 до узла 5, с затратами при

использовании маршрута от узла 1 через каждый из промежуточных

маршрутов и выбору наилучшего пути от узла 1 до узла 5.

С точки зрения линейного программирования задача заключается

в том, чтобы максимизировать  при ограничениях

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

Наложим ограничение Для нахождения наилучшего марш-

рута (пути) рассмотрим единичный поток, исходящий из узла 1

и входящий в остальные узлы:

 (8)

Будем считать, что все потоки, входящие в узлы 2, 3 и 4, должны вытекать из них с последующим втеканием в узел с более высоким порядковым номером:

(9)

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

что с помощью знака можно записать кратко в виде двойной суммы

Задача заключается в том, чтобы минимизировать

 (10).Таким образом, необходимо найти неотрицательные значения удовлетворяющие (8), (9) и (10).

Задача о смесях
В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д. Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы.
Пример. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов. Содержание в 1 кг. каждого вида комбикорма жиров белков и углеводов (граммы) приведено в таблице:

Содержание
в 1 кг.

Комбикорм

А

В

С

Жиры

Белки

Углеводы

Стоимость 1 кг

 Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость?
Математическая модель задачи есть:
- количество комбикорма А,В и С. Стоимость смеси есть: Ограничения на количество ингредиентов:

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры