Решение задач линейного программирования графически, при помощи симплекс-метода и при помощи пакета MATLAB
Построение области допустимых значений задачи линейного программирования. Приведение задачи к канонической форме. Решение задачи максимизации с ограничениями в виде неравенств симплекс-методом. Поиск оптимального решения задачи средствами пакета MATLAB.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 26.01.2017 |
| Размер файла | 279,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Министерство образования и науки РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«Национальный исследовательский Томский политехнический Университет»
Институт электронного обучения
220700 «Автоматизация технологических процессов и производств»
Индивидуальное домашнее задание
по дисциплине:
Математическое программирование и оптимизация систем
Исполнитель:
студент группы З-8Т31
Плотников Дмитрий Игоревич
Руководитель:
Воронин Александр Васильевич
Томск - 2017
ЗАДАНИЕ
Для варианта матриц A, b, cT решить задачу линейного программирования вручную (графически и при помощи симплекс-метода), а также при помощи пакета MATLAB. Матрицы заданы в форме, принятой в MATLAB, элементы разделяются пробелами или запятыми, строки - точкой с запятой.
линейный программирование задача неравенство симплекс
|
№ ВАРИАНТА |
A |
B |
CT |
|
|
3 |
[2, 4; 0.5, 0.25; 2, 2.5] |
[440; 130; 320] |
[8 12] |
Необходимо выполнить следующие пункты:
1. Графическое построение области допустимых значений задачи линейного программирования и нахождение ее решения;
2. Приведение задачи линейного программирования к канонической форме;
3. решение задачи линейного программирования симплекс-методом, с выбором начального базиса из искусственных переменных (по аналогии с примером, приведенным в методических указаниях по выполнению ИДЗ);
4. решение задачи линейного программирования средствами MATLAB.
РЕШЕНИЕ
1. Рассмотрим (по аналогии с примером в методических указаниях) задачу максимизации с ограничениями в виде неравенств ? . Для этого необходимо составить математическую модель задачи и решить ее графически.
При составлении математической модели, необходимо задать переменные x и y, значения которых примем:
для
для
Целевая функция , при заданных матрицах A, b и cT является математической моделью задачи и имеет вид:
при следующих ограничениях
Следующим шагом является определение области допустимых значений на плоскости .
Для этого необходимо построить прямые, которые будут соответствовать ограничениям задачи. Откладываем значение по оси абсцисс, и значение по оси ординат. Данные прямые совместно с осями координат обозначают область допустимых значений. Следовательно, решение задачи находится внутри и на границах области допустимых значений. Для определения оптимального значения необходима прямая, которая соответствует целевой функции .
Для графического построения области допустимых значений (рисунок 1) при помощи пакета Mathcad, выразим линейные функции из вышеприведенных ограничений.
Допустим, целевая функция равняется , отсюда
Рис.1 Область допустимых значений
С помощью трассировки определим оптимальное решение задачи (см. рисунок 2), которым является
Рис.2 Оптимальное решение задачи
Оптимальное решение задачи находится в точке пересечения ограничений и . Для проверки результата решим систему уравнений:
Точка оптимума имеет координаты (60; 80).
Подставим найденные значения переменных в целевую функцию:
.
2. Для приведения математической модели задачи к канонической форме, заменим целевую функцию максимизации на функцию минимизации, при помощи умножения коэффициентов функции на -1. Также изменим вид ограничений с нестрого неравенства на равенство, добавив в каждое по одной дополнительной остаточной переменной. При этом исходные и дополнительные переменные не принимают отрицательных значений.
Запишем каноническую форму модели:
при ограничениях
3. Начальным базисом назначим базис . Тогда симплекс-таблица для начального базиса примет вид:
|
Базис |
b/с |
-8 |
-12 |
0 |
0 |
0 |
|
|
440 |
2 |
4 |
1 |
0 |
0 |
||
|
130 |
0,5 |
0,25 |
0 |
1 |
0 |
||
|
320 |
2 |
2,5 |
0 |
0 |
1 |
В связи с присутствием отрицательных элементов в строке коэффициентов целевой функции, первоначальное решение уже оптимальным не является. Необходимо сменить базис.
Для этого нужно выбрать ведущие строку и столбец.
Найдем минимальное из отрицательных значений, которое равняется -12, и соответствует столбцу . Этот столбец ведущий в таблице. Выделим значения жирным шрифтом.
Далее определим минимальное отношение , которое равно 440/4 = 110, и соответствует строке , становится ведущей строкой. Так же выделим значения строки жирным шрифтом.
Теперь в начальном базисе переменную заменим переменной и получим базис.
После пересчета симплекс-таблицы для нового базиса:
|
Базис |
b/с |
-2 |
0 |
3 |
0 |
0 |
|
|
110 |
0,5 |
1 |
0,25 |
0 |
0 |
||
|
102,5 |
0,375 |
0 |
-0,0625 |
1 |
0 |
||
|
45 |
0,75 |
0 |
-0,625 |
0 |
1 |
Наблюдаем в строке коэффициентов целевой функции одно отрицательное значение, которое показывает, что найденное решение не является оптимальным. Необходимо опять произвести процедуру смены базиса и пересчитать симплекс-таблицу:
|
Базис |
b/с |
0 |
0 |
1,333 |
0 |
2,667 |
|
|
80 |
0 |
1 |
0,667 |
0 |
-0,667 |
||
|
80 |
0 |
0 |
0,25 |
1 |
-0,5 |
||
|
60 |
1 |
0 |
-0,833 |
0 |
1,333 |
Теперь решение оптимальное, т.к. все элементы строки коэффициентов целевой функции приняли неотрицательные значения.
Оптимальное решение задачи в канонической форме имеет вид
.
Подставляя значения переменных в исходную целевую функцию, найдем максимальное значение:
4. Для поиска оптимального решения задачи средствами пакета MATLAB необходимо подставить в команду linprog([-cT],[А],[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
...Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
курсовая работа [142,9 K], добавлен 24.10.2012Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Создание математической модели, приведение ее к виду задачи линейного программирования. Геометрическая трактовка решения. Определение области допустимых значений. Составление симплекс-таблиц. Разработка опорного плана задачи методом минимального элемента.
контрольная работа [260,2 K], добавлен 22.12.2013Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Сущность симплекс-метода. Общая характеристика задачи о смесях. Разработка основных алгоритмов решения задачи. Решение задачи в среде визуального программирования Delphi. Проектирование интерфейса пользователя. Разработка форм ввода-вывода информации.
курсовая работа [476,6 K], добавлен 22.05.2012Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015
