Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Изучение аналитических методов решения задач линейного программирования - файл 1.docx


Изучение аналитических методов решения задач линейного программирования
скачать (615.4 kb.)

Доступные файлы (1):

1.docx616kb.08.12.2011 21:00скачать

содержание
Загрузка...

1.docx

Реклама MarketGid:
Загрузка...


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

Высшего профессионального образования

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ

КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ

Курсовая работа
Изучение аналитических методов решения

задач линейного программирования

Выполнила:
Научный руководитель:

к.э.н., доцент

Потехина Е.В.

Москва 2010

СОДЕРЖАНИЕ



Введение

3

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

4

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

5

Алгоритм графического метода

9

Пример применения графического метода для решения ЗЛП

9

Построение математических моделей Задача об оптимальном использовании ресурсов

16

Пример построения модели

17

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

18

Основные положения

19

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

21

Пример выполнения задания 2. Задача об оптимальном использовании ресурсов

25



ВВЕДЕНИЕ






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

Линейная оптимизация возникла в связи с распространением вопросов о нахождении наивыгоднейшим вариантов при решении различных планово-производственных задач, описываемых линейными моделями, где математические зависимости являются линейными относительно всех переменных величин, включенных в модель.

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

Например таковыми являются балансовые, распределительные, транспортные задачи, задачи нахождения наиболее рационального способа использования сырья и материалов, определения оптимального ассортимента или произведенных режимов повышения эффективности работы транспорта и т.д.


^

ПОСТАНОВКА ЗАДАЧИ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


Equation Chapter 1 Section 1
Задача. Найти наименьшее (наибольшее) значение функции переменных :

\* MERGEFORMAT (.)

при ограничениях

\* MERGEFORMAT (.)

и условиях неотрицательности переменных

\* MERGEFORMAT (.)

Функция (1.1) называется целевой функцией.

Любое решение системы (1.2), удовлетворяющее условию (1.3) называется допустимым решением.

Совокупность всех допустимых решений называется областью допустимых решений (ОДР).

Допустимое решение, для которого целевая функция достигает максимума (минимума), называется оптимальным решением.

^

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ДВУМЯ ПЕРЕМЕННЫМИ






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

Ищем оптимальное значение целевой функции

\* MERGEFORMAT (.)

с ограничениями

\* MERGEFORMAT (.)

и условиями неотрицательности

\* MERGEFORMAT (.)

Каждое из неравенств (1.5) геометрически определяет полуплоскость с граничными условиями

\* MERGEFORMAT (.)

а неравенства (1.6) определяют границы
и означают, что допустимые решения лежат только в первой четверти плоскости.

Чтобы определить, какая именно полуплоскость, удовлетворяет неравенству

\* MERGEFORMAT (.)

достаточно проверить условие (1.8) для некоторой точки, например начала координат .

Область пересечения данных полуплоскостей, лежащая в первой четверти плоскости, определяет область допустимых решений задачи линейного программирования (ОДР).

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



Область допустимых решений может быть:

- выпуклый многоугольник

Рисунок
- выпуклая многоугольная неограниченная область

Рисунок
- пустая область;

- единственная точка.

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

Линии уровней целевой функции (1.4) представляют собой семейство прямых


которые перпендикулярный вектору – градиенты целевой функции

\* MERGEFORMAT (.)

Вектор указывает направление наискорейшего возрастания целевой функции, а противоположный вектор убывания целевой функции.

В одной и той же системе координат изобразим область допустимых решений и линии уровня целевой функции.

Задача определения максимуму (минимума) целевой функции сводится к нахождению в ОДР точки, через которую проходит прямая из семейства (1.9) и которая соответствует наибольшему (наименьшему) значению .

Возможны следующие случаи:

Рисунок

Максимуму целевой функции достигается в точке А, минимум - в точке В.
Рисунок



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

Рисунок

Максимум целевой функции недостижим, минимум – в точке В.

^

