Оптимизация линейных моделей в MS Excel производится симплекс-методом - целенаправленным перебором опорных решений задачи линейного программирования. Алгоритм симплекс-метода сводится к построению выпуклого многогранника в многомерном пространстве, а затем к перебору его вершин с целью поиска экстремального значения целевой функции .

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

В последующих лекциях будут подробно разобраны примеры решения типичных задач оптимизации и принятия управленческих решений с помощью надстройки MS Excel " Поиск решения". Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:

• имеется единственная цель, функционально связанная с другими параметрами системы, которую нужно оптимизировать (найти ее максимум, минимум или определенное числовое значение);
• имеются ограничения, выражающиеся, как правило, в виде неравенств (например, объем используемого сырья не может превышать запасов сырья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);
• имеется набор входных значений-переменных, влияющих на оптимизируемые величины и на ограничения.

Параметры задач ограничиваются такими предельными показателями:

• количество неизвестных – 200;
• количество формульных ограничений на неизвестные – 100;
• количество предельных условий на неизвестные – 400.

Алгоритм поиска оптимальных решений включает в себя несколько этапов:

• подготовительные работы;
• отладка решения;
• анализ решения .

Последовательность необходимых подготовительных работ , выполняемых при решении задач экономико-математического моделирования с помощью MS Excel , приведена на блок-схеме рисунка 1.6 .

Рис. 1.6.

Из приведенных пяти пунктов плана подготовительных работ только пятый пункт является формализуемым. Остальные работы требуют творчества - и разными людьми они могут быть выполнены по -разному. Кратко поясним сущность формулировок пунктов плана.

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

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

Таким образом, в диалоговом окне оптимизационной программы " Поиск решения" мы должны задать следующий целевой алгоритм :

Целевая функция равна произведению вектора искомых значений переменных на вектор целевых коэффициентов

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

Значения переменной должны находиться в заданных пределах число исходных элементов системы

Число исходных элементов системы

Число заданных видов ресурсов

Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):

Рис. 1.7.

• если не получено допустимое решение, то выполнить корректировку модели исходных данных;
• если не получено оптимальное решение , то ввести дополнительные ограничения.

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

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

Экономический анализ ставит перед собой следующие цели :

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

Возможные методы анализа представлены в схеме на рисунке 1.8 .

После получения оптимального решения проводится его анализ по полученным отчетам. Анализ устойчивости - изучение влияния изменений отдельно взятых параметров модели на показатели оптимального решения. Анализ пределов - анализ допустимых изменений в оптимальном плане, при котором план остается оптимальным.

Учитывая ответственность принятия экономического управленческого решения , руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:

• "что будет, если…"
• "что надо, чтобы…"

Анализ с целью ответа на первый вопрос называется вариантным анализом ; анализ с целью ответа на второй вопрос называется решениями по заказу.

Вариантный анализ бывает следующих видов:

• Параметрический - анализ, который заключается в решении задачи при различных значениях некоторого параметра.
• Структурный анализ - когда решение задачи оптимизации ищется при различной структуре ограничений.
• Многокритериальный анализ - это решение задачи по разным целевым функциям.
• Анализ при условных исходных данных - когда исходные данные, используемые при решении задачи, зависят от соблюдения дополнительных условий.

После проведения анализа следует представить результаты в графической форме и составить отчет с рекомендациями о принятии решения с учетом конкретной экономической ситуации.

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

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

Рассмотрим следующую задачу линейного программирования в канонической форме:

(1)

(2)

(3)

Метод искусственного базиса

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

Пусть требуется найти максимум функции

при условиях

где первы n элементы нули. Переменные называются искусственными . Векторы столбцы

(28)

образуют так называемый искусственный базис m -мерного векторного пространства.

Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом.

Теорема 4. Если в оптимальном плане расширенной задачи (24)−(26) значения искусственных переменных , то является оптимальным планом задачи (21)−(23).

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

Значение целевой функции при опорном плане (27):

Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M , а другая − нет.

После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m +1)-ю строку помещают коэффициенты, не содержащие M , а в (m +2)-ю строку − коэффициенты при M .

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

