АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

― Ты знаешь, что самое плохое в моей работе? – спросил Торн. – Никто не понимает, что это бизнес. Вот и всё. На моей памяти люди пятнадцать раз пытались нападать из засады на клетки где-то между Новым Лондоном и мортской границей, чтобы остановить доставку груза. Сразу за Крайзом на сотни тысяч миль ничего нет, кроме пастбищ и полей, поэтому в пшенице смогла бы засесть целая армия. И знаешь, в десяти случаях у меня просто получалось отговорить их от этой глупой затеи. Это было нетрудно, и я не наказывал их.

― Ну да, ― пробормотал Джавель.

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

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

― Но остальные пять...

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

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

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

― Что ты с ними сделал?

― Они послужили наглядным примером, ― ответил Торн. ― Некоторые испытывают трудности с математикой, но наглядный пример быстро помогает им всё усвоить. Конечно, я сожалел, что это было необходимо...

«Да уж конечно, ублюдок, ― подумал Джавель. ― Как пить дать».

―... но так уж вышло. И ты будешь поражён, узнав, как быстро эти примеры заставляли людей вести себя смирно. Взять тебя, к примеру...

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

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

Джавель вспомнил один слушок, однажды донёсшийся до него: о том, что мать Торна работала проституткой в Кишке и продала своего сына работорговцу спустя всего лишь несколько часов после его рождения. Живот Джавеля опять скрутило, на сей раз сильнее, словно кто-то просунул руку ему в пупок, взял внутренности в кулак и сжал, превращая их в кашу. Он откинулся назад, медленно дыша и пытаясь вспомнить план действий, но боль здорово поумерила его пыл, подогретый виски. Он всегда боялся боли как ребёнок.

― Так что теперь, Джавель, вопрос в том, хочешь ли ты по-прежнему напасть на меня или поговорить о деле?

― Поговорить о деле, ― выдохнул стражник.

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

― Хорошо. Давай поговорим о твоей жене.

― При чём тут она?

― Она жива.

― Чушь! ― рявкнул Джавель.

― Это правда. Она жива, и ей хорошо в Мортмине. ― Торн склонил голову набок, словно делая акцент на своих следующих словах. ― Довольно-таки хорошо.

Стражник поморщился.

― Откуда ты знаешь?

― Просто знаю. Я даже знаю, где она.

― И где же?

― Думаешь, я стану раскрывать все свои карты? На данный момент, страж Ворот, тебя должно заботить не это, а то, что я точно знаю, где она, и – что важнее – могу вернуть её обратно.

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

Но затем, спустя шесть месяцев после дня рождения, она взяла ткацкие станки и начала работать на них, мастеря шапки, перчатки и шарфы, а позднее свитера и одеяла. Не самого большого жалованья Джавеля всегда хватало на то, чтобы покупать материал для жены, и к тому времени, как выпал её жребий, она уже ткала большую часть их зимней одежды, которая была тёплой и удобной. После того как Элли увезли в Мортмин, Джавель всё никак не мог упаковать её вещи, и её швейная корзина по-прежнему стояла у камина, а на станках висела незаконченная шапка. Ему нравилось смотреть на эту корзину, полную заготовок: казалось, что Элли просто ушла погостить к родителям и в один прекрасный день вернётся. Порой, напиваясь особенно сильно, он садился напротив камина, ставя корзину себе на колени, и это помогало ему засыпать. Он бы никогда никому не смог рассказать об этом.

Но он всё ещё переживал по поводу тех шести месяцев. Когда Элли забрали, Джавель нанял женщину, которая стала убирать в доме и заниматься стиркой. Спустя несколько недель он взял швейную корзину, показал этой женщине ткацкие станки и спросил, что с ними было не так. Вот таким образом Джавель и узнал, что это были вовсе не ткацкие станки: он купил своей жене вязальные спицы. Ткачество и вязанье были двумя разными вещами, и хотя он знал это, объяснить эту разницу он бы не смог.

