Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

Филиал государственного образовательного учреждения высшего

Профессионального образования «Уфимский государственный нефтяной

Технический университет» в г. Салавате

КУРС ЛЕКЦИИ ПО РАЗДЕЛУ МАТЕМАТИКИ

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

Составитель: Ишемгулов А.Ф., ассистент

Салават 2008

Линейное программирование

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

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

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

(1)

при условии, что на переменные наложены ограничения в виде линейных равенств или неравенств:

(2)

Линейная функция Z, оптимальное значение которой отыскивается в ЗЛП, называется целевой функцией, или функцией цели.

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

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

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

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

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

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

При стандартной форме линейной модели

а) все ограничения записываются в виде равенств с неотрицательной правой частью;

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

в) целевая функция подлежит максимизации или минимизации.

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





Дата публикования: 2015-09-17; Прочитано: 757 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...