Итерационный процесс ведут по m +2 строке до тех пор, пока элементы m +2 строки, соответствующие переменным не станут неотрицательными. При этом, если искусственные переменные исключены из базиса, то найденный план расширенной задачи отвечает некоторому опорному плану исходной задачи.

m +2 строки, столбца x 0 отрицателен, то исходная задача не имеет решения.

Если же не все искусственные переменные исключены из базиса и элемент m +2 строки, столбца x 0 равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.

Если исходная задача содержит несколько единичных векторов, то их следует включить в искусственный базис.

Если в ходе итераций m +2 строка больше не содержит отрицательных элементов, то итерационный процесс продолжают с m +1 строкой, до тех пор, пока не найден оптимальный план расширенной задачи или не выявлен неразрешимость задачи.

Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:

• Составляют расширенную задачу (24)−(26).
• Находят опорный план расширенной задачи.
• Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
• Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.

Для решения задач линейного программирования онлайн, пользуйтесь калькулятором

Дайте понятие проблемы

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

Что понимается под критериями выбора?

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

Какое решение можно считать оптимальным?

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

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

Концепция, утверждающая, что оптимальное решение есть функция факторов среды в самой организации (внутренние переменные) и окружающей  

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

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

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

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

Задача проиллюстрирована рис. 8.3. С помощью модели линейного программирования управляющий может определить, какое количество краски каждого типа производить при известных запасах реагентов и имеющемся резерве времени работы оборудования, а также с учетом вклада в прибыль краски каждого типа. Не имея такой модели, крайне сложно принять оптимальное решение даже в сравнительно простой ситуации.  

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

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

Всякая претендующая на реализацию система экономического саморегулирования должна обеспечивать соблюдение ряда основных принципов социальной справедливости . Прежде всего (и это касается не только геологоразведки) необходимо сделать выбор основного принципа распределения равную оплату за равный труд или равную оплату за равные конечные результаты труда . Дело в том, что в геологии, как ни в какой другой отрасли, ввиду огромных различий естественной производительности труда в зависимости от экономико-географических, геологических и горнотехнических условий эквивалентное количество и качество труда объективно приводит к различным результатам. Поэтому внешне кажется, будто равная оплата за равный труд в этих условиях более справедлива. Ведь неравные условия труда созданы природой и не зависят от исполнителей. Однако этот принцип не стимулирует поиска оптимальных решений в выборе направлений и метода ведения работ. Наоборот, оплата за равные результаты труда максимально стимулирует прогресс, но при этом приведет к значительно большей дифференциации доходов как предприятий, так и отдельных трудящихся. Что предпочесть Нетрудно сформулировать следующее статистическое положение скорость научно-технического и хозяйственного прогресса тесно коррелирует с дифференциацией доходов . На повестку дня встает вопрос быть ли нам значительно более равными по доходам, но существенно беднее, или в среднем значительно богаче, но существенно дифференцированнее по доходам Впрочем, этот вопрос нельзя ставить как альтернативу между двумя крайними существует множество промежуточных положений, из которых можно выбрать подходящее, регулируя оставляемую в распоряжении ПГО долю дифференциальной ренты , образующейся за счет большей естественной производительности труда (дифференциальная рента I). Если эта доля будет существенной, геологоразведочные предприятия будут заинтересованы в проведении работ в первую очередь на объектах с лучшей естественной производительностью труда . Дифференциальную ренту II, по нашему мнению, необходимо целиком оставлять в распоряжении предприятия.  

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

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

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

Способы решения любой проблемы всегда многовариантны. Они не сводятся к простой альтернативе "делать или не делать ". Возможный выбор здесь обычно гораздо более широк, хотя и не очевиден заранее. При этом наиболее выгодными нередко оказываются нетрадиционные, "прорывные" варианты решения проблемы . Обнаружение таких нетривиальных возможностей требует специальных, порой длительных, творческих усилий. Но именно такие варианты обычно дают наибольший экономический эффект . Умение находить нетрадиционные способы (варианты) решения поставленных задач - один из наиболее ярких показателей профессионального уровня руководителя и специалиста. А тщательное многовариантное рассмотрение возможностей является непременным условием отыскания оптимального решения любой достаточно сложной задачи. И нет большей и более досадной ошибки специалистов, принимающих ответственные решения, чем упустить действительно наивыгоднейший вариант просто из-за отсутствия привычки хорошенько подумать.  

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

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

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