И Элли, которая обычно сразу говорила ему, если он делал что-нибудь не так, на сей раз не сказала ни слова, учась вязанию в течение шести месяцев, пока он был на работе. У Джавеля было много поводов для сожаления, связанных с женой, и каждый день к ним добавлялись новые, но одним из самых больших и странных сожалений было то, что он так и не узнал про вязальные спицы до её отправки в Мортмин. Порой, просыпаясь утром в их общей кровати (на всё той же стороне, потому что он не мог больше спать на стороне Элли, словно задыхаясь там), Джавель думал, что мог бы отдать всё на свете, лишь бы Элли узнала, что он понял свою ошибку с вязальными спицами. Ему казалось жизненно важным то, чтобы она узнала, что он понял это.

― С чего мне верить в то, что ты можешь вернуть её?

― Я могу, ― ответил Торн. ― И я сделаю это.

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

― Ты должен доверять мне, Джавель. Я не нарушаю своего слова.

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

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

― Успокойся, Брен, ― тихо сказал Торн. ― Мы здесь уже почти закончили.

Женщина послушалась и снова положила руку себе на колени. По телу Джавеля пошли мурашки.

― Что тебе нужно?

Чиновник одобрительно кивнул.

― Мне нужно пронести кое-что в Крепость. Мне нужен свой человек у Крепостных Ворот, который в определённый момент не стал бы задавать лишних вопросов.

― Когда?

― Когда я скажу.

Джавель посмотрел на него, озарённый пониманием.

― Ты собираешься убить Королеву.

Торн направил на него свой холодный непреклонный взгляд. Стражник подумал о видении, которое явилось ему на Крепостной лужайке: высокая женщина постарше нынешней Королевы, с непоколебимым видом нёсшая корону на голове. От Виля, который всегда первым был в курсе всего, он знал, что два дня назад состоялась коронация, и во время церемонии произошло неудачное покушение Регента на новую Королеву. Проезжая по улицам в сумерках через обычную какофонию звуков, доносившихся от торговцев, которые закрывали лавки, выкрикивали новости торговли и сплетничали, Джавель услышал, как они назвали её Истинной Королевой. Ему было незнакомо это понятие, но двух мнений тут быть не могло: это имя принадлежало высокой женщине с серьёзным лицом, которую он видел на Крепостной лужайке и которая пока вообще не существовала.

«Но она могла, ― подумал Джавель. – Когда-нибудь она появится».

И хотя он не ходил в церковь и даже не верил в Бога с тех пор, как Элли отправили в Мортмин, ему внезапно почувствовалось проклятие, повисшее над его головой, проклятие и история, словно две руки, выжидавшие, чтобы взять его и сильно сжать. Людей, убивших Джонатана Тира, так и не поймали, и это были самые чёрные страницы в истории Тирлинга. Кто бы они ни были, Джавель не сомневался, что они были прокляты за свои преступления. Но он не мог высказать все эти страхи Торну, поэтому лишь произнёс:

― Она Королева. Ты не можешь убить Королеву.

― Нет доказательств того, что она действительно Королева. Это всего лишь девчонка со шрамом от ожога и ожерельем.

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

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

«Это и есть та тёмная трещина, ― наконец, осознал стражник. ― Прямо здесь».

Его снова согнуло пополам: казалось, какой-то маленький зверь в его желудке пробудился и начал разрывать плоть своими неровными когтями и зубами, острыми как иглы. Джавель шёл по лезвию ножа. Его путь был короток, но внизу лишь чернела бесконечная тьма. Что он увидит, когда будет падать?

― Что если твой план провалится? ― выдохнул он. ― Какие у меня гарантии?

― Никаких, ― ответил Торн. ― Но тебе не следует беспокоиться. Только глупец складывает все яйца в одну корзину. У меня же корзин много. Если одна идея не сработает, то мы попробуем другую и, в конце концов, преуспеем.

Достав из рубашки пузырёк с янтарной жидкостью, он предложил его Джавелю, который протянул руку, но схватил лишь воздух.

― По моим подсчётам у тебя есть минута или две, прежде это станет для тебя бесполезным. Итак, страж Ворот, у меня есть только один вопрос: ты в ладах с математикой?

«Мне не победить», ― подумал Джавель, держась за живот.

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

