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

Содержание

1. Применение линейного программирования в математических моделях
2. /23ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие
3. /233.1. Принцип оптимальности в планировании и управленииПринцип
4. /233.2. Задача линейного программированияЭто развёрнутая форма записиЛинейная
5. /233.2. Задача линейного программированияЭто каноническая форма записиЛинейная
6. /233.2. Задача линейного программированияЭто матричная форма записиОна
7. /233.2. Задача линейного программированияЭто стандартная форма записиЛинейная
8. /233.2.Любой вектор x, удовлетворяющий ограничениям и условиям
9. /233.2.ЗЛП может:не иметь ни одного оптимального решениядопустимой
10. /233.2.z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1 ≥
11. /233.2.z = max(x1+x2|0.1x1+0.1x2 ≤ 5, x1 ≥
12. /233.2.z = max(x1+x2|x1+5x2 ≤ 1, x1+x2 ≥
13. /233.2.z = max(2x1+x2|0.1x1+0.1x2 ≥ 5, x1 ≥
14. /233.3. Симплексный методИсходные условия применения симплексного методаЗЛП
15. /233.3.z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1–2x2 ≤
16. /23В таблице выделены жирным шрифтом3.3.Разрешающий столбец:столбец с
17. /233.3.Выполняем обыкновенные жордановы исключения во всей таблице:для
18. /233.3.Опорное решение может быть получено по следующей
19. /233.3.В некоторых случаях алгоритм симплексного метода может
20. /233.4. Экономические приложения линейного программированияМатрица потребности в
21. /233.4. Экономические приложения линейного программированияВектор цен продукции
22. Применение линейного программирования в математических моделях (с)
23. /233.5.Два способа установки XAЕсли есть права доступа
24. Скачать презентанцию

/23ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — глава 2.Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая

Главная
Информатика
Применение линейного программирования в математических моделях

Слайды и текст этой презентации

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

Принцип оптимальности

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

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

/23Лекция 3. Применение линейного программирования в математических моделяхСодержание лекции:Принцип оптимальности в планировании и управленииЗадача линейного программированияСимплексный методЭкономические

Слайд 2/23
Литература
Экономико-математические методы и прикладные модели: Учеб. пособие для вузов /

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

— глава 2.
Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, 2001.
Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: Изд-во АН СССР, 1960.
Светлов Н.М., Светлова Г.Н. Построение и решение оптимизационных моделей средствами программ MS Excel и XA: Методические указания для студентов экономического факультета / РГАУ – МСХА имени К.А. Тимирязева. М., 2005. http://svetlov.timacad.ru/umk1/xa_1.doc

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

/23ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд.

Слайд 3/23
3.1. Принцип оптимальности в планировании и управлении
Принцип оптимальности предполагает следующее:
наличие

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

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

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

/233.1. Принцип оптимальности в планировании и управленииПринцип оптимальности предполагает следующее:наличие определённых ресурсовналичие определённых технологических возможностейцель хозяйственной деятельностиизвлечение

Слайд 4/23
3.2. Задача линейного программирования
Это развёрнутая форма записи
Линейная целевая функция
Линейные ограни-чения

Условия

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

/233.2. Задача линейного программированияЭто развёрнутая форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия неотрицательности переменныхПрименение линейного программирования в математических моделях

Слайд 5/23
3.2. Задача линейного программирования
Это каноническая форма записи
Линейная целевая функция
Линейные ограни-чения
Условия

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

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

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

/233.2. Задача линейного программированияЭто каноническая форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия неотрицательности переменныхЛюбую ЗЛП можно записать в каноническом

Слайд 6/23
3.2. Задача линейного программирования
Это матричная форма записи
Она тождественна канонической форме
Линейная

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

Н.М. Светлов, 2007-2011

/233.2. Задача линейного программированияЭто матричная форма записиОна тождественна канонической формеЛинейная целевая функцияЛинейные ограни-ченияУсловия неотрицательности переменныхПрименение линейного программирования

Слайд 7/23
3.2. Задача линейного программирования
Это стандартная форма записи
Линейная целевая функция
Линейные ограни-чения
Условия

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

/233.2. Задача линейного программированияЭто стандартная форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия неотрицательности переменныхПрименение линейного программирования в математических моделях

Слайд 8/23
3.2.
Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности (безотносительно к

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

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

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

/233.2.Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности (безотносительно к целевой функции), называется допустимым решениемЕсли допустимых решений

Слайд 9/23
3.2.
ЗЛП может:
не иметь ни одного оптимального решения
допустимой области не существует

– система ограничений не совместна
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

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

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

/233.2.ЗЛП может:не иметь ни одного оптимального решениядопустимой области не существует – система ограничений не совместнаz = max(x1+x2|x1+5x2

Слайд 10/23
3.2.
z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1 ≥ 0, x2 ≥

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

Применение линейного программирования в

математических моделях © Н.М. Светлов, 2007-2011

/233.2.z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1 ≥ 0, x2 ≥ 0) x1=50, x2 =0; z = 50Применение

Слайд 11/23
3.2.
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

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

/233.2.z = max(x1+x2|0.1x1+0.1x2 ≤ 5, x1 ≥ 0, x2 ≥ 0) x1=50, x2 =0; z = 50

Слайд 12/23
3.2.
z = max(x1+x2|x1+5x2 ≤ 1, x1+x2 ≥ 5, x1 ≥

0, x2 ≥ 0)
Несовместность системы ограничений
Применение линейного программирования в математических

моделях © Н.М. Светлов, 2007-2011

/233.2.z = max(x1+x2|x1+5x2 ≤ 1, x1+x2 ≥ 5, x1 ≥ 0, x2 ≥ 0)Несовместность системы ограниченийПрименение линейного

Слайд 13/23
3.2.
z = max(2x1+x2|0.1x1+0.1x2 ≥ 5, x1 ≥ 0, x2 ≥

0)
Неограниченность целевой функции
Применение линейного программирования в математических моделях © Н.М. Светлов,

2007-2011

/233.2.z = max(2x1+x2|0.1x1+0.1x2 ≥ 5, x1 ≥ 0, x2 ≥ 0)Неограниченность целевой функцииПрименение линейного программирования в математических

Слайд 14/23
3.3. Симплексный метод
Исходные условия применения симплексного метода
ЗЛП записана в канонической

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

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

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

/233.3. Симплексный методИсходные условия применения симплексного методаЗЛП записана в канонической формеЕё ограничения линейно независимыИзвестно опорное решение, в

Слайд 15/23
3.3.
z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1–2x2 ≤ 75, x1 ≥

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

/233.3.z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1–2x2 ≤ 75, x1 ≥ 0, x2 ≥ 0) x1=50, x2

Слайд 16/23
В таблице выделены жирным шрифтом
3.3.
Разрешающий столбец:
столбец с наибольшим положительным cj
если положительного cj нет,

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

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

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

/23В таблице выделены жирным шрифтом3.3.Разрешающий столбец:столбец с наибольшим положительным cjесли положительного cj нет, достигнут оптимумРазрешающая строка:для всех

Слайд 17/23
3.3.
Выполняем обыкновенные жордановы исключения во всей таблице:
для строк i ≠i'

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

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

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

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

/233.3.Выполняем обыкновенные жордановы исключения во всей таблице:для строк i ≠i' : aijнов = aij – ai'jaij' /ai'j'

Слайд 18/23
3.3.
Опорное решение может быть получено по следующей процедуре:

Выбираем произвольный набор

базисных переменных и выражаем их через свободные
Если строк с отрицательными

свободными членами нет – опорное решение получено; иначе – п.3.
Одну из таких строк выбираем в качестве вспомогательной целевой функции и проводим по ней процедуру решения на минимум, используя алгоритм симплекс-метода
Если в качестве разрешающей выбирается строка с отрицательным свободным членом, то разрешающий элемент тоже должен быть отрицательным
для всех aij в выбранном столбце считаем bi /aij
наименьшее положительное значение этого отношения указывает разрешающую строку
если положительных нет, выбираем другую строку с отрицательным свободным членом в качестве вспомогательной целевой функции
если таковых не находится, опорных решений не существует (целевая функция не ограничена множеством допустимых решений)
Если оптимум достигнут при отрицательном свободном члене – система ограничений несовместна; иначе – п.5
Как только достигнуто положительное значение свободного члена, переходим к п.2.

/233.3.Опорное решение может быть получено по следующей процедуре:Выбираем произвольный набор базисных переменных и выражаем их через свободныеЕсли

Слайд 19/23
3.3.
В некоторых случаях алгоритм симплексного метода может зацикливаться.
Пути преодоления этой

Н.М. Светлов, 2007-2011

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

Слайд 20/23
3.4. Экономические приложения линейного программирования
Матрица потребности в ресурсах для обеспечения

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

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

отрасли.

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

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

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

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

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

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

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

/233.4. Экономические приложения линейного программированияМатрица потребности в ресурсах для обеспечения единичного объёма производства в каждой отрасли.Строки –

Слайд 21/23
3.4. Экономические приложения линейного программирования
Вектор цен продукции (за вычетом НДС),

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

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

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

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

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

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

Слайд 22Применение линейного программирования в математических моделях (с) Н.М. Светлов, 2007
/23
3.5. Программное

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

Запуск решения – [Ctrl]+[x]
Найти XA

Применение линейного программирования в математических моделях (с) Н.М. Светлов, 2007/233.5. Программное обеспечение линейного программированияЗапуск решения – [Ctrl]+[x]Найти

Слайд 23/23
3.5.
Два способа установки XA
Если есть права доступа к каталогу C:\WINDOWS
копируем

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

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

Найти XA

$/233.5.Два способа установки XAЕсли есть права доступа к каталогу C:\WINDOWSкопируем туда файлы CXA32.DLL и CAXA32.DLLИначекопируем файлы CXA32.DLL$

Скачать презентацию

Теги

Разделы презентаций

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

Содержание

Слайды и текст этой презентации

Слайд 1/23Лекция 3. Применение линейного программирования в математических моделяхСодержание лекции:Принцип оптимальности

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

Слайд 2/23ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов /

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

Слайд 3/233.1. Принцип оптимальности в планировании и управленииПринцип оптимальности предполагает следующее:наличие

Слайд 4/233.2. Задача линейного программированияЭто развёрнутая форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия

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

Слайд 5/233.2. Задача линейного программированияЭто каноническая форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия

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

Слайд 6/233.2. Задача линейного программированияЭто матричная форма записиОна тождественна канонической формеЛинейная

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

Слайд 7/233.2. Задача линейного программированияЭто стандартная форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия

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

Слайд 8/233.2.Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности (безотносительно к

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

Слайд 9/233.2.ЗЛП может:не иметь ни одного оптимального решениядопустимой области не существует

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

Слайд 10/233.2.z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1 ≥ 0, x2 ≥

0) x1=50, x2 =0; z = 50Применение линейного программирования в

Слайд 11/233.2.z = max(x1+x2|0.1x1+0.1x2 ≤ 5, x1 ≥ 0, x2 ≥

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

Слайд 12/233.2.z = max(x1+x2|x1+5x2 ≤ 1, x1+x2 ≥ 5, x1 ≥

0, x2 ≥ 0)Несовместность системы ограниченийПрименение линейного программирования в математических

Слайд 13/233.2.z = max(2x1+x2|0.1x1+0.1x2 ≥ 5, x1 ≥ 0, x2 ≥

0)Неограниченность целевой функцииПрименение линейного программирования в математических моделях © Н.М. Светлов,

Слайд 14/233.3. Симплексный методИсходные условия применения симплексного методаЗЛП записана в канонической

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

Слайд 15/233.3.z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1–2x2 ≤ 75, x1 ≥

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

Слайд 16/23В таблице выделены жирным шрифтом3.3.Разрешающий столбец:столбец с наибольшим положительным cjесли положительного cj нет,

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

Слайд 17/233.3.Выполняем обыкновенные жордановы исключения во всей таблице:для строк i ≠i'

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

Слайд 18/233.3.Опорное решение может быть получено по следующей процедуре:Выбираем произвольный набор

базисных переменных и выражаем их через свободныеЕсли строк с отрицательными

Слайд 19/233.3.В некоторых случаях алгоритм симплексного метода может зацикливаться.Пути преодоления этой

проблемы описаны в рекомендуемой литературе.Применение линейного программирования в математических моделях ©

Слайд 20/233.4. Экономические приложения линейного программированияМатрица потребности в ресурсах для обеспечения

единичного объёма производства в каждой отрасли.Строки – ресурсы, столбцы –

Слайд 21/233.4. Экономические приложения линейного программированияВектор цен продукции (за вычетом НДС),

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

Слайд 22Применение линейного программирования в математических моделях (с) Н.М. Светлов, 2007/233.5. Программное

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

Слайд 23/233.5.Два способа установки XAЕсли есть права доступа к каталогу C:\WINDOWSкопируем

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

Похожие презентации

Обратная связь

Что такое TheSlide.ru?

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

Принцип оптимальности

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

Слайд 2/23
Литература
Экономико-математические методы и прикладные модели: Учеб. пособие для вузов /

Слайд 3/23
3.1. Принцип оптимальности в планировании и управлении
Принцип оптимальности предполагает следующее:
наличие

Слайд 4/23
3.2. Задача линейного программирования
Это развёрнутая форма записи
Линейная целевая функция
Линейные ограни-чения

Условия

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

Слайд 5/23
3.2. Задача линейного программирования
Это каноническая форма записи
Линейная целевая функция
Линейные ограни-чения
Условия

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

Слайд 6/23
3.2. Задача линейного программирования
Это матричная форма записи
Она тождественна канонической форме
Линейная

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

Слайд 7/23
3.2. Задача линейного программирования
Это стандартная форма записи
Линейная целевая функция
Линейные ограни-чения
Условия

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

Слайд 8/23
3.2.
Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности (безотносительно к

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

Слайд 9/23
3.2.
ЗЛП может:
не иметь ни одного оптимального решения
допустимой области не существует

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

Слайд 10/23
3.2.
z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1 ≥ 0, x2 ≥

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

Применение линейного программирования в

Слайд 11/23
3.2.
z = max(x1+x2|0.1x1+0.1x2 ≤ 5, x1 ≥ 0, x2 ≥

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

Слайд 12/23
3.2.
z = max(x1+x2|x1+5x2 ≤ 1, x1+x2 ≥ 5, x1 ≥

0, x2 ≥ 0)
Несовместность системы ограничений
Применение линейного программирования в математических

Слайд 13/23
3.2.
z = max(2x1+x2|0.1x1+0.1x2 ≥ 5, x1 ≥ 0, x2 ≥

0)
Неограниченность целевой функции
Применение линейного программирования в математических моделях © Н.М. Светлов,

Слайд 14/23
3.3. Симплексный метод
Исходные условия применения симплексного метода
ЗЛП записана в канонической

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

Слайд 15/23
3.3.
z = max(x1+x2|0.1x1+0.2x2 ≤ 5, x1–2x2 ≤ 75, x1 ≥

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

Слайд 16/23
В таблице выделены жирным шрифтом
3.3.
Разрешающий столбец:
столбец с наибольшим положительным cj
если положительного cj нет,

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

Слайд 17/23
3.3.
Выполняем обыкновенные жордановы исключения во всей таблице:
для строк i ≠i'

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

Слайд 18/23
3.3.
Опорное решение может быть получено по следующей процедуре:

Выбираем произвольный набор

базисных переменных и выражаем их через свободные
Если строк с отрицательными

Слайд 19/23
3.3.
В некоторых случаях алгоритм симплексного метода может зацикливаться.
Пути преодоления этой

проблемы описаны в рекомендуемой литературе.
Применение линейного программирования в математических моделях ©

Слайд 20/23
3.4. Экономические приложения линейного программирования
Матрица потребности в ресурсах для обеспечения

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

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

Слайд 21/23
3.4. Экономические приложения линейного программирования
Вектор цен продукции (за вычетом НДС),

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

Слайд 22Применение линейного программирования в математических моделях (с) Н.М. Светлов, 2007
/23
3.5. Программное

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

Запуск решения – [Ctrl]+[x]
Найти XA

Слайд 23/23
3.5.
Два способа установки XA
Если есть права доступа к каталогу C:\WINDOWS
копируем

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