Решение задач линейного программирования графическим методом
Нахождение минимального значения целевой функции при заданной системе ограничений. Область допустимых решений. Расчет задачи с помощью Поиска решения в Excel. Установка и активация надстроек. Построение таблицы в Excel, заполнение ячеек, ограничения.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 17.11.2013 |
| Размер файла | 1,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«
Контрольная работа
Вариант № 29.12.
Специальность «Финансы и кредит»
2013г
Решение задач линейного программирования графическим методом
Необходимо найти минимальное значение целевой функции:
Z(x) = 3x1+5x2 > min, при системе ограничений:
|
x1 + x2 ? 0 |
(1) |
|
|
3x1 + x2 ? 3 |
(2) |
|
|
5x1+4x2 ? 20 |
(3) |
|
|
x1 - x2 ? 0 |
(4) |
Решение:
В первую очередь, найдем область допустимых значений, т.е. точки x1 и x2 , которые удовлетворяют системе ограничений. По условию задачи x1? 0, x2 ? 0 ,т.е. мы рассматриваем только те точки, которые принадлежат первой четверти.
Шаг 1: Рассмотрим неравенство 1 системы ограничений.
x1+x2 ? 0
Построим прямую.
Заменим знак неравенства на знак равенства.
x1+x2 = 0
x2 = -x1
Прямая проходит через начало координат.
Какие точки нас интересуют?
x1+x2 ? 0
x2 ? -x1
Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой.
Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок.
Область допустимых значений выделена штриховкой.
Точки принадлежащие области допустимых значений:
A (0 , 0)
Шаг 2: Рассмотрим неравенство 2 системы ограничений.
3x1 + x2 ? 3
Построим прямую.
Заменим знак неравенства на знак равенства.
3x1 + x2 = 3
Преобразуем уравнение следующим образом.
Каждый член уравнения разделим на 3 .
Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.
На оси X1 рисуем точку с координатой 1 .
На оси X2 рисуем точку с координатой 3 .
Соединяем полученные точки и получаем необходимую прямую.
Какие точки нас интересуют?
3x1 + x2 ? 3
x2? -3x1 + 3
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.
Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок.
Область допустимых значений выделена штриховкой.
Точки принадлежащие области допустимых значений:
A (0 , 0)
B (1 , 0)
C (0 , 3)
Шаг 3: Рассмотрим неравенство 3 системы ограничений.
5x1+4x2 ? 20
Построим прямую.
Заменим знак неравенства на знак равенства.
5x1+4x2 = 20
Преобразуем уравнение следующим образом .
Каждый член уравнения разделим на 20 .
Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.
На оси X1 рисуем точку с координатой 4 .
На оси X2 рисуем точку с координатой 5 .
Соединяем полученные точки и получаем необходимую прямую.
Какие точки нас интересуют?
5x1+4x2 ? 20
4x2 ? -5x1+20
x2? -5/4x1 + 5
Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой.
Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок.
Ответ:
Задача не имеет решения. Область допустимых решений пустое множество. Не существует точек, удовлетворяющих данной системе ограничений.
Решение задачи с помощью Поиска решения в Excel
Перед тем как начать решать задачу в Excel первым делом надо посмотреть активирована ли настройка «Поиск решения».
Проделываем всё это по следующей инструкции.
Установка и активация надстроек "Поиск решения"
Откройте вкладку Файл.
Нажмите кнопку Параметры и выберите категорию Надстройки.
Убедитесь, что в нижней части диалогового окна Параметры Excel в поле Управление выбран элемент Надстройки Excel, и нажмите кнопку Перейти.
В диалоговом окне Надстройки установите флажок Поиск решения и нажмите кнопку ОК.
Если отобразится сообщение о том, что надстройку не удается запустить, и выведется предложение установить ее, нажмите кнопку Да, чтобы установить надстройку.
Примечание
Обратите внимание, что на вкладку Данные добавлена группа Анализ. Она содержит кнопку команды для надстроек Поиск решения.
Переходим к решению задачи
Для этого строим в Excel Таблицу 1.
Табл.1
Здесь:
Ячейки А3 и В3 содержат значения искомых переменных Х1 и Х2 и задаются изначально равными нулю.
Ячейка С3 содержит значение целевой функции F, которая задается в виде формулы:
=А4*А3+В4*В3
Ячейки А6-А9 и В6-В9 содержат коэффициенты стоящие при Х1 и Х2 в нашей системе ограничений
|
x1 + x2 ? 0 |
(1) |
|
|
3x1 + x2 ? 3 |
(2) |
|
|
5x1+4x2 ? 20 |
(3) |
|
|
x1 - x2 ? 0 |
(4) |
В ячейках D6-D9 записываются знаки неравенств
Ячейки Е6-Е9 содержат правую часть неравенств
В ячейке С6 задается формула первого (1) ограничения системы в виде:
=А6*А3+В6*В3
В ячейке С7 задается формула второго (2) ограничения системы в виде:
=А7*А3+В7*В3
В ячейке С8 задается формула третьего (3) ограничения системы в виде:
=А8*А3+В8*В3
В ячейке С9 задается формула четвертого (4) ограничения системы в виде:
=А9*А3+В9*В3
Т.к. изначально значения ячеек А3 и В3 равно нулю, то и ячейки С6-С9 до поиска решений также будут нулевыми.
Таблица построена, теперь нажимаем кнопку команды Поиск решения, вываливается вот такое окно:
Там где написано Оптимизировать целевую функцию: вводим ячейку С3;
Выбираем Минимум;
Изменяя ячейки переменных: вводим ячейки А3 и В3;
Слева от поля В соответствии с ограничениями: нажимаем кнопку Добавить и в появившимся окне
задаем ограничения:
С6 >= E6 (Добавить)
C7 >= E7 (Добавить)
C8>= E8 (Добавить)
C9 >=E9 (ОК)
В строчке Выберете метод решения: выбираем Поиск решения линейных задач симплекс методом (это метод используется для решения линейных задач, а наши неравенства являются как раз линейными типа Ах+Ву+С>=0) минимальный функция поиск решение
В итоге заполненный формуляр выглядит так:
Нажимаем кнопку Найти решение, а затем ОК. Таблица Excel в результате решения обновится и будет выглядеть так - Таблица 2:
В ячейках А3 и В3 будут показаны искомые Х1=2 и Х2=0 при которых целевая функция F минимальна и равна 6.
После нажатия кнопки Найти решение вывалится окно в котором будет написано Значения ячейки целевой функции не сходятся
Это сообщение означает, что, если должно быть получено минимальное значение (как в нашем случае), существуют подходящие решения со сколь угодно меньшими значениями целевой ячейки., т.е. область допустимых значений целевой функции не ограничена сверху (целевая функция уменьшается неограниченно).
Размещено на Allbest.ru
...Подобные документы
Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа [1,1 M], добавлен 27.08.2012Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Решение задачи расчета структуры и объема товарооборота методом линейного программирования. Формулы ограничений, транспортная задача оптимизации доставки товаров. Решение задачи о назначениях на основе матрицы стоимостей в электронной таблице Excel.
контрольная работа [1023,6 K], добавлен 27.05.2013Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Принципы решения задач линейного программирования в среде электронных таблиц Excel, в среде пакета Mathcad. Порядок решения задачи о назначении в среде электронных таблиц Excel. Анализ экономических данных с помощью диаграмм Парето, оценка результатов.
лабораторная работа [2,0 M], добавлен 26.10.2013Решение общей задачи линейного программирования симплексным методом, графическое построение целевой функции. Его проверка с помощью встроенной функции "Поиск решения" MS Excel. Определение плана перевозок при наименьших суммарных транспортных затрат.
контрольная работа [362,3 K], добавлен 03.11.2011Нахождение высоты конуса наименьшего объема, описанного около данного шара радиуса. Определение исследуемой функции, зависящей от одной переменной. Составление математической модели задачи. Построение графика заданной функции с помощью MS Excel.
задача [3,2 M], добавлен 15.02.2010Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Строение системы уравнений-ограничений и ее переменных, графический способ решения задач линейного программирования на плоскости. Выражение неизвестных через две независимые переменные, являющиеся координатными осями графика. Значение целевой функции.
лабораторная работа [61,4 K], добавлен 07.01.2011Математическая модель задачи. Построение области допустимых планов. Построение линии уровня целевой функции. Оптимизация целевой функции. Точка контакта линии уровня с областью допустимых планов. Максимальное значение и вектор-градиент целевой функции.
презентация [534,8 K], добавлен 11.05.2013Построение пространства допустимых решений. Нахождение оптимального решения с помощью определения направления убывания целевой функции. Нахождение оптимальной точки. Поиск экстремумов методом множителей Лагранжа. Условия экстремума Куна-Таккера.
контрольная работа [396,2 K], добавлен 13.09.2010Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.
курсовая работа [514,8 K], добавлен 04.02.2011Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Особенности решения задач линейного программирования (ЛП) в табличном редакторе Microsoft Excel. Создание экранной формы для ввода условия задачи. Ограничения и граничные условия, перенесение зависимостей из математической модели в экранную форму.
лабораторная работа [160,5 K], добавлен 26.05.2015Решение нелинейного уравнения вида f(x)=0 с помощью программы Excel. Построение графика данной функции и ее табулирование. Расчет матрицы по исходным данным. Проведение кусочно-линейной интерполяции таблично заданной функции с помощью программы Mathcad.
контрольная работа [1,8 M], добавлен 29.07.2013
