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

Размещено на 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