Лекция 3. Применение линейного программирования в математических моделях

в планировании и управлении
Задача линейного программирования
Симплексный метод
Экономические приложения линейного программирования
Программное

обеспечение линейного программирования

Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005.

— глава 2.
Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, 2001.
Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: Изд-во АН СССР, 1960.
Линейное программирование. Оптимальное распределение ресурсов. Методические указания для выполнения лабораторных работ для студентов направлений подготовки бакалавриата 120700, 080100 и 080200./НМСУ «Горный». Сост. В.В. Беляев, Т.Р. Косовцева. СПб, 2012., 62 с.

в семье врача. В 18 лет он закончил математико-механический факультет

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

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

определённых ресурсов
наличие определённых технологических возможностей
цель хозяйственной деятельности
извлечение прибыли
удовлетворение потребностей
предотвращение угрозы
накопление

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

материалов;
задачи составления смесей;
задачи оптимизации раскроя;
оптимизации производственной программы предприятий;
оптимального размещения и

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

неотрицательности переменных

ограни-чения
(фазовые ограничения)
Условия неотрицательности переменных (естественные ограничения)
Любую ЗЛП можно записать в

каноническом виде (ограничения – равенства, свободные члены неотрицательны, решается на максимум)

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

принадлежит этому множеству.

/23

некоторое ограничение (например, первое) было неравенством, то оно преобразуется в

равенство, введением в левую часть некоторой неотрицательной переменной, причем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»
a11x1+a12x2+...+a1nxn<=b1
Вводим переменную
xn+1=b1-a11x1-a12x2+...+a1nxn.
Тогда неравенство запишется в виде:
a11x1+a12x2+...+a1nxn +xn+1=b1
В каждое из неравенств вводится своя "уравнивающая” переменная, после чего система ограничений становится системой уравнений.

/23

неотрицательности, то ее заменяют (в целевой функции и во всех

ограничениях) разностью неотрицательных переменных
Xk=Xk-Xl
где: Xk>=0, Xl>=0
l - свободный индекс
3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)

4. Если исходная задача была задачей на минимум, то введением новой целевой функции 
F1 = -F
мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F1.

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

/23

целевая функция
Линейные ограни-чения
Условия неотрицательности переменных

неотрицательности переменных

целевой функции), называется допустимым решением
Если допустимых решений не существует, говорят,

что система ограничений несовместна
Областью допустимых решений (ОДР) называется множество, включающее все допустимые решения данной ЗЛП
Допустимое решение x*, доставляющее наибольшее значение целевой функции среди всех допустимых решений данной ЗЛП, называется оптимальным решением
часто его называют просто решением ЗЛП

– система ограничений не совместна
z = max(x1+x2|x1+5x2  1, x1+x2

 5, x1  0, x2  0)
допустимая область существует, но не ограничивает целевую функцию
z = max(2x1+x2|0.1x1+0.1x2  5, x1  0, x2  0)
иметь одно оптимальное решение
z = max(x1+x2|0.1x1+0.2x2  5, x1  0, x2  0)
x1=50, x2 =0; z = 50
иметь бесконечно много оптимальных решений
z = max(x1+x2|0.1x1+0.1x2  5, x1  0, x2  0)
x1=50, x2 =0; z = 50 … x1=0, x2 =50; z = 50

Компактная запись

0)
x1=50, x2 =0; z = 50

0)
x1=50, x2 =0; z = 50 … x1=0, x2

=50; z = 50

0, x2  0)
Несовместность системы ограничений

0)
Неограниченность целевой функции

и привести ее к каноническому виду.
Для откорма животных употребляют два

вида кормов; стоимость 1 кг корма I вида - 5 у.е., а корма - II вида 2 у.е. В каждом килограмме корма I вида содержится 5 ед. питательного вещества  А, 2.5 ед. питательного вещества B и 1 ед. питательного вещества C. В каждом килограмме корма II вида содержится соответственно 3, 3 и 1.3 ед. Суточный рацион предусматривает питательных единиц  A не менее 225 ед., типа B - не менее 150 ед. и типа C - не менее 80 ед. Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты были минимальны?

