Лабораторная работа №1
(Теоретическая часть)
В общем случае задача линейного программирования (ЛП) формулируется следующим образом:
Найти 
при условиях: 
,
, 
Причем, систему ограничений вида неравенств 
и 
всегда можно свести к ограничениям типа равенства введением, так называемых, дополнительных переменных. Тогда, если предположить, что 
общую задачу ЛП можно представить в канонической форме: 
при ограничениях: 
, 
.
Случай нахождения 
отдельно не выделяется, т.к. он сводится к нахождению 
, причем 
. Для решения задач ЛП в частных случаях применяется графический метод 
. Универсальным методом решения задач ЛП является симплекс – метод, который непосредственно применяется к задаче в канонической форме. Допустимым решением называется любое неотрицательное решение , удовлетворяющее системе ограничений (*) типа равенств. Область допустимых решений ограничена выпуклым многоугольником. Вершины многоугольника называются базисным решением или опорным планом. Оптимальное решение ищется среди вершин многоугольника. Отсюда один из методов решения задач ЛП: Найти все вершины многоугольника решений, для чего надо решать большое количество простых систем из двух уравнений. Далее необходимо вычислить значение целевой функции в вершинах многоугольника и сравнить эти значения. Этот путь трудоемкий. Для решения задач ЛП используют универсальный метод – симплекс – метод. Суть симплекс – метода заключается в целенаправленном переборе вершин, в последовательном улучшении отправного базисного решения, вплоть до оптимального, за конечное число шагов. Причем метод дает схему упорядоченного перехода от одного базисного решения к другому.
Задача ЛП применяется в производстве для составления оптимального плана выпуска продукции, в планировании производства, в транспортной логистике и во многих других областях. Два математика, Канторович Леонид Витальевич и Леонтьев Василий Васильевич являются лауреатами Нобелевской премии по экономике. Математик Канторович Л.В. получил Нобелевскую премию в 1975 году «За вклад в теорию оптимального распределения ресурсов», является одним из создателей ЛП. Леонтьев В.В. является американским экономистом Российского происхождения, создатель теории межотраслевого анализа, получил Нобелевскую премию «За развитие метода затраты – выпуск и за его применение к важным экономическим проблемам».
Сформулируем прямую задачу ЛП.
Пусть 
– искомый план производства 
– го вида продукции, где 
; 
– доход, получаемый от реализации одной единицы продукции – го вида; 
– количество сырья 
– го вида, необходимое для изготовления продукции – го вида; 
– запасы – го вида сырья; 
.
В качестве целевой функции 
принимается суммарная прибыль, получаемая от реализации продукции, которая должна быть максимальной:
В математическую модель задачи включаются следующие ограничения:
1) Расход сырья каждого вида на выпуск суммарной продукции не должен превышать его запасов 
:
2) Количество продукции не может быть отрицательной величиной, т.е. 
, 
.
Двойственная задача
Припишем единице каждого 
- го вида сырья оценку 
. Эти оценки должны удовлетворять следующим условиям:
1) Общая оценка количества всех видов сырья, используемых в производстве должна быть минимальной:
2) Суммарная оценка всех видов сырья, расходуемого на выпуск единицы продукции любого вида, должна быть не ниже прибыли от реализации единицы продукции данного вида. В противном случае предприятие откажется от выпуска данного вида продукции. Оценка сырья – это количество прибыли, которую можно получить с единицы сырья. Математически ограничения двойственной задачи можно записать в следующем виде:
3) Оценки 
.
Такие задачи называют взаимно двойственными или парой двойственных задач. Можно решать прямую задачу на получение максимальной прибыли или двойственную на минимизацию общей стоимости имеющегося сырья. Между двойственными задачами можно установить следующие связи:
1) Если прямая задача на максимум, то двойственная к ней – на минимум и наоборот.
2) Коэффициенты 
целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.
3) Свободные члены 
ограничений прямой задачи являются коэффициентами целевой функции двойственной задачи.
4) Матрицы ограничений прямой и двойственной задач являются транспонированными друг другу.
5) Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Если двойственная задача решается на минимум, то ее система ограничений имеет вид неравенств типа .
Между решениями прямой и двойственной задачи имеется ряд важных соотношений:
1) Если одна из задач обладает оптимальным планом, то и другая задача обладает оптимальным планом, причем
2) Если целевая функция одной из задач двойственной пары не ограничена на множестве планов, то система ограничений другой – противоречива.
3) Положительную оценку имеют лишь те виды сырья, которые полностью используются в оптимальном плане:
Если 
то 
, 
4) Двойственные оценки характеризуют дефицитность используемого сырья. Большей оценке соответствует наиболее дефицитное сырье.
5) Если данный вид продукции вошел в оптимальный план, то оценка ресурсов, затрачиваемых на производство единицы продукции равна прибыли от ее реализации и производство рентабельно:
Если 
то 
,
6) Если 
, то в двойственной задаче 
- ое ограничение выполняется как неравенство. Оценка ресурсов, затрачиваемых на выпуск единицы этой продукции выше прибыли от ее реализации. Производство убыточно.
Двойственная задача возникает как задача оптимального использования ресурсов. Двойственные оценки ресурсов 
в зарубежной литературе называют теневыми оценками.
Величина двойственной оценки 
в оптимальном решении двойственной задачи численно равна изменению целевой функции при изменении соответствующего свободного члена 
системы ограничений прямой задачи на единицу:
При одновременном изменении ресурсов всех видов на величину 
можно оценить их суммарное влияние на значение целевой функции при условии неизменности двойственных оценок:
Таким образом, экономические свойства оценок 
оптимального плана следующие:
1) Мера дефицитности ресурсов и продукции.
2) Мера влияния ограничений на целевую функцию
3)Инструмент определения эффективности отдельных вариантов.
Двойственные оценки выступают как инструмент балансирования затрат и результатов, тем самым гарантируя рентабельность оптимального плана.
Изучить самостоятельно следующие вопросы:
1) Устойчивость оптимального плана на изменение стоимости продукции. В каких пределах могут меняться значения коэффициентов целевой функции 
,так чтобы оптимальный план оставался неизменным.
2) Интервалы устойчивости двойственных оценок по отношению к изменению количества сырья.