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



бет2/6
Дата11.06.2022
өлшемі489.26 Kb.
#268043
түріСамостоятельная работа
1   2   3   4   5   6
1 Линейное программирование
Мы описываем идеи и приложения линейного программирования; на нашу презентацию сильно повлияла превосходная книга Джоэла Франклина "Методы математической экономики" [Fr]. Мы настоятельно рекомендуем эту книгу всем, кто заинтересован в очень удобочитаемом изложении, изобилующем примерами и ссылками.Линейное программирование - это обобщение линейной алгебры. Он способен решать самые разные задачи, начиная от поиска расписаний авиакомпаний или фильмов в кинотеатре и заканчивая распределением масла от нефтеперерабатывающих заводов до рынков.
1.1 Задача канонического линейного программирования
Постановка проблемы диеты
Сначала мы рассмотрим простой случай проблемы диеты, а затем обсудим обобщение. Предположим для простоты, что есть только два продукта, которые для определённости мы будем считать хлопьями и стейком. Далее, мы предполагаем, что для поддержания жизни людям нужны только два продукта: железо и белок; каждый день человек должен потреблять не менее 60 единиц железа и не менее 70 единиц белка, чтобы оставаться в живых. Предположим, что одна единица хлопьев стоит 20 долларов и содержит 30 единиц железа и 5 единиц белка, и что одна единица стейка стоит 2 доллара и содержит 15 единиц железа и 10 единиц белка. Цель состоит в том, чтобы найти самую дешёвую диету, которая удовлетворит минимальные ежедневные потребности. Мы намеренно выбрали абсурдные цены и уровни железа и белка для каш и стейков, чтобы проиллюстрировать это позже. Пусть x1 представляет количество единиц хлопьев, которые человек потребляет в день, а x2 - количество единиц потребляемого железа. Чтобы диета соответствовала минимальным требованиям, мы должны иметь
30x1 + 5x2 ≥ 60
15x1 + 10x2 ≥ 70 (1)
x1 ≥ 0
x2 ≥ 0
Левая часть первого неравенства представляет количество железа, потребляемого человеком при употреблении х1 единиц хлопьев и х2 единиц стейка; оно должно быть не менее 60, так как в противном случае потребляется недостаточно железа. Аналогично, левая часть второго неравенства представляет количество потребляемого белка и должна составлять не менее 70. Последние два неравенства отражают тот факт, что мы не можем съесть отрицательное количество пищи. Стоимость диеты составляет
Cost(x1, x2) = 20x1 + 2x2, и проблема диеты становится: минимизировать затраты (x1, x2), при условии, что x1, x2 удовлетворяют (1). Очень важно, чтобы не только ограничения в переменных были линейными, но и функция, которую мы пытаемся максимизировать, также была линейной. Мы можем переписать (1) в матричной форме.

