Решение задач линейного программирования графически, при помощи симплекс-метода и при помощи пакета MATLAB

Размещено на http://www.allbest.ru

Министерство образования и науки РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«Национальный исследовательский Томский политехнический Университет»

Институт электронного обучения

220700 «Автоматизация технологических процессов и производств»

Индивидуальное домашнее задание

по дисциплине:

Математическое программирование и оптимизация систем

Исполнитель:

студент группы З-8Т31

Плотников Дмитрий Игоревич

Руководитель:

Воронин Александр Васильевич

Томск - 2017

ЗАДАНИЕ

Для варианта матриц A, b, c^T решить задачу линейного программирования вручную (графически и при помощи симплекс-метода), а также при помощи пакета MATLAB. Матрицы заданы в форме, принятой в MATLAB, элементы разделяются пробелами или запятыми, строки - точкой с запятой.

линейный программирование задача неравенство симплекс

Необходимо выполнить следующие пункты:

1. Графическое построение области допустимых значений задачи линейного программирования и нахождение ее решения;

2. Приведение задачи линейного программирования к канонической форме;

3. решение задачи линейного программирования симплекс-методом, с выбором начального базиса из искусственных переменных (по аналогии с примером, приведенным в методических указаниях по выполнению ИДЗ);

4. решение задачи линейного программирования средствами MATLAB.

РЕШЕНИЕ

1. Рассмотрим (по аналогии с примером в методических указаниях) задачу максимизации с ограничениями в виде неравенств ? . Для этого необходимо составить математическую модель задачи и решить ее графически.

При составлении математической модели, необходимо задать переменные x и y, значения которых примем:

для

для

Целевая функция , при заданных матрицах A, b и c^T является математической моделью задачи и имеет вид:

при следующих ограничениях

Следующим шагом является определение области допустимых значений на плоскости .

Для этого необходимо построить прямые, которые будут соответствовать ограничениям задачи. Откладываем значение по оси абсцисс, и значение по оси ординат. Данные прямые совместно с осями координат обозначают область допустимых значений. Следовательно, решение задачи находится внутри и на границах области допустимых значений. Для определения оптимального значения необходима прямая, которая соответствует целевой функции .

Для графического построения области допустимых значений (рисунок 1) при помощи пакета Mathcad, выразим линейные функции из вышеприведенных ограничений.

Допустим, целевая функция равняется , отсюда

Рис.1 Область допустимых значений

С помощью трассировки определим оптимальное решение задачи (см. рисунок 2), которым является

Рис.2 Оптимальное решение задачи

Оптимальное решение задачи находится в точке пересечения ограничений и . Для проверки результата решим систему уравнений:

Точка оптимума имеет координаты (60; 80).

Подставим найденные значения переменных в целевую функцию:

.

2. Для приведения математической модели задачи к канонической форме, заменим целевую функцию максимизации на функцию минимизации, при помощи умножения коэффициентов функции на -1. Также изменим вид ограничений с нестрого неравенства на равенство, добавив в каждое по одной дополнительной остаточной переменной. При этом исходные и дополнительные переменные не принимают отрицательных значений.

Запишем каноническую форму модели:

при ограничениях

3. Начальным базисом назначим базис . Тогда симплекс-таблица для начального базиса примет вид:

В связи с присутствием отрицательных элементов в строке коэффициентов целевой функции, первоначальное решение уже оптимальным не является. Необходимо сменить базис.

Для этого нужно выбрать ведущие строку и столбец.

Найдем минимальное из отрицательных значений, которое равняется -12, и соответствует столбцу . Этот столбец ведущий в таблице. Выделим значения жирным шрифтом.

Далее определим минимальное отношение , которое равно 440/4 = 110, и соответствует строке , становится ведущей строкой. Так же выделим значения строки жирным шрифтом.

Теперь в начальном базисе переменную заменим переменной и получим базис.

После пересчета симплекс-таблицы для нового базиса:

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

Теперь решение оптимальное, т.к. все элементы строки коэффициентов целевой функции приняли неотрицательные значения.

Оптимальное решение задачи в канонической форме имеет вид

.

Подставляя значения переменных в исходную целевую функцию, найдем максимальное значение:

4. Для поиска оптимального решения задачи средствами пакета MATLAB необходимо подставить в команду linprog([-c^T],[А],[b]) данные из задания.

Листинг программы (см. рисунок 3)

X=linprog ([-8 -12],[2 4;0.5 0.25;2 2.5;-1 0;0 -1],[440;130;320;0;0])

Optimization terminated.

X =

60.0000

80.0000

Рис. 3. Решение в среде MATLAB.

Подставив найденные значения переменных, определим максимальное значение функции:

ОТВЕТ: максимальное значение функции равно 1440 при значении переменных , .

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Воронин А.В. Математическое программирование и оптимизация систем: метод. указ. и индивид. задания для студентов ИнЭО, обучающихся по напр. 220700 «Автоматизация технологических процессов и производств» / сост. А.В. Воронин; Томский политехнический университет. - Томск: Изд-во Томского политехнического университета, 2014. - 31 с.

2. Воронин А.В. Математическое программирование и оптимизация систем: учебное пособие / А.В. Воронин; Томский политехнический университет. - Томск: Изд-во Томского политехнического университета, 2014. - 85 с.

3. Калиткин Н.Н. Численные методы. - М.: Наука, 1991.

4. Лесин В.В. Основы методов оптимизации/ В.В. Лесин, Ю.П. Лисовец. - М.: Изд-во МАИ, 1995. - 344 с.

5. Мину М. Математическое программирование. Теория и алгоритмы / пер. с фр. и предисл. А.И. Штерна. - М.: Наука, Гл. ред. физ.-мат. лит., 1990. - 488 с.

6. Хэмди А. Таха. Введение в исследование операций. 7-е изд.: пер. с англ. - М.: ИД «Вильямс», 2005. - 902 с.

Размещено на Allbest.ru