АЛГОРИТМ ГРАФИЧЕСКОГО МЕТОДА




    1. 

    2. Построить каждую из прямых системы (1.7) и определить полуплоскость, соответствующую ограничениям (1.8).

    3. Определить многоугольник решений.

    4. Построить вектор градиента целевой функции .

    5. Построить прямую , проходящую через начало координат и перпендикулярную вектору .

    6. Передвигать данную прямую параллельно себе в направлении вектора . Рассматриваются только линии пересекающие область допустимых решений (ОДР). Наиболее удаленные вершины ОДР соответствуют максимуму целевой функции. При поиске минимума следует передвигать прямую в направлении, противоположном .

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


^

ПРИМЕР ПРИМЕНЕНИЯ ГРАФИЧЕСКОГО МЕТОДА

ДЛЯ РЕШЕНИЯ ЗЛП




Задача № 22. Решить графическим методом следующую задачу линейного программирования:
Решение:

  1. а) Построим полуплоскоть, определяемую неравенством


Сначала по двум точками







0

3

-4

0

построим прямую .

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

Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.

б). Построим полуплоскоть, определяемую неравенством

Сначала по двум точками







0

3

3

0

построим прямую .

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

Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.

в). Построим полуплоскоть, определяемую неравенством

Сначала по двум точкам







0




1

0

построим прямую .

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

Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.

г). Построим полуплоскоть, определяемую неравенством
Сначала по двум точкам







0

2

3

0

построим прямую .

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

Так как прямая не проходит через начало координат, подставим координаты точки в неравенство и получим строгое неравенство . Следовательно, точка лежит в полуплоскости решений неравенства . Отметим эту полуплоскость с помощью шриховки, направленной в сторону начала координат.

Рисунок




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

Рисунок

  1. Построим вектор-градиент .


Рисунок

  1. Построим прямую , проходящую через начало координат перпендикулярно .

Рисунок

  1. 

  2. Перемещаем прямую параллельно и пересечем ОДР. Последнее пересечение с ОДР будет в точке , которая соответствует максимуму целевой функции.

Рисунок

  1. Определим координаты точки , решая систему

.

При решении таких систем можно воспользоваться правилом Крамера:


Подставив координаты точки в целевую функцию, получим

:
Точка С (2,14; 0,85) является точкой максимума

Ответ: Fmax= 8,12 при x (2,14; 0,85)

^






ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

ЗАДАЧА ОБ ОПТИМАЛЬНОМ ИСПОЛЬЗОВАНИИ РЕСУРСОВ


Equation Chapter 10 Section 1
Для изготовления видов продукции используются видов ресурсов . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции и их цены, приведены в таблице:

Виды ресурсов

Расходов ресурсов на ед. продукции

Запасы ресурсов
























































































Цена единицы продукции
















- расход ресурса на изготовление продукции

- запас ресурса .

Дана задача: требуется составить такой план производства продукции, при котором прибыль от её реализации будет максимальной.

Решение:

Пусть - число единиц продукции .

Требуется найти такой ассортимент продукции , дающий максимальную суммарную прибыль от реализации всей продукции

,

при выполнении условий ограниченности запасов



.

По смыслу задачи ищем решение, удовлетворяющее условиям

^

ПРИМЕР ПОСТРОЕНИЯ МОДЕЛИ




Фирма выпускает два вида мороженного: сливочное и шоколадное. Для изготовления мороженного используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженного, суточные запасы исходных продуктов и отпускные цены на 1 кг продукции даны в таблице:

Ресурсы

Расходы исходных продуктов на 1 кг мороженного

Запасы, кг.

сливочное

шоколадное

молоко

0,8

0,5

400

наполнители

0,4

0,8

365

цена (ден.ед)

16

14




Изучение рынка сбыта показало, что суточный спрос на сливочное мороженное превышает спрос на шоколадное мороженное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженное не превышает 350 кг в сутки количество мороженного каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.

Решение.

Обозначим

(кг) – суточный объём выпуска сливочного мороженного,



(кг) – суточный объём выпуска шоколадного мороженного.

Экономико-математическая модель задачи:

Целевая функция будет иметь вид
при ограничениях

^

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ




Дана целевая функция

\* MERGEFORMAT (.)