Груз опоздал.

Королева Мортмина не смогла выкинуть это из головы ни сегодня, ни вчера, ни позавчера. Она пыталась сконцентрироваться, пока Аукционист приводил ей цифры за последний месяц. Февраль получился неплохим: в королевскую казну поступило свыше пятидесяти тысяч марок. Обычно по прибытии груза Королева отбирала самый лучший товар либо для себя, либо кому-нибудь в подарок. Но большинство рабов уходили с молотка мортским нобилям или состоятельным дельцам, которые перепродавали их за более высокую цену в северных и окрестных городах. Аукцион всегда приносил хорошую прибыль, однако высокий уровень февральских продаж не мог избавить Королеву от назойливого ощущения грядущей неудачи, будто проблема становилась всё серьёзнее, и она никак не могла помешать этому. Девчонке исполнилось девятнадцать, её так и не нашли, а теперь ещё и груз не пришёл вовремя. Что бы это могло значить?

Наверняка, тирский Регент опять в чём-то напортачил. Сначала ему не удалось помешать Элиссе тайком вывезти девчонку из замка (хотя даже сама Королева не смогла предугадать такое развитие событий: кто бы мог подумать, что в Элиссе есть хотя бы крупица хитрости?). Но спустя восемнадцать лет эту девчонку уже следовало найти. По настоянию Королевы Регент, наконец, нанял людей из Кейдена несколько месяцев назад, но она откуда-то знала, что уже было слишком поздно.

― Это всё, ваше Величество.

Бруссар, её Аукционист, убрал бумаги в сумку.

― Хорошо.

Он не двигался с места, зажав сумку в руках.

― Да?

― Что насчёт нового груза, Ваше Величество?

Даже её люди не позволяли ей забыть об этом.

― Бруссар, как только я что-нибудь узнаю, то ты тоже это узнаешь. Иди и готовься к своему аукциону. И в этот раз не забудь отсеять и избавиться от бездельников.

Аукционист покраснел и сжал челюсти, скрытые бородой. Он хорошо делал свою работу, обладая врождённой способностью превращать живой товар в деньги. Много лет назад, когда аукцион был ещё всем в диковинку, Королева садилась на низкий балкон десятого числа каждого месяца и с удовольствием наблюдала, как Бруссар выжимал последнюю возможную прибыль за каждый фунт человеческого тела. Что-то внутри неё радовалось при виде тирцев, продаваемых с молотка. Но однажды, около пяти лет назад, один из помощников Бруссара проявил небрежность при проведении дезинсекции, и вскоре Дворец и несколько дворянских поместий заполонили вши.

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

Он ушёл, держа сумку, как мать держит своё единственное дитя. Королева с удовлетворением отметила, что он напряжённо и обиженно сгорбил спину, но это не приглушило шёпот у неё в голове и тот тихий вопрос, изводивший её уже насколько дней: где груз? На доставку уходило четыре дня при хорошей погоде и пять при плохой. Он никогда не приходил позднее пятого числа. Сегодня же было 6 марта. В случае какой-нибудь проблемы Регент или Торн уже бы известили её. Королева прижала ладонь ко лбу, чувствуя надвигавшуюся боль в висках. Её организм был настолько хорош, что она даже почти никогда не болела. Единственным исключением были головные боли, возникавшие из ниоткуда, не имевшие объяснения с точки зрения медицины и столь же быстро проходившие.

«А что если груз вообще не придёт?»

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

Неожиданно Королева поняла, что ей не хватает Лирианы. Как и все её слуги, предсказательница состарилась, хотя сама она оставалась молодой, и несколько лет назад отошла в мир иной. Лириана обладала истинным зрением и могла видеть не только будущее, но и настоящее с прошлым. Уж она бы увидела, что произошло в Тире. Как Королева ни убеждала себя, она не могла избавиться от навязчивых подозрений, что возможная проблема была связана именно с девчонкой. Если её не убили в пути, то сейчас она уже должна была достигнуть Крепости. Смог ли Торн позаботиться обо всём? На Регента ни в чём нельзя было положиться, в отличие от Торна. Если он не преуспел, то что следует делать дальше? Нарушить договор и развязать войну? Королеве изначально не хотелось вторгаться в Тирлинг. Для захвата и владения чужой территорией требовались деньги, оснащение, вооружение. Всё это доставило бы немало трудностей. Взимать дань было проще, это считалось идеальным решением.

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