Хотя для менеджера идеально достижение оптимального решения, руководитель, как правило, на практике не мечтает о таковом. Исследователь Герберт Саймон указывает, что, решая проблему, руководитель склоняется к поведению, которое он называет удовлетворяющим, а не максимизирующим. Обычно оптимальное решение не обнаруживается из-за нехватки времени и невозможности учесть всю уместную информацию и альтернативы. В силу этих ограничений руководитель, как правило, выбирает направление действия, которое, очевидно, является приемлемым, но не обязательно наилучшим из возможных14.  

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

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

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

Смотреть страницы где упоминается термин Оптимальное решение

:          c.184 ]

Это наилучшее средство для поиска информации на сайте

Данному случаю соответствует взаимная противоречивость ограничений, входящих в задачу.

2) Допустимое множество - выпуклый ограниченный многогранник.

Допустимое множество - выпуклое неограниченное многогранное множество.

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

Возможные случаи оптимальных решений (планов) задачи линейного программирования.

1) Задача не имеет оптимальных решений .

Данный случай может возникнуть: либо тогда, когда допустимое множество решений пусто ("не из чего выбирать" оптимальный план),

либо когда допустимое множество представляет собой неограниченное многогранное множество, и целевая функция на нем неограниченно возрастает (если L  max) или неограниченно убывает (при L min).

2) Задача имеет единственное решение (единственный оптимальный план).

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

3) Задача имеет бесконечное множество оптимальных решений, заданное некоторым линейным образованием - ребром, гранью, гипергранью и т.д. Среди точек этого линейного образования имеются и вершины допустимого множества.

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

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

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

1. Графоаналитический способ решения задач линейного программирования

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

Пусть задача линейного программирования имеет вид:

(1.7)

где с 1 , с 2 , а i 1 , а i 2 , b i - заданные действительные числа; знаки в неравенствах произвольны; целевая функция либо максимизируется, либо минимизируется.

Каждое из неравенств (1.7) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми
;i =1,…,m . В том случае, если система неравенств (1.7) совместна, допустимая область решений задачи есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называютмногоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.

Множеством допустимых решений для данной частной задачи может быть:

пустая область;

выпуклый многоугольник, включая вырожденные случаи - отрезок и единственную точку;

выпуклая многоугольная неограниченная область, включая вырожденные случаи - луч и прямую.

Практическая реализация решения задачи линейного программирования (1.6) – (1.7) на основе ее геометрической интерпретации включает следующие этапы:

1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (1.7) знаков неравенств на знаки равенств.

2. Найти полуплоскости, определяемые каждым из ограничений.

Соответствующая полуплоскость может быть найдена подстановкой в неравенство координат какой-нибудь «простой» точки - (0,0), (0,1) или (1,0). Главное - чтобы эта точка не принадлежала границе полуплоскости. Если после подстановки неравенство окажется справедливым, то выбирается та полуплоскость, где содержится эта точка. Если неравенство не справедлива, то выбирается альтернативная полуплоскость.

3. Определить многоугольник решений, как пересечение найденных полуплоскостей.

4. Построить градиент целевой функции, т.е. вектор
, координатами которого служат коэффициенты целевой функцииL .

Этот вектор определяет направление наискорейшего возрастания целевой функции.

5. Построить ряд линий уровня целевой функцииL , т.е. прямых перпендикулярных градиентуL . При этом построение линий уровня следует вести в направлении градиента, если решается задача на максимум, и в противоположном направлении (в направлении «антиградиента»), если решается задача на минимум. В результате отмечается точка (точки), в которой линии уровня в последний раз касаются допустимого множества.

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

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

Заканчивая рассмотрение геометрической интерпретации задачи (1.6) – (1.7), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1.1 – 1.3. Рис. 1.1 характеризует такой случай, когда целевая функция принимает оптимальное значение в единственной точке А, одной из вершин допустимого множества. На рис. 1.2 оптимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 1.3 изображен случай, когда оптимальное значение целевой функции недостижимо.

Рис. 1.1. Оптимум функции L достижим в точке А

Рис. 1.2. Оптимум функцииL достигается в любой точке отрезка АB

Рис. 1.3. Оптимум функции L недостижим