при условиях связи:

\* MERGEFORMAT (.)

и условиях неотрицательности

\* MERGEFORMAT (.)

Утверждение. Любая задача линейного программирования (ЗЛП) может быть приведена к задаче линейного программирования в канонической форме путем введения балансовых переменных.



Пример.
Решение.

Вводим балансовые переменные во второе и третье ограничение:
Полученная задача имеет вид
Далее ЗЛП будет дана в канонической форме, т.е. условия связи заданы в виде равенств

\* MERGEFORMAT (.)

^

ОСНОВНЫЕ ПОЛОЖЕНИЯ




Теорема Кронекера-Капели.
Система (1.4) имеет решение тогда и только тогда, когда ранг расширенной матрицы равен рангу системы:
причем, если , то система (1.4) имеет единственное решение,

если , то система (1.4) имеет бесконечное множество решений.

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

Предположим, что ранг матрицы равен числу уравнений (все условия линейно независимые):
Определение. Базисным (опорным) решением системы линейных уравнений с неизвестными называется решение, в котором все свободные переменные равны нулю.

Оставшиеся базисных переменных образуют базис.

Замечание. Выбор базисных и свободных переменных неоднозначен.

Определение. Допустимым базисным решением (ДБР) системы (1.4) называется решение, удовлетворяющее условию неотрицательности (1.3).

Утверждение. Допустимое решение ЗЛП является угловой точкой ОДР тогда и только тогда, когда это решение является допустимым базисным.
^ Основные теоремы линейного программирования.
Теорема 1 «Об оптимальном решении в ограниченной области».

Если ОДР ограничена, то оптимальное решение ЗЛП существует и совпадает хотя бы с одним из базисных решений системы.

Теорема 2 «Об оптимальном решении в неограниченной области».

Если ОДР неограниченна, то оптимальное решение ЗЛП, совпадающее по крайней мере с одним из базисных решений существует только тогда, когда целевая функция ограничена сверху – в задаче на поиск максимума, снизу – в задаче на поиск минимума.



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

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

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

Симплекс метод – это метод направленного перебора базисных решений.


^

АЛГОРИТМ СИМПЛЕКС-МЕТОДА




Шаги алгоритма симплекс-метода выполним на конкретном примере.

Рассмотрим ЗЛП:

\* MERGEFORMAT (.)

\* MERGEFORMAT (.)

\* MERGEFORMAT (.)

Шаг . Выбрать базисные переменные (БП) и свободные переменные (СП).

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

В рассматриваемом примере:
Замечание. Приведение системы к требуемому виду осуществляется на предварительном шаге (Шаг 0). Это может быть сделано методом Гаусса или методом искусственного базиса.

Шаг . Выразим БП через СП:

\* MERGEFORMAT (.)

Шаг . Приравняв СП равными нулю, найти допустимое базисное решение (ДБР):
так как все значения неотрицательны.

Шаг . Выразить целевую функцию через СП и вычислить значение целевой функции для найденного .
.

Шаг . Проверить оптимальность найденного решения.
^ Критерий оптимальности решения поиска максимуму (минимума) целевой функции.
Если в выражении линейной целевой функции через СП отсутствуют положительные коэффициенты для задачи поиска максимума (отрицательные коэффициенты для задачи поиска минимума) при СП, то решение является оптимальным.

Если решение является оптимальным, то наша целевая функция достигла своего максимума (минимума) и на этом решение задачи закончено, 

а если нет, то необходимо определить свободную переменную, переходящую в базис и базисную, становящуюся свободной.

В примере - неоптимальное, т.к. коэффициент при положителен.

Шаг .Определить свободную переменную, переходящую в базис и базисную, становящуюся свободной.

Правило. В базис переходит одна из свободных переменных, имеющая положительный (отрицательный) коэффициент в целевой функции.

.

Для следующего базисного решения переменная уже должна быть больше нуля ,чтобы увеличилось значение целевой функции. При увеличении значения (оставляя ) будут изменяться значения базисных переменных в системе (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 ед. продукции В.








Скачать файл (615.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru