Название: Математические модели принятия решений в экономике - Розен В. В. Жанр: Экономика Рейтинг: Просмотров: 903 |
Лекция 4. задачи линейного программирования
, Общая задача линейного программирования. Задача 4. Задача производственного планирования. Задача 5. Задача о смеси. Задача 6. Задача о перевозках (транспортная задача). • Основной принцип линейного программирования. Понятие о симплекс-методе. Особенности существования решений в задачах линейного программирования. • Двойственность в линейном программировании. Экономический смысл двойственности. 1. Задача линейного программирования представляет собой частный случай задачи оптимизации при наличии ограничений, который характеризуется тем, что: а) целевая функция является линейной; б) система ограничений, выделяющая допустимую область D, представляет собой систему линейных неравенств. Общая задача линейного программирования (ОЗЛП) может быть задана в следующем виде: найти m&xf(xi,.. ., хп) при ограничениях gi{xi, ...,i„)< h, (4-І) 9т{.Х , . . . , Xji) < bjn, г^е fi 9i, ■ ■ ■, gm — линейные функции n переменных; при этом, как правило, накладываются граничные условия неотрицательности переменных: хі > 0 для всех і — 1, п. Замечание. К общей задаче линейного программирования легко приводится случай, когда вместо максимума требуется найти минимум Целевой функциии в системе ограничений (4.1) знаки неравенств противоположны, а также если некоторые ограничения имеют вид равенств: 3ЗДача нахождения минимума функции / эквивалентна задаче нахожде-*°*я Максимума функции —/; изменение направления знака неравенства эквивалентно умножению обеих частей неравенства на —1, а равенство эквивалентно двум противоположенным неравенствам. ОЗЛП на плоскости (т. е. относительно двух переменных) имеет следующий вид: найти максимум функции f(x,y) = Ах + Ву + С при системе ограничений ах + Ьіу < сі, (4.2) ЄітХ + bmy cm. Так как каждое неравенство a,jx + bjy < Cj (j = l,m) определяет полуплоскость, ограниченную прямой ajx + bjy = Cj, то допустимая область V, выделяемая системой ограничений (4.2), представляет собой в этом случае пересечение конечного числа полуплоскостей, называемое выпуклым многоугольным (или многогранным) множеством. Если выпуклое многоугольное множество ограничено, оно будет выпуклым многоугольником. ОЗЛП в пространстве (т.е. относительно трех переменных) принимает вид: найти максимум линейной функции f(x, y,z) = Ах + By + Cz + D при системе ограничений ах + Ъу + Cz < d (4.3) ЄЬт.Х ~~ Ьту -- CmZ ^ djn. Здесь каждое неравенство ajX+bjy + Cjz < dj (j — l,m) определяет полупространство, ограниченное плоскостью ajX + bjy + CjZ — dj; пересечение конечного числа полупространств называется выпуклым многогранным множеством (ВММ); если это множество ограничено, то оно представляет собой выпуклый многогранник. Та же терминология принимается и для общего случая п переменных (термин плоскость заменяют в общем случае на гиперплоскость). Итак, с геометрической точки зрения ОЗЛП состоит в нахождении максимума линейной функции в допусти-мой области, которая представляет собой выпуклое многогранное множество. Рассмотрим несколько стандартных задач линейного программирования. Задача 4. Задача производственного планирования.
Производственный план (короче — план) формально можно задать ВеКТОрОМ X = (Xl, . . . ,Хп), ГДЄ неотрицательное ЧИСЛО Xi > О указывает количество продукции г'-го типа (г = 1, п), производимое в случае принятия этого плана (некоторые Хі могут быть равны нулю — это означает, что соответствующий тип продукции при этом плане не производится). Перейдем к определению оптимального плана. Определение, а) План называется допустимым, если он может быть реализован, т. е. если для его реализации хватает ресурсов всех типов. б) План называется оптимальным, если, во-первых, он является допустимым, и, во-вторых, дает максимальную прибыль среди всех допустимых планов. Выразим теперь условия допустимости и оптимальности плана. Так как при плане х = (х,..., хп) расход ресурса j-ro типа равен aixi + ■ ■ ■ + aJnxn, а запас ресурса j-ro типа равен Ь3, то для того Чтобы план был реализуемым «по ресурсу j», надо, чтобы выполнялось неравенство ах + ■ ■ ■ + aJnxn < bJ; реализуемость плана «в целом» означает его реализуемость по каждому виду ресурсов и сводится, таким образом, к системе линейных неравенств 'axi + h ахп < bl, < a{xi + ■■■ + а{хп < b (4.4) Kafx1 + --- + a^xn к которой должны быть добавлены граничные условия
неотрицате-тельности переменных: Х > 0,..., хп > 0. Далее, прибыль от реализации плана х = (хх,...,хп) равна
сХ + • ■ • + спхп. Таким образом, задача нахождения оптимального плана
сводится к следующей оптимизационной задаче: найти максимум линейной функции f(xi, ...,хп) = СіХі - h спхп в допустимой области Т>, выделяемой системой линейных
неравенств (4.4) при граничных условиях хг > 0 (г = 1,п). Это — частный
случай общей задачи линейного программирования.
х + 2у < 15, 16в + 6у < 96, 9х + 7у < 69 при граничных условиях неотрицательности х > 0, у > 0. Допустимая область V представляет собой многоугольник (рис. 4.1), ограниченный следующими прямыми: (її) : х + 2у = 15; (h) : 16х + 6у = 96; (^з) : 9х + 7у = 69; (/4) : х = 0; (/5) : у = 0. Целевая функция имеет вид: f(x,y) = 5х + 7у, а семейство линий уровня — это семейство прямых Ъх + 1у = с, где с — константа. Градиентом целевой функции здесь является постоянный вектор g = grad / с координатами (5; 7), который
(4.5) Г х + 2у = 15, 9х + 7у = 69. Решая систему, находим х* — 3, у" = 6. Задача 5. Задача о смеси. Содержательная постановка задачи состоит в следующем. Имеется некоторый набор первичных продуктов, из которых можно составлять различные смеси. Обязательное требование к составляемой смеси заключается в том, что в ней количество питательных веществ (белков, жиров, углеводов, минеральных солей, витаминов и т.п.) должно быть не ниже заданной нормы. Требуется среди всех смесей, удовлетворяющих этому требованию, найти такую, которая имеет минимальную стоимость. Здесь а3\% — количество питательных веществ j-ro типа, которое содержится в единице продукта г'-го типа, сг — стоимость единицы продукта г-го типа, Ъ3 — минимальная норма питательного вещества типа j в смеси (г = 1, п; j = 1, m). Смесь называется допустимой, если содержащееся в ней количество питательного вещества каждого типа не ниже минимальной нормы. Смесь называется оптимальной, если она допустима и среди всех допустимых смесей имеет наименьшую стоимость. Условия допустимости смеси х = (х,..., хп) сводятся к системе линейных неравенств 'ахх Н Ь alnxn > б1, < ахх + ■ ■ ■ + а^Хп > bi, (4.6) kofa;i + -v+o^a;„>b'n, где х > 0,..., хп > 0. ' ' Так как стоимость смеси х равна СХ + • ■ ■ + спхп, то задача нахождения оптимальной смеси сводится к следующей оптимизационной задаче: найти минимум функции f(x,..., хп) = с^х-^ + • • ■ + спхп в области Т>, заданной системой линейных неравенств (4.6) при условии неотрицательности переменных. С учетом замечания на с. 39 сформулированная задача является частным видом общей задачи линейного программирования. Задача 6. Задача о перевозках (транспортная задача). Имеется п пунктов производства (или хранения) некоторого продукта и m пунктов потребления этого продукта. Количество данного продукта в пункте г равно сг, а потребность в нем в пункте j равна bJ (г = 1, п, j = 1, m). Стоимость перевозки единицы продукта из пункта г в пункт j равна d. Как оптимальным образом спланировать перевозки? Решение этой задачи состоит в следующем. Составить план перевозок — значит для каждого пункта производства г и для каждого пункта потребления j указать количество х3 продукта, которое должно перевозиться из і в j при этом плане. Таким образом, математически план перевозок может быть задан в виде неотрицательной матрицы х = \х3г\ (г = l,n; j = l,m). Установим условия допустимости (т.е. реализуемости) такого плана. Общее m количество продукта, вывозимое из пункта г, есть ^ х3, а общее .7 = 1 п количество продукта, доставляемого в пункт j, равно ^ х. План будет допустимым, если, во-первых, для каждого пункта производства вывезенное количество продукта не превышает его наличного количества, и, во-вторых, должны быть удовлетворены потребности в данном продукте всех пунктов потребления. Итак, условия допустимости плана х — ЦхЩ принимают следующий вид: m ^х\<сг, i = T~R, (4.7) j=i n Y,xl=V, j =17^. (4.8) г=і (Заметим, что условия допустимости могут быть выполнены тогда, когда общая потребность в данном продукте не превышает его т п общего запаса, т.е. когда ]Г) Ъ3 < ]Г) сг.) 3=1 г=1 План перевозок называется оптимальным, если он является допустимым и среди всех допустимых планов перевозок имеет наименьшую стоимость. Общая стоимость всех перевозок при плане перевозок х = \х^\ может быть представлена в виде п тп г = 1 j = l (считается, что стоимость перевозок продукта пропорциональна его количеству). Итак, задача нахождения оптимального плана перевозок сводится к нахождению минимума функции (4.9) при ограничениях (4.7), (4.8) и граничных условиях неотрицатетельности переменных. Данная задача с учетом замечания на с. 39 является частным случаем общей задачи линейного программирования. 2. Сформулируем основной принцип линейного программирования. Он базируется на следующем утверждении. Правило 4.1. Линейная функция п переменных, заданная в области Т) С R™ и отличная от постоянной, может достигать глобального экстремума только на границе области Т>. Для простоты записи рассмотрим случай функции трех переменных f(x, у, z) = Ах + By +Cz + D. Градиент функции / является здесь постоянным вектором с координатами (А, В, С), причем так как функция / отлична от постоянной, ее градиент не равен нулю. На основании принципа стационарности и замечания к нему (см. лекцию 3, п. 1) получаем, что функция / не может достигать глобального экстремума ни в какой внутренней точке области Т>. Отсюда и следует утверждение правила 4.1. Рассмотрим теперь линейную функцию /, заданную на выпуклом многограннике Т> С R™. Так как выпуклый многогранник представляет собой замкнутое и ограниченное множество, то согласно теореме Вейерштрасса (см. лекцию 3, п. 1) функция / достигает на нем глобального максимума; учитывая правило 4.1, приходим к следующему утверждению. Следствие. Линейная функция /, заданная на выпуклом многограннике Т> С R™, достигает как глобального минимума, так и глобального максимума на границе многогранника Т>. Теперь, чтобы сформулировать основной принцип линейного программирования, остается сделать одно уточнение к указанному следствию; оно состоит в том, что линейная функция, заданная на выпуклом многограннике, достигает своих экстремумов в некоторых вершинах этого многогранника. Обоснуем это утверждение, ограничиваясь случаем функции трех переменных. Согласно приведенному выше следствию, глобальный экстремум функции / достигается на границе многогранника V. Граница выпуклого многогранника представляет собой объединение выпуклых многоугольников. Предположим, что функция / достигает, например, глобального максимума в некоторой внутренней точке Мо многоугольника Р, представляющего собой часть границы выпуклого многогранника V (рис. 4.2). Тогда градиент функции / в точке Мо должен быть перпендикулярен плоскости многоугольника Р. В самом деле, если бы это было не так, то можно было бы сдвинуться из точки Мо в некоторую точку Mi £ Р ло направлению вектора а, составляющему острый угол с вектором g = grad/ІМо- Так как разность /(Mi) - /(М0) представима в виде скалярного произведения g на вектор смещения MqMi, то учитывая, что g • МоМ > 0, получаем /(Мх) > /(Мо) в противоречие с тем, что Мо — точка глобального максимума функции / в области Т>. Из условия перпендикулярности градиента g плоскости Многоугольника Р сразу следует, что функция / является постоянной на Р, значит, она достигает глобального максимума в любой вершине многоугольника Р. Итак, получаем следующее правило. Правило 4.2 (Основной принцип линейного программирования). Линейная функция, заданная на выпуклом многограннике D С IR™, достигает как глобального минимума, так и глобального максимума в некоторых вершинах этого многогранника.
На правиле 4.2 основаны общие алгоритмы нахождения решения задач линейного программирования. В принципе можно найти точки глобального экстремума линейной функции, заданной на выпуклом многограннике, с помощью перебора его вершин. Однако технические сложности процедуры перебора вершин многогранника настолько существенны, что, за исключением простейших случаев, этот метод в практическом отношении бесполезен. Самый известный алгоритм решения задач линейного программирования — симплекс-метод — использует «направленный перебор», когда, например, при поиске глобального максимума, вначале находят какую-нибудь вершину допустимого многогранника, а затем переходят к таким соседним вершинам этого многогранника, в которых значения целевой функции увеличиваются (алгоритм симплекс-метода детально описан во многих учебниках). В заключение отметим некоторые особенности, относящиеся к существованию решений в задачах линейного программирования (в качестве иллюстрации используются задачи линейного программирования на плоскости). Может быть несколько основных случаев. Допустимая область Т> есть пустое множество (рис. 4.3). Это означает, что система ограничений является несовместной. Тогда ни допустимых, ни оптимальных решений нет. Допустимая область Т> ограничена. Тогда она представляет собой выпуклый многогранник, который является всегда замкнутым. Так как линейная функция непрерывна, то, в силу теоремы Вейерштрасса (см. лекцию 3), в этом случае целевая функция достигает в области Т> как глобального минимума, так и глобального максимума. По правилу 4.2 точками глобального минимума и глобального максимума являются некоторые вершины выпукло-
го многогранника D (рис. 4.4). При этом один из экстремумов, а также оба они могут достигаться во всех точках некоторого ребра многогранника V (в общем случае — во всех точках некоторого многогранника меньшей размерности); последняя ситуация показана на рис. 4.5. Рис. 4.7
В компактной записи система ограничений такой задачи имеет вид следующей системы линейных неравенств: п £)a?a:, при граничных условиях х, > 0 (г = 1, п), а целевая
функция имеет вид f(xl,...,Xn)=ClXl- Ь СпХп = (с, х). Напомним, что общая задача линейного программирования состоит
в максимизации целевой функции (с, х) при системе ограничений (4.10). Назовем
эту задачу прямой задачей линейного программирования. Тогда двойственная ей задача линейного программирования
формально строится по той же матрице, в которой строки и столбцы меняются
ролями и, кроме того, знаки неравенств в системе ограничений меняются на обратные.
Для записи системы ограничений двойственной задачи, во-первых, введем
двойственные переменные у — (у1,.. ., ут). Система ограничений двойственной
задачи имеет вид следующей системы линейных неравенств: т Х>г^>Сг, *=Т7^, (4.11) При граничных условиях у3 > 0 (j = l,m), а целевая
функция 5(2/1,...j2/m)=012/1+--- + bm2/m = (b,2/). Бели прямая задача линейного программирования состоит в
нахождении максимума целевой функции, то двойственная задача состоит в
нахождении минимума целевой функции (о, у) при системе ограничений (4.11). Можно показать, если допустимые области как прямой, так и
двойственной задачи линейного программирования не пусты, то и прямая, и
двойственная задачи имеют решение.
Рассмотрим задачу о смеси, заданную таблицей типа табл. 4.5, где {#!,...,#„} — первичные продукты, из которых составляется смесь, а в качестве питательных веществ берутся белки (Б), жиры (Ж) и углеводы (У). Прямая задача линейного программирования в данном случае имеет следующий вид: найти минимум функции f(x і,.. ., xn) = сХ ! + ••• + cnxn при системе ограничений { ах 1-І Ь ахг Л f- ахп > Ъ1, ахх + --- + а2хг + --- + а2пхп > о2, (4.12) ах і + • • • + а3хг Н + ахп > Ь3 4 граничных условиях х і > 0,..., хп > 0. Построим двойственную задачу линейного программирования. Система ограничений двойственной задачи принимает вид 'aly1 + а2у2 + ау3 < сь
< агУ + а2у2 + а3у3 < а, (4.ІЗ)
с граничными условиями у1 > О, у2 > О, у3 > 0. Целевая функция двойственной задачи есть д^у1, у2, у3) = Ь1?/1 + Ь2у2 + Ь3у3. Двойственная задача формулируется следующим образом: найти максимум функции д(у1, у2, у3) при системе ограничений (4.13). В чем состоит в данном случае экономический смысл двойственной задачи? Предположим, что некая фирма А продает первичные продукты {Пі,..., Пп} по цене Сі за единицу продукта Щ (i = 1,п). Возникает конкурирующая фирма В, которая предлагает покупателям не сами первичные продукты Пі,..., Пп, а белки, жиры и углеводы «в чистом виде» (например, в виде таблеток, или «на вес»). Пусть у1, у2, у3 — цена «единицы белков», «единицы жиров» и «единицы углеводов» соответственно. Так как единица продукта Пг может быть заменена набором, состоящим из а ед. белков, а2 ед. жиров и а?ед. углеводов (будем записывать такой набор в виде аБ ф а?Ж© фа3У), то покупатель сможет предпочесть такой набор единице продукта П только в том случае, когда стоимость этого набора будет не больше стоимости единицы продукта Щ, т.е. когда ajy1 + а2у2 + а3у3 < а, но это и есть как раз неравенство, входящее в систему ограничений двойственной задачи. Далее, если покупатель приобретает белки, жиры и углеводы «в чистом виде», то для получения требуемой смеси он должен приобрести набор, состоящий из Ь1 ед. белков, Ь2 ед. жиров и Ь3ед. углеводов, т.е. набор ЬХБ @Ъ2Ж ®Ъ3У. Стоимость такого набора равна Ь1?/1 + Ъ2у2 + Ь3у3, что совпадает с целевой функцией двойственной задачи.
Итак, в данном случае смысл двойственных переменных у1, у2, у3 — это цены, назначаемые за единицу белков, жиров и углеводов соответственно. Экономический смысл оптимального вектора цен у = (у1 ,у2,у3) состоит в следующем. а) Допустимость вектора цен у = (у1, у2, у3) означает, что «це- ны должны быть не слишком высокими»; точнее, такими чтобы покупателю было выгодно вместо покупки единицы каждого про- дукта Щ купить по этим ценам эквивалентный ему набор аБ фа2Ж ©а3У, г = T~n. б) Оптимальность вектора цен состоит в том, что «цены долж- ны быть не слишком низкими». Точнее, среди всех допустимых век- торов цен оптимальный вектор цен характеризуется тем, что при покупке набора ЬХБ © Ь2 Ж © Ь3 У по оптимальным ценам он при- носит фирме В наибольший доход. |
| Оглавление| |
- Акмеология
- Анатомия
- Аудит
- Банковское дело
- БЖД
- Бизнес
- Биология
- Бухгалтерский учет
- География
- Грамматика
- Делопроизводство
- Демография
- Естествознание
- Журналистика
- Иностранные языки
- Информатика
- История
- Коммуникация
- Конфликтология
- Криминалогия
- Культурология
- Лингвистика
- Литература
- Логика
- Маркетинг
- Медицина
- Менеджмент
- Метрология
- Педагогика
- Политология
- Право
- Промышленность
- Психология
- Реклама
- Религиоведение
- Социология
- Статистика
- Страхование
- Счетоводство
- Туризм
- Физика
- Филология
- Философия
- Финансы
- Химия
- Экология
- Экономика
- Эстетика
- Этика
Лучшие книги
Гражданский процесс: Вопросы и ответы
ЗАПАДНОЕВРОПЕЙСКОЕ ИСКУССТВО от ДЖОТТО до РЕМБРАНДТА
Коммуникации стратегического маркетинга
Консультации по английской грамматике: В помощь учителю иностранного языка.
Международные экономические отношения