Выдаём удостоверения и дипломы установленного образца

Получите 5% кэшбэк!

Запишитесь на один из 793 курсов и получите 5% кэшбэк стоимости курса на карту

Выбрать курс
Инфоурок Информатика СтатьиОбщая постановка задачи линейного программирования и ее графическое решение

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

Скачать материал
библиотека
материалов

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


Задачей линейного программирования (ЗЛП) называется задача вида


(1.1.1)


(1.1.2)

(1.1.3)

где - это управляющие переменные или решения задачи,

- параметры.

Система неравенств (1.1.1) называется системой ограничений задачи.

Неравенства (1.1.2) – условие не отрицательности переменных.

Функция (1.1.3) – функция цели (целевая функция).

Вектор , удовлетворяющий неравенствам (1.1.1) и (1.1.2), называется планом задачи линейного программирования или допустимым вектором, или допустимым решением.


Решить задачу линейного программирования – это значит найти значения управляющих переменных , удовлетворяющих ограничениям (1.1.1) и (1.1.2), при которых це6левая функция (1.1.3) принимает минимальное или максимальное значение.


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


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


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


Причины, по которым не может быть найдено оптимальное решение:

  1. Функция на допустимом множестве неограниченна. Эта задача называется неразрешимой из-за неограниченности целевой функции.

  2. Допустимое множество пусто , то есть не существует допустимых решений. Такая задача называется несовместимой.

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


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

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

Решение задачи происходит в два этапа.

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


Этап 1. Построение допустимого множества.


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

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

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


Алгоритм выполнения первого этапа.


Шаг 1. Выделение первого координатного угла, если присутствуют ограничения неотрицательности переменных.

Шаг 2. .

Шаг 3. -е неравенство записывается как уравнение.

Шаг 4. Полагаем, находим из уравнения.

Шаг 5. Полагаем, находим из уравнения.

Шаг 6. Через точку и проводится прямая.

Шаг 7. Если правая часть не равна нулю, то в качестве пробной точки удобнее всего выбрать начало координат (0,0), иначе можно взять любую точку, не лежащую на этой прямой. В левую часть неравенства подставляются координаты этой точки. Если неравенство выполнено, то выбирается полуплоскость, содержащая заданную точку, в противном случае – противоположная полуплоскость.

Шаг 8. Если , то , переходим к Шагу 3, иначе Шаг 9.

Шаг 9. Допустимое множество получено. Если оно пустое, то выписывается ответ: «Задача несовместна», иначе переход к Этапу 2.



Этап 2. Поиск оптимальной точки.


Рассмотрим градиент функции . Так как функция линейна, то ее градиент есть постоянный вектор с координатами .

Примечание:

Известно, что движение в направлении градиента увеличивает значение функции.

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


Алгоритм выполнения второго этапа.

Шаг 1. Строится вектор-градиент .

Шаг 2. Кладется линейка перпендикулярно вектору-градиенту.

Шаг 3. Линейка сдвигается параллельно самой себе по направлению вектора-градиента, пока хотя бы одна точка соответствующей прямой принадлежит допустимому множеству.

Шаг 4. Если при любом положении линейки перпендикулярно вектору-градиенту имеются точки допустимого множества, то выписывается ответ: «Задача неразрешима из-за неограниченности целевой функции» и переход к Шагу 10. Иначе Шаг 5.

Шаг 5. Находится последняя точка допустимого множества, лежащая на соответствующей линии уровня.

Шаг 6. Если эта точка не единственная, то выбирается точка, которая является пересечением двух прямых, ограничивающих допустимое множество.

Шаг 7. Выписывается система двух уравнений с двумя неизвестными.

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

Шаг 9. Находится оптимальное значение целевой функции .

Шаг 10. Конец.


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

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

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









Пример решения задачи:

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


Решение:

1. Построим допустимое множество решений. Для этого определим множество, как пересечение полуплоскостей всех заданных неравенств.

1) Построим прямую

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

При оптимизации целевой функции на максимум крайней точкой допустимого множества является точка пересечения третей прямой с осью абсцисс. Определим эту точку:

получаем точку с координатами - это оптимальная точка.

Рассчитаем значение целевой функции в этой точке:



hello_html_789e84ff.png

рис.1 Пример решения задачи


  • Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
    Пожаловаться на материал
Курс повышения квалификации
Курс профессиональной переподготовки
Учитель математики и информатики
Курс профессиональной переподготовки
Учитель информатики
Скачать материал
Найдите материал к любому уроку,
указав свой предмет (категорию), класс, учебник и тему:
также Вы можете выбрать тип материала:
Проверен экспертом
Общая информация
Учебник: «Информатика (углублённый уровень) (в 2 частях)», Семакин И.Г., Хеннер Е.К., Шестакова Л.В.
Тема: Часть 2

Номер материала: ДБ-1386419

Скачать материал

Вам будут интересны эти курсы:

Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Методика преподавания информатики в начальных классах»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»
Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Современные тенденции цифровизации образования»
Курс повышения квалификации «Специфика преподавания дисциплины «Информационные технологии» в условиях реализации ФГОС СПО по ТОП-50»
Курс повышения квалификации «Применение интерактивных образовательных платформ на примере платформы Moodle»

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.