Изучение аналитических методов решения задач линейного программирования
Постановка и графический метод решения задач линейного программирования с двумя переменными. Построение математических моделей. Особенности симплексного метода решения задач линейного программирования, его основные положения, алгоритм, применение.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 22.04.2011 |
| Размер файла | 415,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
Высшего профессионального образования
РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ
КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ
Курсовая работа
Изучение аналитических методов решения
задач линейного программирования
Выполнила:
Научный руководитель:
к.э.н., доцент
Потехина Е.В.
Москва 2010
ВВЕДЕНИЕ
Линейные задачи оптимального управления выделяются своей наиболее простой математической формулировкой и широким практическим применением.
Линейная оптимизация возникла в связи с распространением вопросов о нахождении наивыгоднейшим вариантов при решении различных планово-производственных задач, описываемых линейными моделями, где математические зависимости являются линейными относительно всех переменных величин, включенных в модель.
Особенностью задачи линейной оптимизации является то, что в них имеются большая свобода изменения различных параметров и ряд ограничивающих условий.
Например таковыми являются балансовые, распределительные, транспортные задачи, задачи нахождения наиболее рационального способа использования сырья и материалов, определения оптимального ассортимента или произведенных режимов повышения эффективности работы транспорта и т.д.
ПОСТАНОВКА ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задача. Найти наименьшее (наибольшее) значение функции переменных :
при ограничениях
и условиях неотрицательности переменных
Функция (1.1) называется целевой функцией.
Любое решение системы (1.2), удовлетворяющее условию (1.3) называется допустимым решением.
Совокупность всех допустимых решений называется областью допустимых решений (ОДР).
Допустимое решение, для которого целевая функция достигает максимума (минимума), называется оптимальным решением.
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ДВУМЯ ПЕРЕМЕННЫМИ
Рассмотрим задачу линейного программирования с двумя переменными и ограничениями только в виде неравенств.
Ищем оптимальное значение целевой функции
с ограничениями
и условиями неотрицательности
Каждое из неравенств (1.5) геометрически определяет полуплоскость с граничными условиями
а неравенства (1.6) определяют границы
и означают, что допустимые решения лежат только в первой четверти плоскости.
Чтобы определить, какая именно полуплоскость, удовлетворяет неравенству
достаточно проверить условие (1.8) для некоторой точки, например начала координат .
Область пересечения данных полуплоскостей, лежащая в первой четверти плоскости, определяет область допустимых решений задачи линейного программирования (ОДР).
Область допустимых решений является выпуклым множеством, которое называется многоугольником решений.
Область допустимых решений может быть:
- выпуклый многоугольник
Рисунок 1
Размещено на http://www.allbest.ru/
- выпуклая многоугольная неограниченная область
Рисунок 2
Размещено на http://www.allbest.ru/
- пустая область;
- единственная точка.
Если область допустимых решений пустое множество, задача линейного программирования не имеет оптимального решения из-за задача имеет единственное и, следовательно, оптимальное решение. В остальных случаях следует построить линии уровней целевой функции.
Линии уровней целевой функции (1.4) представляют собой семейство прямых
которые перпендикулярный вектору - градиенты целевой функции
Вектор указывает направление наискорейшего возрастания целевой функции, а противоположный вектор убывания целевой функции.
В одной и той же системе координат изобразим область допустимых решений и линии уровня целевой функции.
Задача определения максимуму (минимума) целевой функции сводится к нахождению в ОДР точки, через которую проходит прямая из семейства (1.9) и которая соответствует наибольшему (наименьшему) значению .
Возможны следующие случаи:
Рисунок 3
Максимуму целевой функции достигается в точке А, минимум - в точке В.
Рисунок 4
Максимум целевой функции достигается в любой точке отрезка , минимум в точке В.
Рисунок 5
Максимум целевой функции недостижим, минимум - в точке В.
АЛГОРИТМ ГРАФИЧЕСКОГО МЕТОДА
1. Построить каждую из прямых системы (1.7) и определить полуплоскость, соответствующую ограничениям (1.8).
2. Определить многоугольник решений.
3. Построить вектор градиента целевой функции .
4. Построить прямую , проходящую через начало координат и перпендикулярную вектору .
5. Передвигать данную прямую параллельно себе в направлении вектора . Рассматриваются только линии пересекающие область допустимых решений (ОДР). Наиболее удаленные вершины ОДР соответствуют максимуму целевой функции. При поиске минимума следует передвигать прямую в направлении, противоположном .
6. Определить координаты точек экстремума и значение целевой функции в этих точках.
ПРИМЕР ПРИМЕНЕНИЯ ГРАФИЧЕСКОГО МЕТОДА
ДЛЯ РЕШЕНИЯ ЗЛП
Задача № 22. Решить графическим методом следующую задачу линейного программирования:
Решение:
1. а) Построим полуплоскость, определяемую неравенством
Сначала по двум точками
|
0 |
3 |
|
|
-4 |
0 |
построим прямую .
Найдем, которая из двух плоскостей, на которые прямая делит всю плоскость, является областью решения неравенства .
Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.
б). Построим полуплоскость, определяемую неравенством
Сначала по двум точками
|
0 |
3 |
|
|
3 |
0 |
построим прямую .
Найдем, которая из двух плоскостей, на которые прямая делит всю плоскость, является областью решения неравенства .
Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.
в). Построим полуплоскость, определяемую неравенством
Сначала по двум точкам
|
0 |
||
|
1 |
0 |
построим прямую .
Найдем, которая из двух плоскостей, на которые прямая делит всю плоскость, является областью решения неравенства .
Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.
г). Построим полуплоскость, определяемую неравенством
Сначала по двум точкам
|
0 |
2 |
|
|
3 |
0 |
построим прямую .
Найдем, которая из двух плоскостей, на которые прямая делит всю плоскость, является областью решения неравенства .
Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.
Рисунок 6
2. Найдем общую часть всех полуплоскостей решений. Получим, что область допустимых решений представляет собой четырехугольник .
Рисунок 7
3. Построим вектор-градиент .
Рисунок 8
4. Построим прямую , проходящую через начало координат перпендикулярно .
Рисунок 9
5. Перемещаем прямую параллельно и пересечем ОДР. Последнее пересечение с ОДР будет в точке , которая соответствует максимуму целевой функции.
Рисунок 10
6. Определим координаты точки , решая систему
.
При решении таких систем можно воспользоваться правилом Крамера:
Подставив координаты точки в целевую функцию, получим
:
Точка С (2,14; 0,85) является точкой максимума
Ответ: Fmax= 8,12 при x (2,14; 0,85)
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ.
ЗАДАЧА ОБ ОПТИМАЛЬНОМ ИСПОЛЬЗОВАНИИ РЕСУРСОВ
Для изготовления видов продукции используются видов ресурсов . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции и их цены, приведены в таблице:
|
Виды ресурсов |
Расходов ресурсов на ед. продукции |
Запасы ресурсов |
||||
|
Цена единицы продукции |
- расход ресурса на изготовление продукции
- запас ресурса .
Дана задача: требуется составить такой план производства продукции, при котором прибыль от её реализации будет максимальной.
Решение:
Пусть - число единиц продукции .
Требуется найти такой ассортимент продукции , дающий максимальную суммарную прибыль от реализации всей продукции
,
при выполнении условий ограниченности запасов
.
По смыслу задачи ищем решение, удовлетворяющее условиям
ПРИМЕР ПОСТРОЕНИЯ МОДЕЛИ
Фирма выпускает два вида мороженного: сливочное и шоколадное. Для изготовления мороженного используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженного, суточные запасы исходных продуктов и отпускные цены на 1 кг продукции даны в таблице:
|
Ресурсы |
Расходы исходных продуктов на 1 кг мороженного |
Запасы, кг. |
||
|
сливочное |
шоколадное |
|||
|
молоко |
0,8 |
0,5 |
400 |
|
|
наполнители |
0,4 |
0,8 |
365 |
|
|
цена (ден.ед) |
16 |
14 |
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженное превышает спрос на шоколадное мороженное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженное не превышает 350 кг в сутки количество мороженного каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.
Решение.
Обозначим
(кг) - суточный объём выпуска сливочного мороженного,
(кг) - суточный объём выпуска шоколадного мороженного.
Экономико-математическая модель задачи:
Целевая функция будет иметь вид
при ограничениях
СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Дана целевая функция
при условиях связи:
и условиях неотрицательности
Утверждение. Любая задача линейного программирования (ЗЛП) может быть приведена к задаче линейного программирования в канонической форме путем введения балансовых переменных.
Пример.
Решение.
Вводим балансовые переменные во второе и третье ограничение:
Полученная задача имеет вид
Далее ЗЛП будет дана в канонической форме, т.е. условия связи заданы в виде равенств
ОСНОВНЫЕ ПОЛОЖЕНИЯ
Теорема Кронекера-Капели.
Система (1.4) имеет решение тогда и только тогда, когда ранг расширенной матрицы равен рангу системы:
причем, если , то система (1.4) имеет единственное решение,
если , то система (1.4) имеет бесконечное множество решений.
Методом Гаусса среди переменных можно выделить базисных переменных и свободных переменных, причем базисные переменные могут быть линейно выражены через свободные.
Предположим, что ранг матрицы равен числу уравнений (все условия линейно независимые):
Определение. Базисным (опорным) решением системы линейных уравнений с неизвестными называется решение, в котором все свободные переменные равны нулю.
Оставшиеся базисных переменных образуют базис.
Замечание. Выбор базисных и свободных переменных неоднозначен.
Определение. Допустимым базисным решением (ДБР) системы (1.4) называется решение, удовлетворяющее условию неотрицательности (1.3).
Утверждение. Допустимое решение ЗЛП является угловой точкой ОДР тогда и только тогда, когда это решение является допустимым базисным.
Основные теоремы линейного программирования.
Теорема 1 «Об оптимальном решении в ограниченной области».
Если ОДР ограничена, то оптимальное решение ЗЛП существует и совпадает хотя бы с одним из базисных решений системы.
Теорема 2 «Об оптимальном решении в неограниченной области».
Если ОДР неограниченна, то оптимальное решение ЗЛП, совпадающее по крайней мере с одним из базисных решений существует только тогда, когда целевая функция ограничена сверху - в задаче на поиск максимума, снизу - в задаче на поиск минимума.
Из приведенных выше теорем следует, что если есть оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений.
Следовательно, нужно перебрать все угловые точки, что связано с большими вычислительными трудностями.
Если же указанный перебор базисных решений производить направленно, на каждом шаге улучшая значения целевой функции, то число перебираемых базисных решений можно резко сократить.
Симплекс метод - это метод направленного перебора базисных решений.
АЛГОРИТМ СИМПЛЕКС-МЕТОДА
Шаги алгоритма симплекс-метода выполним на конкретном примере.
Рассмотрим ЗЛП:
Шаг . Выбрать базисные переменные (БП) и свободные переменные (СП).
Если возможно выбрать переменные, которые входят в единственном числе только в одно уравнение и при этом нет таких уравнений, в которые они не входят, то эти переменные выбираем в качестве базисных переменных. Правые части при этом должны быть неотрицательны.
В рассматриваемом примере:
Замечание. Приведение системы к требуемому виду осуществляется на предварительном шаге (Шаг 0). Это может быть сделано методом Гаусса или методом искусственного базиса.
Шаг . Выразим БП через СП:
Шаг . Приравняв СП равными нулю, найти допустимое базисное решение (ДБР):
так как все значения неотрицательны.
Шаг . Выразить целевую функцию через СП и вычислить значение целевой функции для найденного .
.
Шаг . Проверить оптимальность найденного решения.
Критерий оптимальности решения поиска максимуму (минимума) целевой функции.
Если в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты для задачи поиска максимума (отрицательные коэффициенты для задачи поиска минимума) при СП, то решение является оптимальным.
Если решение является оптимальным, то наша целевая функция достигла своего максимума (минимума) и на этом решение задачи закончено, а если нет, то необходимо определить свободную переменную, переходящую в базис и базисную, становящуюся свободной.
В примере - неоптимальное, т.к. коэффициент при положителен.
Шаг .Определить свободную переменную, переходящую в базис и базисную, становящуюся свободной.
Правило. В базис переходит одна из свободных переменных, имеющая положительный (отрицательный) коэффициент в целевой функции.
.
Для следующего базисного решения переменная уже должна быть больше нуля ,чтобы увеличилось значение целевой функции. При увеличении значения (оставляя ) будут изменяться значения базисных переменных в системе (1.8), которые при этом должны остаться неотрицательными.
Если все базисные переменные будут увеличиваться, то задача оптимизации не имеет решения. Если же некоторые из них будут уменьшаться, то та базисная переменная, которая первой обнулится и станет свободной переменной.
Для примера имеем
Положив , получим следующие ограничения, до которых может расти переменная . Заметим, что в первом уравнении может расти неограниченно:
Ищем самое строгое ограничение сверху, т.е.
Выберем уравнение системы (1.8), в котором БП обращается в нуль. Это уравнение называется разрешающим. Соответствующая базисная переменная становится свободной.
В примере разрешающим уравнением является уравнение
Повторяем шаги алгоритма.
Шаг .
Шаг .
Упрощаем:
Шаг .
Шаг .
Шаг .
Так как в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты, найденное решение является оптимальным.
ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАНИЯ 2.
ЗАДАЧА ОБ ОПТИМАЛЬНОМ ИСПОЛЬЗОВАНИИ РЕСУРСОВ
Задание: Составить математическую модель задачи и решить её симплекс-методом.
Задача 22: При изготовлении изделий видов А и В используется сырье 4-ч видов. Расходы сырья на единицу продукции каждого вида и цена единицы продукции приведены в таблице
|
Сырье |
Расход сырья не одно изделие |
Запас сырья |
||
|
А |
В |
|||
|
Сырье 1 |
2 |
3 |
19 |
|
|
Сырье 2 |
2 |
1 |
13 |
|
|
Сырье 3 |
0 |
3 |
15 |
|
|
Сырье 4 |
3 |
0 |
18 |
|
|
Цена одного изделия, ден.ед. |
7 |
5 |
Необходимо определить план выпуска продукции, чтобы общий доход от реализации выпускаемой продукции был бы максимальным.
Решение.
Пусть - число единиц продукции А
- число единиц продукции В.
По условию задачи составим целевую функцию и систему ограничений:
Шаг 0. Приведем систему к требуемому виду:
Шаг . Выберем базисные переменные (БП) и свободные переменные (СП). В качестве базисных переменных выбираем переменные которые по одному стоят в каждом уравнении, при этом правые части неотрицательны.
Шаг . Выразим БП через СП:
Шаг . Приравняв СП равными нулю, найдем допустимое базисное решение (ДБР):
Шаг . Выразим целевую функцию через СП и вычислим значение целевой функции для найденного .
.
Шаг . Проверим оптимальность найденного решения.
ДБР - неоптимальное, т.к. все коэффициенты положительны
Шаг . На данном шаге определим свободную переменную, переходящую в базис, и базисную, преходящую в свободную.
Так как в примере обе свободные переменные в целевой функции имеют положительные коэффициенты, то пусть . Из системы
, оставив , получаем
Найдем самое строгое ограничение сверху, т.е.
При переменная обратиться в нуль, значит перейдет в разряд свободных.
Выполним второй цикл решения.
Шаг .
Шаг . Выразим БП через СП:
Шаг . Приравняв СП равными нулю, найдем допустимое базисное решение (ДБР):
Шаг . Выразим целевую функцию через СП и вычислим значение целевой функции для найденного .
Шаг . Проверим оптимальность найденного решения.
ДБР - неоптимальное, т.к. не все коэффициенты отрицательны.
Шаг . Определим свободную переменную, переходящую в базис, и базисную, преходящую в свободную.
Пусть
Из системы
оставив , получаем
При переменная обратиться в нуль, значит перейдет в разряд свободных.
Выполним третий цикл решения.
Шаг .
Шаг . Выразим БП через СП:
Шаг . Приравняв СП равными нулю, найдем допустимое базисное решение (ДБР):
Шаг . Выразим целевую функцию через СП и вычислим значение целевой функции для найденного .
Шаг . Проверим оптимальность найденного решения.
ДБР - неоптимальное, т.к. не все коэффициенты отрицательны.
Шаг . Определим свободную переменную, переходящую в базис, и базисную, преходящую в свободную.
Так как то
Из системы
оставив , получаем
графический линейный программирование симплексный
При переменная обратиться в нуль, значит перейдет в разряд свободных.
Выполним четвертый цикл решения.
Шаг .
Шаг . Выразим БП через СП:
Шаг . Приравняв СП равными нулю, найдем допустимое базисное решение (ДБР):
Шаг . Выразим целевую функцию через СП и вычислим значение целевой функции для найденного .
Шаг . Проверим оптимальность найденного решения.
Так как в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты, найденное решение является оптимальным
Ответ. Для получения наибольшего дохода, который составляет 50 ден. ед., необходимо выпускать 5 ед. продукции А и 3 ед. продукции В.
Размещено на Allbest.ru
Подобные документы
Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
реферат [162,8 K], добавлен 20.05.2019Общее понятие вектора и векторного пространства, их свойства и дополнительные структуры. Графический метод в решении задачи линейного программирования, его особенности и область применения. Примеры решения экономических задач графическим способом.
курсовая работа [1,2 M], добавлен 14.11.2010Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
контрольная работа [79,4 K], добавлен 04.06.2010Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Основные понятия математического моделирования, характеристика этапов создания моделей задач планирования производства и транспортных задач; аналитический и программный подходы к их решению. Симплекс-метод решения задач линейного программирования.
курсовая работа [2,2 M], добавлен 11.12.2011Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Предназначена библиотеки "simplex" для оптимизации линейных систем с использованием симплексного алгоритма. Построение экономико-математической модели формирования плана производства. Основные виды транспортных задач, пример и способы ее решения.
курсовая работа [477,9 K], добавлен 12.01.2011Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010