Тогда задача диеты эквивалентна минимизации 20x1 + 2x2 при условии Ax ≥ b и x ≥ 0 Приведенное выше является примером задачи линейного программирования:
1. у нас есть переменные xj ≥ 0 для j ∈ {1, . . . , N};
2. переменные удовлетворяют линейным ограничениям, которые мы можем записать как Ax ≥ b;
3. цель состоит в том, чтобы минимизировать линейную функцию переменных: cT x = c1 x1 + · · · + cN xN .
Обратите внимание на сходство между (4) и стандартной задачей линейной алгебры. Различия заключаются в том, что вместо Ax = b мы имеем Ax ≥ b, и вместо решения для x с Ax = b мы решаем для x, удовлетворяющего Ax ≥ b, что минимизирует некоторую линейную функцию. Таким образом, Линейный Алгебра становится подмножеством линейного программирования. Фактически, в следующем разделе мы покажем, как, вводя дополнительные переменные, мы можем заменить ограничения Ax ≥ b новыми ограничениями и новыми переменными, A0 x0 = b0.
1.2 Определения
Прежде чем определить каноническую задачу линейного программирования, мы сначала заметим, что достаточно рассмотреть только те случаи, когда ограничения больше или равны. Это связано с тем, что такое ограничение, как
ai1x1 + · · · + aiN xN ≤ bi. (5)
может быть переписано как
−ai1x1 − · · · − aiN xN ≥ −bi; (6)
элементами матрицы A может быть любое действительное число. Таким образом, нет никакой потери в общности, если предположить, что все ограничения больше или равны. Кроме того, за счет добавления дополнительных переменных мы можем предположить, что все ограничения на самом деле являются равенствами. Рассмотрим некоторые ограничения
(7)
Мы вводим новую переменную zi ≥ 0 и меняем приведённое выше ограничение на
(8)
Таким образом, для каждого ограничения в Ax ≥ b со знаком больше, чем, за счет добавления новой переменной zi ≥ 0 мы можем заменить знак больше, чем равенством. Переменная zi добавляется только к ограничению, а не к линейной функции, которую мы пытаемся минимизировать. Отметим, что мы можем предположить, что каждая переменная xj ≥ 0. Для этого может потребоваться добавление дополнительных ограничений и дополнительных переменных (и дополнительные переменные также будут неотрицательными). Предположим, мы хотим, чтобы xj ≥ mj (мы допускаем, что mj равно −∞). Если mj ≥ 0 и конечно, то мы просто добавьте ограничение xj ≥ mj . Если mj ≤ 0 и конечна, мы заменяем переменную xj на zj, устанавливая zj = xj − mj с zj ≥ 0; обратите внимание, что у нас все еще есть линейная функция для минимизации. Наконец, если mj = −∞ , мы вводим две новые переменные uj , vj ≥ 0, и заменяем xj на uj − vj . Наконец, скажем, что вместо минимизации линейной функции cT x мы хотим ее максимизировать. Поскольку минимизация линейной функции −cT x - это то же самое, что максимизация функции cT x, нет никакой потери общности в предположении, что мы хотим минимизировать линейную функцию. Приведенные выше аргументы показывают, что мы можем взять любую задачу линейного программирования и записать ее в следующем :
Определение 1.1 (Задача канонического линейного программирования). Каноническая задача линейного программирования имеет следующий вид:
1. у нас есть переменные xj ≥ 0 для j ∈ {1, . . . , N};
2. переменные удовлетворяют линейным ограничениям, которые мы можем записать как Ax = b (где A - матрица с M строками и N столбцами, а b - вектор столбцов с M компонентами);
3. цель состоит в том, чтобы минимизировать линейную функцию переменных: cT x = c1 x1 + · · · + cN xN .
Если x удовлетворяет ограничениям (Ax = b, x ≥ 0), то мы называем x возможным решением задачи каноническая задача линейного программирования; если дальнейшее x минимизирует линейную функцию cT x, то x называется оптимальным решением канонической задачи линейного программирования. Мы обсуждаем некоторые патологические случаи. Рассмотрим следующие канонические задачи линейного программирования.
1. Ограничения таковы: x1 = -2007, при x1 ≥ 0 и минимизации 10x1. Нет никаких осуществимых
решений; следовательно, нет и оптимальных решений.
2. Ограничения равны 2x1 − 5x2 = 0, при x1, x2 ≥ 0 и минимизации −17x1. Существует
бесконечно много возможных решений: любое (x1, x2) работает с x1 = 2,5 x2; однако
оптимального решения не существует (множество x1 = =).
3. Ограничения равны x1 + x2 = 1, при этом x1, x2 ≥ 0 и минимизируют x1 + x2. Здесь существует бесконечно много возможных решений, и каждое возможное решение также является оптимальным решением. Приведенные выше примеры показывают, что требуется определенная осторожность. Общая задача линейного программирования не обязательно должна иметь осуществимое решение. Если у него действительно есть осуществимое решение, у него не обязательно должно быть оптимальное
решение. Кроме того, даже если у него есть оптимальное решение, ему не обязательно иметь уникальное оптимальное решение.


Достарыңызбен бөлісу:
1   2   3   4   5   6




©melimde.com 2022
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
бойынша жиынтық
жиынтық бағалау
Сабақ тақырыбы
Сабақтың мақсаты
ғылым министрлігі
тоқсан бойынша
бағдарламасына сәйкес
бағалауға арналған
Сабақ жоспары
Реферат тақырыбы
жиынтық бағалауға
сәйкес оқыту
арналған тапсырмалар
Қазақстан республикасы
білім беретін
оқыту мақсаттары
бағалау тапсырмалары
республикасы білім
Жалпы ережелер
жиынтық бағалаудың
рсетілетін қызмет
бекіту туралы
тоқсанға арналған
Қазақстан тарихы
мерзімді жоспар
Қазақстан республикасының
арналған жиынтық
қызмет стандарты
болып табылады
жалпы білім
арналған әдістемелік
Мектепке дейінгі
оқыту әдістемесі
бағалаудың тапсырмалары
Қазақ әдебиеті
пәнінен тоқсанға
Инклюзивті білім
нтізбелік тақырыптық
Зертханалық жұмыс
Әдістемелік кешені
білім берудің
республикасының білім
туралы жалпы
Қазақстанның қазіргі
Қысқа мерзімді
Жұмыс бағдарламасы
атындағы жалпы
қазақ тілінде
қазіргі заман
туралы хабарландыру