Линейное программирование. 1. Задачи линейного программирования и их свойства

1. Задачи линейного программирования и их свойства

Во многих областях практики возникают своеобразные задачи исследования операций отмеченными особенностями:

· показатель эффективности W есть линейная функция от элементарного решения ;

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

Запишем формулировки основных задач линейного программирования.

Задача о пищевом рационе:

Сельхоз предприятия производит откорм скота с коммерческой целью. Иметься 4 вида продуктов питания . Стоимость ед. продукта соответственно равна . Требуется составить пищевой рацион, который должен содержать:

· белков, не менее единиц;

· углеводов, не менее единиц;

· жиров, не менее единиц.

Для продуктов содержание жиров, белков, углеводов приведены в таблице:

Продукты	Элементы
Белки	Углеводы	Жиры

Пищевой рацион состоит таким образом что бы его стоимость была минимальной.

Решение:

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

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

Запишем ограничения по белкам, углеводам и жирам

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

Задача о загрузке оборудования

Каждая ткацкая фабрика имеет в наличии 2 вида станков; среди них - станков типа І, - станков II типа. Станки производят 3 типа тканей , но с разной производительностью. Станок типа І производит в месяц метров ткани , метров ткани , метров ткани. Можно составить таблицу для и

Станок	Тип ткани
Прибыль

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

Решения:

Математическая модель такой задачи:

Пусть - число станков типа занятых производством ткани . Таким образом получаем 6 переменных (необходимо выбрать таким образом, что бы прибыль была максимальной)

Станки не должны простаивать, поэтому

Кроме того, должны быть выполнено задание по ассортименту с учетом производительности станков

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

Задача о перевозках

Имеется 4 пункта отправления: в которых сосредоточенные запасы определенного вида груза в количествах Кроме того, имеется 3 пункта назначения Пункты подали заявки на единиц груза. Сума заявок равна суме имеющихся запасов, . Известна стоимость перевозки груза из пункта А в пункт В. Стоимость каждой перевозки будет начисляться: ;

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

Математическая модель задачи:

Пусть - количество единиц груза отправляемого из пункта в пункт назначения.

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

Так, как все запасы должны быть исчерпаны, то:

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

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

Формула записи задачи ЛП, которая ограниченная только равенствами называется стандартной формой, а сама задача называется задачей ЛП (ОЗЛП).