КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Постановка и формы представления задач линейного программирования
Линейное программирование относится к наиболее распространенным методам исследования операций, используемых для решения производственных и коммерческих задач. Общей задачей линейного программирования называется задача, которая состоит в определении максимального или минимального значения целевой функции: при наложении на переменные следующих условий: Функция F называется целевой функцией, система – системой ограничений. Задача линейного программирования называется стандартной или симметричной, если в системе ограничений используются только неравенства. Задача линейного программирования называется канонической или основной, если в системе ограничений используются только уравнения.
ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1. Задача использования сырья (задача планирования производства). Для изготовления двух видов продукции и используют три вида сырья: , и . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 10.1. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль. Таблица 10.1
Составим экономико-математическую модель (математическое описание исследуемого экономического процесса) задачи. Обозначим через , количество единиц продукции соответственно , , запланированных к производству. Тогда учитывая количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также запасы сырья, получим систему ограничений (10.1) По смыслу задачи переменные , . (10.2) Суммарная прибыль F(x) составит руб. от реализации продукции и руб. – от реализации продукции , т.е. . (10.3) Итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (10.1) и условию (10.2), при котором функция (10.3) принимает максимальное значение. Задачу легко обобщить на случай выпуска n видов продукции с использованием m видов сырья.
2. Задача составления рациона (задача о диете). Имеется два вида корма I и II, содержащие питательные вещества (витамины) , и . Содержание количества единиц питательного вещества в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 10.2. Таблица 10.2
Необходимо составить дневной рацион, в котором содержание каждого вида питательных веществ было бы не менее установленного минимума, причем затраты на него должны быть минимальными. Составим экономико-математическую модель задачи. Обозначим через и соответственно количество кормов I и II, входящих в дневной рацион. Принимая во внимание значения, приведенные в табл. 10.2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получим систему ограничений (10.4) Кроме того, переменные , . (10.5) Общая стоимость рациона (в руб.) составит . (10.6) Итак, экономико-математическая модель задачи: составить дневной рацион , удовлетворяющий системе (10.4) и условию (10.5), при котором функция (10.6) принимает минимальное значение.
3. Задача о раскрое материалов. На раскрой поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах пропорциональных числам , , …, (условие комплектности). Каждая единица материала может быть раскроена n различными способами, при этом использование i-го способа (i =1, 2, …, n) дает единиц k-го изделия (k = 1, 2, …, l). Требуется составить план раскроя, обеспечивающий максимальное количество комплектов. Составим экономико-математическая модель задачи. Обозначим через количество единиц материала, раскраиваемых i-м способом, и x – количество изготавливаемых комплектов изделий. Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то (10.7) Условие комплектности выразится уравнениями (k = 1, 2, …, l) (10.8) по смыслу задачи переменные (i = 1, 2, …, n). (10.9) Итак, экономико-математическая модель задачи: найти такое решение , удовлетворяющее системе уравнений (10.7) – (10.8) и условию (10.9), при котором функция F = x принимает максимальное значение.
неизвестных и свободных членов системы уравнений задачи. План Х называется опорным планом основной задачи линейного программирования, если система векторов , входящих в разложение (10.14) с положительными коэффициентами , линейно независима. Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он является вырожденным. План , при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.
СВОЙСТВА РЕШЕНИЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Для обоснования свойств задачи линейного программирования и методов ее решения приведем матричную форму записи канонической задачи: (10.15) при ограничениях АХ = В, (10.16) Х 0, (10.17) где , , Теорема 10.1. Множество всех планов задачи линейного программирования выпукло (если оно не пусто). Доказательство. Пусть и – два допустимых плана задачи (10.15)-(10.17). Тогда , и , . Рассмотрим выпуклую линейную комбинацию , , и покажем, что Х также является планом задачи. Действительно, , т.е. Х удовлетворяет (10.16). Но так как , , , , то и , т.е. удовлетворяет и условию (10.17). Таким образом, множество всех решений задачи линейного программирования является выпуклым (выпуклым многогранником или выпуклой многогранной областью), которое в дальнейшем будем называть многогранником решений. Теорема 10.2. Целевая функция задачи линейного программирования достигает своего минимального (максимального) значения в угловой точке многогранника решений. Если целевая функция принимает минимальное (максимальное) значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек. Доказательство. Предположим, что многогранник решений является ограниченным, имеющим конечное число угловых точек. Обозначим его через К. В К имеет вид многоугольника, изображенного на рисунке. Обозначим угловые точки К через , , …, , а оптимальный план через . Тогда для всех Х из К. Если - угловая точка, то первая часть теоремы доказана.
Рисунок 10.2. Предположим, что не является угловой точкой, тогда можно представить как выпуклую линейную комбинацию угловых точек К, т.е. , , . Так как F(Х) – линейная функция, получаем (10.18) В этом разложении среди значений выберем минимальное. Пусть оно соответствует угловой точке и обозначим его через М, т.е. . Заменим в (10.18) каждое значение этим минимальным значением. Тогда, учитывая, что , , получим . По предположению – оптимальный план, поэтому, с одной стороны, , но с другой стороны, доказано, что , следовательно, , где – угловая точка. Итак, существует угловая точка , в которой линейная функция принимает минимальное значение. Для доказательства второй части теоремы допустим, что принимает минимальное значение более чем в одной угловой точке, например в точках , , …, , ; тогда . Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е. , , Так как – линейная функция, получим , т.е. линейная функция F принимает минимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек , , …, . Теорема 10.3. Если система векторов в разложении (10.14) линейно независима и такова, что где все , то точка является угловой точкой многогранника решений. Теорема 10.4. Если – угловая точка многогранника решений, то векторы , соответствующие положительным в разложении (10.14), линейно независимы. Итак, если линейная функция задачи линейного программирования ограничена на многограннике решений, то: 1) существует такая угловая точка многогранника решений, в которой линейная функция задачи линейного программирования достигает своего оптимума; 2) каждый опорный план соответствует угловой точке многогранника решений. Поэтому для решения задачи линейного программирования необходимо исследовать только угловые точки многогранника решений, т.е. только опорные планы.
Дата добавления: 2015-04-29; Просмотров: 605; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |