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

Область определения задачи будет представлять собой пересечение всех построенных полуплоскостей - многоугольник АВСDЕ. Следующим этапом присвоим целевой функции f значение нуль и построим прямую

х1-3x2=0

Эта прямая, проходящая через начало координат, строится следующим образом В левой части уравнения стоит скалярное произведение двух векторов С=(с1, с2) = (1, -3) и Х=(х1,х2). Если скалярное произведение векторов равно нулю, то векторы перпендикулярны.

Построим вектор С , он проходит через начало координат и точку (1, -3) и перпендикулярно ему через начало координат проведем прямую.

Вектор С всегда показывает направление возрастания значения целевой функции, а противоположный ему вектор (-С) направление убывания значения целевой функции. Передвигая прямую х1-3x2=0 по области определения параллельно самой себе в направлении вектора С, значения целевой функции будут возрастать. Передвижение в направлении вектора (-С) дает убывание значения целевой функции.

Целевая функция в задаче достигает своего минимального значения в точке В многоугольника, а максимального - в точке D.

Оптимальному решению задачи соответствует точка В, которая лежит на пересечении прямых

-х1+х2=3

х1+х2=10

Для определения координат точки В решим систему. В результате получим: х1=3,5, х2=6,5; f=-16.

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

Чтобы найти область допустимых значений ограничений, уравнения прямых записываются в виде y=kx+b. Чтобы выразить переменную y через x, необходимо в уравнение прямой выделить y в рамку и последовательно ввести команды Symbolics- Variable- Solve.

Графики прямых строятся с использованием команд Insert- Graph-X-Y-Plot. Чтобы на одном графике построить несколько прямых, необходимо после ввода значения по оси ординат нажать символ запятая.

Для построения осей в контекстном меню Format поля графика устанавливается флажок Crossed.

Строятся для одного или нескольких значений С линии уровня целевой функции f(x,y)=C.

Определяется и вычисляется точка экстремума целевой функции.

Алгоритм симплекс-метода

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

Шаг 1. Строим и заполняем исходную симплексную таблицу по следующей схеме:

В столбце "Базис" записываются базисные переменные, в столбце "С" -- коэффициенты при базисных переменных в целевой функции (сi), в столбце "В" -- свободные члены ограничений (bi), т. е. значения базисных переменных. В столбцах хj (небазисные переменные) отражаются коэффициенты при небазисных переменных в ограничениях (аij), над переменными xj -- коэффициенты при этих переменных в целевой функции (сj). Строка "" в столбце "В" содержит значение целевой функции, которое рассчитывается по формуле:

а столбцы хj этой же строки -- значения относительных оценок (), рассчитываемых по формуле.

Числа (--1) и 0, записываемые соответственно над столбцами "С" и "В", неизменно присутствуют в каждой симплексной таблице и носят вспомогательный характер, чтобы при расчете оценок по таблице не забывать о вычитании сj.

При определении значения f фактически нужно найти сумму произведений элементов столбца "С" на соответствующие элементы столбца "В", что равносильно подстановке базисного плана в целевую функцию, а при определении значения относительной оценки -- сумму произведений элементов столбца "С", включая (--1), на соответствующие элементы того столбца xj для которого она рассчитывается.

Шаг 2. Проверим полученный базисный решение на оптимальность по условию оптимальности.

Если и среди базисных переменных нет искусственных, то решение является оптимальным.

Если и среди базисных переменных есть искусственные, то задача неразрешима, так как ее система ограничений несовместна.

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

Если в оптимальном решение , то это говорит о том, что задача имеет бесконечное число решений.

Шаг 3. Для перехода к новому базисному решению в первую очередь из числа небазисных переменных с отрицательными оценками выбирается переменная, которая вводится в базис. Введем в новый базис переменную хk, которой соответствует наибольшая по абсолютной величине отрицательная оценка :

Столбец, отвечающий переменной xk, назовем главным. Элементы главного столбца обозначаются через аik. Выбранная переменная будет вводиться в базис.

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

Шаг 4. Выбираем переменную, которая выводится из базиса. Ее индекс r находится из соотношения:

по всем i, для которых аik>0.

