Решение задачи линейного программирования (МОР)

СОДЕРЖАНИЕ
Введение……………………………………...……………...….5
1. В чем суть модифицированного симплекс метода? 6
2. Что означает симметричность прямой и двойственной ЗЛП? 10
3. Что означает выпуклый многогранник? 12
4. Практическое задание 13
4.1. Исходная задача 13
4.2. Двойственная задача 17
4.3. Устойчивость решения 18
4.4. Целочисленное ограничение 19
Список использованных источников 22

1. В чем суть модифицированного симплекс метода

В литературе этот метод встречается также под названием метода обратной матрицы.
При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), модифицированный симплекс-метод требует по сравнению с другими значительно меньшего количества вычислительных операций и объема памяти ЭВМ.
В модифицированном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A-1, обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису Ax.
Рассмотрим поэтапно шаги решения задачи линейного программирования модифицированным симплекс-методом:
1. В начале первого цикла нам известна обратная матрица (единичная матрица), базисное решение xb = b.

1. Что означает симметричность прямой и двойственной ЗЛП
Каждой задаче линейного программирования можно определенным образом поставить в соответствие другую задачу линейного программирования, называемую сопряженной или двойственной по отношению к исходной или прямой задаче, сформулированную по стандартным правилам.
Каждая из этих задач может быть решена самостоятельно, но при этом допустимые решения их прямо связаны между собой, что позволяет, зная оптимальное решение одно из них, определить оптимальное решение другое, при этом часто решение двойственной задачи намного легче найти, чем решение прямой.
...

4.1. Исходная задача
Кондитерская фабрика для производства трех видов карамели А, В и С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производство 1 т карамели данного вида, общее количество сырья каждого вида, которое может быть использовано фабрикой, а также прибыль от реализации 1 т карамели данного вида приведены в таблице:
Таблица 1 – Условие задачи.
Вид сырья
Нормы расхода сырья (т) на 1 т карамели
Общее количество сырья (т)

А
В
С

Сахарный песок
0,8
0,5
0,6
850
Патока
0,4
0,4
0,3
600
Фруктовое пюре
-
0,1
0,1
120
Прибыль/ 1 т (р.)
108
112
126
 
 
Найти план производства карамели, обеспечивающий максимальную прибыль от ее реализации. Производство карамели В не более 10 единиц.

1. Ввести обозначения для переменных.
Пусть х1 – карамель вида А, х2 – карамель вида В, х3 – карамель вида С.
2. С помощью этих обозначений составить ЭММ (записать целевую функцию и ограничения модели).
...

4.4. Целочисленное ограничение
Найдем целочисленное решение, и рассмотрим изменение.

Рисунок 6– Поиск решения
В результате поиска решения получим ответ

Рисунок 7– Результат решения

Рисунок 8– Отчет по результатам
Как видно из решения увеличивается выпуск продукции А на 0,5 тонны, и выпуск продукции С уменьшается на 4 тонны, и становится рентабельным выпуск карамели В – 4 тонны.

Заключение
Можно выделить, по крайней мере, два аспекта применения математических методов в решении практических проблем.
1. Совершенствование системы экономической информации. Математические методы позволяют упорядочить систему экономической информации.
2. Повышение точности экономических расчетов. Формализация экономических задач и применение ЭВМ многократно ускоряют типовые, массовые расчеты, повышают точность и сокращают трудоемкость.
Формальные методы являются, прежде всего, средством научно обоснованной подготовки материала для действий человека в процессах управления.
...