2014-02-24
479
1. Задачи линейного программирования и их свойства
Во многих областях практики возникают своеобразные задачи исследования операций отмеченными особенностями:
· показатель эффективности W есть линейная функция от элементарного решения 
;
· ограничительное условие, полагаемая на элементарные решения имеют вид линейных равенств или неравенств. Такие задачи являются задачами линейного программирования.
Запишем формулировки основных задач линейного программирования.
Задача о пищевом рационе:
Сельхоз предприятия производит откорм скота с коммерческой целью. Иметься 4 вида продуктов питания 
. Стоимость ед. продукта соответственно равна 
. Требуется составить пищевой рацион, который должен содержать:
· белков, не менее 
единиц;
· углеводов, не менее 
единиц;
· жиров, не менее 
единиц.
Для продуктов 
содержание жиров, белков, углеводов приведены в таблице:
| Продукты | Элементы | ||
| Белки | Углеводы | Жиры | |
| 
| 
| 
|
Пищевой рацион состоит таким образом что бы его стоимость была минимальной.
Решение:
1. Составить математическую модель:
Пусть 
- количество продуктов , входящих в рацион. Тогда стоимость рационального питания (показатель эффективности) равен:
Запишем ограничения по белкам, углеводам и жирам
Ограниченное количество элементов. Поставлена задача сводится к тому чтобы найти 
при которому себестоимость рационализации была минимальная.
Задача о загрузке оборудования
Каждая ткацкая фабрика имеет в наличии 2 вида станков; среди них 
- станков типа І, 
- станков II типа. Станки производят 3 типа тканей 
, но с разной производительностью. Станок типа І производит в месяц 
метров ткани 
, 
метров ткани 
, 
метров ткани
. Можно составить таблицу для и
| Станок | Тип ткани | ||
|
|
|
| |
|
|
|
|
|
Прибыль 
| 
| 
| 
|
Фабрикой приписан план производительности за месяц метров ткани 
. Требуется так распределить загрузку станков что бы план был выполнен, станки не простаивали и суммарная прибыль была максимальная.
Решения:
Математическая модель такой задачи:
Пусть 
- число станков типа 
занятых производством ткани 
. Таким образом получаем 6 переменных 
(необходимо выбрать таким образом, что бы прибыль была максимальной)
Станки не должны простаивать, поэтому
Кроме того, должны быть выполнено задание по ассортименту с учетом производительности станков
Поставленная задача сводиться к тому, что бы получить такие неотрицательные значения переменных удовлетворяющие ограниченные условием по загрузке и ассортименту, а целевая функция обращалась в максимум.
Задача о перевозках
Имеется 4 пункта отправления: 
в которых сосредоточенные запасы определенного вида груза в количествах 
Кроме того, имеется 3 пункта назначения 
Пункты подали заявки на 
единиц груза. Сума заявок равна суме имеющихся запасов, 
. Известна стоимость перевозки груза из пункта А в пункт В. Стоимость каждой перевозки будет начисляться: 
; 
Требуется составить такой план перевозок (какое количество груза откуда и куда отправить) при котором суммарные перевозки обращаются в минимум.
Математическая модель задачи:
Пусть - количество единиц груза отправляемого из 
пункта в 
пункт назначения.
Запишем ограничения налягаемые на элементы решения. Ограничения записываем с учетом того, что все заявки должны быть выполнены.
Так, как все запасы должны быть исчерпаны, то:
Требуется выбрать такие неотрицательные значения переменных что бы выполнялись все заданные выше ограничения и при этом целевая функция обращалась в минимум. Основными особенностями ограничительных условий записанных в задаче является то, что в первуй задаче ограничения имели вид линейных неравенств, во второй – линейных неравенств и равенств, а в третей – только равенств.
Однако любую задачу линейного программирования с условиями - неравенства можно свести к задаче с условными равенствами путем введения остаточных или избыточных переменных.
Формула записи задачи ЛП, которая ограниченная только равенствами называется стандартной формой, а сама задача называется задачей ЛП (ОЗЛП).