Строку таблицы, в которой получено наименьшее отношение элемента столбца "В" к соответствующему положительному элементу главного столбца, назовем главной. Элементы главной строки обозначаются через arj. Выбранная переменная xr будет выводиться из базиса.

Если окажется несколько одинаковых наименьших значений отношений, то выбирается любая из соответствующих им переменных. Это может произойти в вырожденной задаче.

Элемент, стоящий на пересечении главной строки и главного столбца, назовем главным (обозначается через аrk).

В случае отсутствия значений аik>0 задача неразрешима, так как ее целевая функция не ограничена на множестве решений задачи.

Шаг 5. Для определения нового базисного решения производим пересчет элементов таблицы и результаты заносим в новую симплексную таблицу. Выбранные переменные в новой таблице меняются местами вместе со своими коэффициентами в целевой функции. Остальные переменные переписываются без изменений со своими коэффициентами. Элементы новой симплексной таблицы рассчитываются по приведенным ниже формулам.

Элементы главной строки ;

главный элемент

элементы главного столбца ;

все остальные элементы таблицы:

Шаг 6. Проверяем правильность расчета значений целевой функции f и оценок по формулам 1и 2.Переходим к шагу 2.

Решение задач оптимизации с использование ЭП Excel

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

Задачи решаются с помощью инструмента Excel Поиск решения. Для запуска выполняется команда Сервис- Настройка. В результате выполнения команды Поиск решения появляется окно диалога Поиск решения .

В поле ввода Установить целевую ячейку указывается ссылка на ячейку с целевой функцией, значение которой будет максимальным, минимальным или нулем в зависимости от выбранного вами переключателя.

В поле ввода Изменяя ячейки указываются ячейки, которые отведены под переменные целевой функции.

Кнопка Параметры вызывает окно диалога Параметры поиска решения, в котором можно изменять параметры алгоритма поиска решения.

Порядок выполнения:

- вводятся формулы для целевой функции и ограничений;

- вводятся начальные значения переменных (нулевыми);

- выполните команду Сервис - Поиск решения. Появится окно диалога "Поиск решения ;

- в поле ввода Установить целевую ячейку введите ссылку на целевую функцию;

- в поле ввода Изменяя ячейки укажите ссылки на ячейки со значениями переменных;

- начинаем вводить информацию в поле ввода Ограничения. Нажмите кнопку Добавить. Появится окно диалога "Добавить ограничения". В поле ввода Ссылка на ячейку введите ссылку на ячейку с первым ограничением. В поле ввода Ограничение введите <= и число;

- воспользуйтесь кнопкой Добавить для ввода остальных ограничений. Для изменения ограничения установите на него курсор и нажмите кнопку Изменить.

- нажмите кнопку Выполнить. После окончания расчета Excel откроет окно Результаты поиска решения;

- выберите в окне Тип отчета и .нажмите кнопку ОК. Перед тем листом, где записана постановка задачи, будет вставлен лист "Отчет по результатам 1", а на экране вы увидите ответ на поставленную задачу.

- Нажмите мышью ярлык "Отчет по результатам 1". На экране появится отчет Excel о решенной задаче.

Список литературы

Основная литература:

1. В.П.Агальцов, И.В. Волдайская, Математические методы в программировании, Москва, ИД "Форум"- ИНФРА-М, 2006

2. Е.М.Кудрявцев, MathCad 8, Символьное и численное решение разнообразных задач, Москва, ДМК, 2000.

3. Г.С. Малик, Основы экономики и ММ в планирование, Москва, Высшая школа, 1988

4. Ю. Стоцкий, Office 2000,. Санкт-Петербург, Питер, 2002

Дополнительная литература:

1. А.И. Карасев, Н.Ш. Кремер, Г.И. Савельев, Математические методы и модели в планировании, Москва, экономика, 1987

2. Л.М. Климова, Основы программирования. Решение типовых задач Delphi 7, Москва, 2005

3. Т.Л. Партыка, И.И. Попов, Математические методы, Москва, ИД "Форум" - ИНФРА-М, 2007

4. М. Хэлворсон, М. Янг, Office 2007, Санкт-Петербург, Питер, 2000

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