Снаружи послышалась какая-то суматоха. Подняв взгляд, Королева увидела, как Берилл, её камердинер, направился к большим дверям её комнаты для аудиенций. Он со всем разберётся. Со смертью Лирианы Берилл стал старейшим и самым преданным слугой Королевы, настолько хорошо знавшим все пожелания своей хозяйки, что ей даже не приходилось спрашивать его о повседневных делах в замке. Посмотрев на часы, она решила пойти в свою комнату и потребовать ранний ужин, после чего развлечься с одним из рабов. С тем высоким, мускулистым, похожим на кузнеца, мужчиной с тёмными густыми волосами и бородой, которого отобрали из последней партии тирского товара. Только в Тирлинге мужчины были столь высокого роста.

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

Вдоль стен коридора выстроились стражники, предусмотрительно опустившие глаза. При виде их её радостное возбуждение несколько поубавилось. В последнем докладе Регента сообщалось, что большинство королевских стражников ушли из замка на поиски девчонки. Кэрролл, Булава, Элстон… Королева помнила эти имена и понимала, что не следует недооценивать этих людей. Если бы она встретила Булаву раньше Элиссы, то всё бы могло быть по-другому. Тирские сапфиры исчезли, словно растворившись в воздухе, и здесь ясно чувствовались происки Булавы. Если бы только ей удалось забрать драгоценности до смерти Элиссы! Возможно, у неё бы больше не было головных болей, и ей бы почти не требовались лекарства.

Но теперь всё наладится. Она получит сапфиры, а после прибытия груза, пожалуй, стребует с Регента кругленькую сумму за задержку. Он будет ныть и жаловаться, но всё заплатит. Представив себе его бледное огорчённое лицо, Королева улыбнулась и разделась, предвкушая, как ей приведут раба. Её пажи работали быстро. Она не пробыла в своих покоях и пяти минут, как раздался стук в дверь.

― Входи! ― рявкнула она, с раздражением почувствовав, что головная боль усилилась.

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

Дверь отворилась. Королева повернулась к вошедшему Бериллу и хотела попросить его принести ей порошок от головной боли, но слова застряли у неё в горле. Лицо её камердинера побелело, глаза были полны страха. В трясущейся руке он сжимал свиток бумаги.

― Леди, ― сказал он дрожащим голосом.

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

Рассмотрим задачу линейного программирования с двумя переменными. В общем виде она выглядит следующим образом:

где ;

x_1,2 – переменные;

a_i1, a_i2, b_i, c₁, c₂ - константы;

m – число ограничений.

2.2.1 Построение области допустимых планов

В двумерной системе координат каждое из неравенств системы ограничений определяет полуплоскость с граничной прямой a_i1x₁ + a_i2x₂ = b_i, а уравнение - саму прямую. Пересечение этих полуплоскостей и прямых и представляет собой ОДП задачи.

ОДП задачи может быть:

а) пустой

Это происходит в том случае, если эти полуплоскости и прямые не пересекаются.

Например, предположим, что в задаче из раздела 1.1 требуется произвести не менее 1200 т карамели «Снежинка». Тогда в систему ограничений добавится неравенство х₁ ³ 1200. Ему будет соответствовать полуплоскость, которая не пересекается с четырехугольником, представленным на рисунках 6-9 (т.е. пересечение – пустое множество). График примет вид, представленный на рисунке 10. В самом деле, выделенные ресурсы не позволяют выпустить такое количество карамели, и выполнить поставленные условия невозможно (допустимых планов, действительно, нет).

б) непустой

Непустая ОДП может быть:

1 ограниченной

Ограниченная ОДП может быть одномерна (представлять собой отрезок или точку) либо двумерна (представлять собой многоугольник).

Например, ОДП на рисунках 6-9 представляет собой многоугольник (четырехугольник).