Нобелевская премия за труды по теории экономического регулирования (совсем не

проблемы линейного программирования!)
Еще в 1945 г. без помощи линейного программирования ДЖОРДЖ СТИГЛЕР. составил "самый дешевый набор продуктов", явившийся фактически прообразом потребительской корзины.
Пытался найти наиболее дешевый рацион, удовлетворяющий 9 диетическим требования, сформулированным в 1943 году. В наборе продуктов было 77 наименований, от пшеничной муки до клубничного джема.
Подводя итоги своей работы в 1945 «Затраты на питание» :
«По всей видимости не существует универсального метода нахождения минимума линейной функции при «соблюдении линейных ограничений.
Разработав в конце 40-х годов симплекс-метод, Георг Данциг совершил переворот. 70 лет назад решение задачи составления рациона вызывало затруднения у лучших экономистов мира, теперь доступно для начинающих студентов.

форме
Её ограничения линейно независимы
Известно опорное решение, в котором:
имеется не

более m ненулевых переменных
задача содержит n переменных и m ограничений
все ограничения выполняются
m переменных, называемых базисными (среди которых все ненулевые)
выражены через:
n–m переменных, называемых свободными (каждая равна нулю)
свободный член ограничения
Результат этой процедуры записан в начальную (первую, исходную) симплексную таблицу

задачу симплексным методом необходимо выполнить следующее:
Привести задачу к каноническому виду
Найти

начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

/23

0, x2  0)
x1=50, x2 =0; z = 50
Каноническая

форма:
max x1+x2
0.1x1+0.2x2+x3 = 5
x1–2x2 +x4 = 75
x1  0, x2  0, x3  0, x4  0

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

cj нет, достигнут оптимум
Разрешающая строка:
для всех положительных aij в выбранном

столбце считаем bi /aij
если положительных нет, ц.ф. не ограничена
выбираем строку, где это значение минимально

: aijнов = aij – ai'jaij' /ai'j' , где
i' и

j' – координаты выбранных (разрешающих) строки и столбца
для строки i =i' : aijнов = aij /ai'j'

Отрицательных cj больше нет – достигнут оптимум (в больших задачах для этого требуются тысячи итераций)

проблемы описаны в рекомендуемой литературе.

задачи ui (двойственная переменная).
Каждой j-ой переменной исходной задачи соответствует ограничение

двойственной задачи. Матрица коэффициентов ограничений двойственной задачи является транспонированной

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

Если исходная задача была на нахождение максимума, то двойственная будет на нахождение минимума

двойственные переменные принято называть двойственными оценками Ui

задач совпадают
Двойственная оценка называется теневой ценой теневая цена ui

является коэффициентом при bi => показывает, как изменится целевая функция при изменении i-го ресурса на единицу.

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

(2.2) - система ограничений; (2.3) - естественные граничные условия;

единичного объёма производства в каждой отрасли.

Строки – ресурсы, столбцы –

отрасли.

Объёмы невоспроизводимых ресурсов (земельные угодья, трудовые ресурсы, запасы полезных ископаемых и т.п.), имеющиеся в распоряжении народного хозяйства

Матрица затрат (+) и выпуска (-) ресурсов при единичном объёме производства в каждой отрасли.

Строки – ресурсы, столбцы – отрасли.

Вектор, состоящий из нулей

Матрица выпуска (+) конечной продукции при единичном объёме производства в каждой отрасли.

Строки – виды продукции, столбцы – отрасли.

Вектор объёмов потребления каждого вида конечной продукции при единичном (стандартном) уровне удовлетворения потребностей

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

руб./ед.
Вектор цен ресурсов (включая НДС), руб./ед.
Матрица затрат ресурсов на производство

и реализацию единицы продукции, ед.рес./ед.прод.

Вектор наличия (начальных запасов) ресурсов

Матрица объёмов обязательств, выполняемых вследствие реализации единицы продукции каждого вида

Объёмы обязательств, имеющихся у предприятия и учитываемых при оптимальном планировании (выполнение которых зависит от составленного плана)

обеспечение линейного программирования
Запуск решения – [Ctrl]+[x]
Найти XA

туда файлы CXA32.DLL и CAXA32.DLL
Иначе
копируем файлы CXA32.DLL и CAXA32.DLL в

ту папку, в которой решаем модель
после вызова файла модели нажимаем кнопку и указываем расположение любого из этих файлов
это действие повторяется при каждом вызове Excel
Антивирус Касперского блокирует выполнение XA
При первом вызове программы следует в ответ на предупреждение антивируса дать ему указание разрешать выполнение данной программы

Найти XA