Если бы требовалось израсходовать ровно 800 т сахара, не больше и не меньше, то первое ограничение этой задачи представляло бы собой уравнение. Тогда допустимыми планами были бы точки только на соответствующей прямой, а не во всей полуплоскости. ОДП являлась бы отрезком (на рисунке 11 этот отрезок выделен более жирной линией).

Теперь, например, предположим, что в задаче из раздела 1.1 требуется произвести не менее 1000 т карамели «Снежинка». Тогда в систему ограничений добавится неравенство х₁ ³ 1000. Ему будет соответствовать полуплоскость, которая пересекается с четырехугольником, представленным на рисунках 6-9, в единственной точке (1000; 0) (эта точка выделена на рисунке 12). Эта точка и будет представлять собой ОДП задачи – единственный допустимый план при таких условиях (разумеется, он же будет и оптимальным).

2 неограниченной

Неограниченность ОДП означает, что существуют допустимые планы со сколь угодно большими по модулю значениями хотя бы одной из координат. Неограниченная ОДП также может быть одномерна (луч, прямая) и двумерна (полуплоскость, многоугольная область).

Например, пусть в задаче из раздела 1.1 запасы ресурсов не ограничены, но при этом требуется израсходовать на производство соответственно не менее 800, 600 и 120 т трех видов ресурсов. Тогда в трех неравенствах системы ограничений знак неравенства изменится на противоположный, и система примет вид:

0,8х₁ + 0,5х₂ ³ 800

0,2х₁ + 0,4х₂ ³ 600

0,01х₁ + 0,1х₂ ³ 120

х_1,2 ³ 0

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

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

Предположим, например, что в задаче поставлено единственное ограничение (помимо ограничений неотрицательности) – выпустить ровно 1000 т карамели «Снежинка» (х₁ = 1000). Тогда ОДП задачи будет представлять собой луч (полупрямую), представленный на рисунке 14 (ОДП выделена более жирной линией). Эта ОДП тоже не ограничена, так как одна координата – х₂ - может принимать сколь угодно большие значения.

Чтобы привести пример ОДП в виде полуплоскости, рассмотрим задачу с единственным ограничением: х₂ £ -2. Такая ОДП заштрихована на рисунке 15. Она тоже неограниченная: здесь обе координаты могут принимать бесконечно большие по модулю значения (х₁ - вообще любые, а х₂ – отрицательные).

Чтобы привести пример ОДП в виде прямой, рассмотрим задачу с единственным ограничением: х₁ - х₂ = 2. Неограниченная ОДП выделена более жирной линией на рисунке 16.

Из проведенных рассуждений видно, что задача линейного программирования может иметь 0, 1 или бесконечное множество оптимальных планов. При этом можно сказать, что любая точка на отрезке между допустимыми планами тоже будет допустимым планом*.

2.2.2 Нахождение оптимального плана

Зафиксировав значение целевой функции равным некоторому числу z, можно построить прямую с₁х₁ + с₂х₂ = z. Эта прямая называется линией уровня целевой функции. Различным значениям z будут соответствовать прямые, параллельные друг другу, причем все они будут перпендикулярны градиенту целевой функции. Координаты градиента будут определяться коэффициентами целевой функции при соответствующих переменных (так как функция линейная, ее частные производные будут константами).

Итак, пусть поставлена задача на максимум (целевая функция максимизируется). Чтобы определить направление роста целевой функции, проведем на графике вектор из начала координат в точку (с₁; с₂) (можно указать направление градиента и любым другим способом). Проведем перпендикулярно градиенту линию уровня и будем сдвигать ее в направлении градиента до крайнего положения. Крайнее положение линии уровня - это такое ее положение, в котором она еще пересекает ОДП, но если сдвинуть дальше, то перестанет ее пересекать.

Точка пересечения крайнего положения линии уровня и ОДП представляет собой точку оптимума (точку максимума, оптимальный план) Х^* (х₁^*, х₂^*). Координаты этой точки получают путем решения соответствующей системы уравнений.

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

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

Дата добавления: 2015-01-18 | Просмотры: 1105 | Нарушение авторских прав