Аннотация: Данная лекция раскрывает ряд вопросов, посвященных линейному программированию как одному из разделов математического программирования; в частности, формулирует основные виды задач линейного программирования, раскрывает отличия данных задач от классических задач математического анализа; знакомит с различными формами записи данных задач, осуществляет их постановку и исследование структуры. Наиболее полно раскрыт вопрос о решении задач линейного программирования симплекс-методом.
– это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями.
Наличие ограничений делает задачи принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.
Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.
Можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач.
В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:
Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования .
Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.
Термин " линейное программирование " возник в результате неточного перевода английского " linear programming ". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского " linear programming " было бы не " линейное программирование ", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.
Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.
Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.
Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.
Общая форма задачи имеет вид: найти при условиях
Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме
Т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I 2 = 0 , а в другом - I 1 = 0 .
Задача ЛП в канонической форме.
Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин.
Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов (алгоритм), логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика совмещаются с логически обоснованным пониманием сущности изучаемого явления.
С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах), решается задача рационального раскроя материалов (с оптимальным выходом заготовок). В сельском хозяйстве он используется для определения минимальной стоимости кормовых рационов при заданном количестве кормов (по видам и содержащимся в них питательным веществам). Задача о смесях может найти применение и в литейном производстве (состав металлургической шихты). Этим же методом решаются транспортная задача, задача рационального прикрепления предприятий-потребителей к предприятиям-производителям.
Все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Решить такую задачу - значит выбрать из всех допустимо возможных (альтернативных) вариантов лучший, Оптимальный. Важность и ценность использования в экономике метода линейного программирования состоят в том, что оптимальный вариант выбирается из весьма значительного количества альтернативных вариантов. При помощи других способов решать такие задачи практически невозможно.
В качестве примера рассмотрим решение задачи рациональности использования времени работы производственного оборудования.
В соответствии с оперативным планом участок шлифовки за первую неделю декабря выпустил 500 колец для подшипников типа А, 300 колец для подшипников типа Б и 450 колец для подшипников типа В. Все кольца шлифовались на двух взаимозаменяемых станках разной производительности. Машинное время каждого станка составляет 5000 мин. Трудоемкость операций (в минутах на одно кольцо) при изготовлении различных колец характеризуется следующими данными (табл. 6.5).
Таблица 6.5
Следует определить оптимальный вариант распределения операций по станкам и время, которое было бы затрачено при этом оптимальном варианте. Задачу выполним симплексным методом.
Для составления математической модели данной задачи введем следующие условные обозначения: jc, х2, хъ, - соответственно количество колец для подшипников типов Л, Б, В, производимых на станке I; х4, х5, х6, - соответственно количество колец для подшипников типов А, Б, В, производимых на станке II.
Линейная форма, отражающая критерий оптимальности, будет иметь вид:
min а(х) = 4x,-f 10x2-f 10x3-f 6x4-f 8х5+20х6 при ограничениях
4х, -f 10х2 -f 10;t3 lt; 5000
6х4 -f 8х5 -f 20х6 ~lt; 5000
х, = 500
х2 +х5 = 300
х3 +х6 = 450
Xj^0,j=l, ..., 6
Преобразуем условие задачи введением дополнительных (вспомогательных) и фиктивных переменных. Условие запишем так:
шіп lt;х(х) = 4дг, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Мх9 + Мх{0+Мх{,
Система уравнений, отражающая ограничительные условия машинного времени и количество произведенной продукции:
4х, + l(bc2 + 10х3 +х1 = 5000
6х4 + 8х5 + 20х6 + xs = 5000
Xj +х4 +х9 = 500
х2 +х5 +х10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Решение этой задачи представлено в табл. 6.6. Оптимальный вариант получен на седьмом этапе (итерации). Если бы на станке I производилось 125 колец подшипников типа А, 450 колец подшипников типа В, на станке II - 375 колец подшипников типа А и 300 колец подшипников типа Б, то при такой загрузке оборудования было бы высвобождено 350 мин машинного времени станка II. Общие затраты времени по оптимальному варианту составили бы 9650 мин, тогда как фактически затрачено 10000 мин машинного времени.
Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Ее смысл заключается в минимизации грузооборота при доставке товаров широкого потребления от производителя к потребителю, с оптовых складов и баз в розничные торговые предприятия. Она решается симплекс-методом или распределительным методом.
Решение транспортной задачи распределительным методом было дано в третьем издании учебника «Теория экономического анализа» («Финансы и статистика», 1996).
Решение задачи рациональности использования станков симплексным методом
| Базис | с | Ро | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | м | м | м |
| Л | Рг | Ръ | Л | Р ъ | | Pi | Р8 | р* | Л 0 | Л, |
|||
| Л | 0 | 5000 | 4 | 10 | 0 | 0 | 0 | 0 | і | 0 | 0 | 0 | 0 |
| Р, | 0 | 5000 | 0 | 0 | 0 | 6 | 8 | 20 | 0 | 1 | 0 | 0 | 0 |
| Л | м | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Л 0 | м | 300 | ш | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| Л. | м | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Zj-Cj | | 1250М | М-4 | М-10 | М-10 | М-6 | М-8 | М-20 | 0 | 0 | 0 | 0 | 0 |
| Pi | 0 | 3000 | 0 | 10 | 10 | -4 | 0 | 0 | 0 | 0 | -4 | 0 | 0 |
| р* | 0 | 5000 | 0 | 0 | 0 | 6 | 8 | 20 | 1 | 1 | 0 | 0 | 0 |
| Ро | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Ло | м | 300 | 0 | 1 | 0 | 0 | ш | 0 | 0 | 0 | 0 | 1 | 0 |
| Л. | м | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| zr-9 | | 750Л/+2000 | 0 | М-10 | М-10 | -2 | М-8 | О 2 | 0 | 0 | -М + 4 | 0 | 0 |
| Базис | С | Р0 | 4 | Pi | 10 | 6 | 8 | 20 | 0 | 0 | м | м | М |
| | | Pi | 10 | ^3 | л | Р5 | р6 | Pi | р« | р9 | Pi 0 | Рц |
|
| Pi | 0 | 3000 | 0 | 10 | 10 | -4 | 0 | 0 | 1 | 0 | -4 | 0 | 0 |
| Р* | 0 | 2600 | 0 | -8 | 0 | 6 | 0 | 20 | 0 | 1 | 0 | -8 | 0 |
| Pi | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Р5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| РП | М | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Zj-Cj | | 450Л/+4400 | 0 | -2 | М-10 | -2 | 0 | М-20 | 0 | 0 | -М+4 | -М+8 | 0 |
| Ръ | 10 | 300 | 0 | 1 | 1 | 4 10 | 0 | 0 | 1 10 | 0 | 4 10 | 0 | 0 |
| Р% | 0 | 2600 | 0 | -8 | 0 | 6 | 0 | 20 | 0 | 1 | 0 | -8 | 0 |
| Pi | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Р5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| Рц | М | 150 | 0 | -1 | 0 | j4_ 10 | 0 | 1 | _ J_ 10 | 0 | 4 10 | 0 | 1 |
| zrCj | | 150Л/+7400 | 0 | -M+S | 0 | - М-6 10 | 0 | М-20 | - ~М+1 10 | 0 | -±м 10 | - Af+8" | 0 |
| Базис | с | Л, | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | М | М | м |
||
| Л | Рг | Л | л | PS | р6 | Pi | рamp; | Р9 | Ло | л. |
|||||
| Л | 10 | 300 | 0 | 1 | 1 | 4 | 0 | 0 | 1 | | 0 | | 4 | 0 | 0 |
| | | | | | | “10 | | | То | | | | “ 10 | | |
| р6 | 20 | 130 | 0 | 4 | 0 | 3 | 0 | 1 | 0 | | 1 | | 0 | 4 | 0 |
| | | | | ~Ї0 | | 10 | | | | | 20 | | | 10 | |
| л | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | 0 | | 1 | 0 | 0 |
| Ps | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | 0 | | 0 | 1 | 0 |
| Р\\ | М | 20 | 0 | 6 | 0 | 1 | 0 | 0 | 1 | | 1 | | 4 | 4 | 1 |
| | | | | 10 | | ~10 | | | То | | 20 | То | 10 | |
|
| Zj-Cj | | 20М+10000 | 0 | | 0 | -м | 0 | 0 | м+\ | | -м+\ | --М | -*М | 0 |
|
| | | | | 10 | | 10 | | | 10 | 20 | | 10 | 10 | |
|
| л | 10 | 380 | 0 | 14 | 1 | 0 | 0 | 0 | 3 | | 2 | | 12 | 0 | 0 |
| | | | | 10 | | | | | 10 | | 10 | 10 | | |
|
| р% | 20 | 70 | 0 | 14 | 0 | 0 | 0 | 1 | 3 | | 2 | | 12 | 16 | -3 |
| | | | | 10 | | | | | 10 | | 10 | | 10 | 10 | |
| Л | 4 | 300 | 1 | 6 | 0 | 0 | 0 | 0 | 1 | | 1 | | -3 | | -10 |
| | | | | | | | | | | | 2 | | | | |
| р5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | 0 | | 0 | 1 | 0 |
| Р4 | 6 | 200 | 0 | -6 | 0 | 1 | 0 | 0 | -1 | | 1 | | 4 | 4 | 10 |
| | | | | | | | | | | | ’ 2 | | | | |
| Z.-Ci | | 10000 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | -М | -М | -м |
||
| Базис | | Лgt; | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | м | м | л/ |
| о | Л | Рг | ръ | Р* | Р5 | Р6 | Л | Рamp; | р9 | Л 0 | л. |
||
| Рг | 10 | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | | |
| Р% | 0 | 350 | 0 | 7 | 0 | 0 | 0 | 5 | 3 5 | 1 | | | |
| Л | 4 | 125 | 1 | 5 2 | 0 | 0 | 0 | 5 2 | 1 4 | 0 | | | |
| Ps | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | | |
| Р4 | 6 | 375 | 0 | 5 2 | 0 | 1 | 0 | 5 2 | 1 4 | 0 | | | |
| Zj-Cj | | 9650 | 0 | -7 | 0 | 0 | 0 | -5 | 1 2 | 0 | | | |
Линейное программирование представляет собой один из наиболее значимых разделов математики, где осуществляется изучение теоретических и методических основ решения определенных задач. Данная математическая дисциплина широко используется в последние годы в разнообразных экономических и технических областях, где не последняя роль отведена математическому планированию и использованию автоматических систем вычисления. Этот раздел науки посвящен изучению линейных оптимизационных моделей. То есть линейное программирование посвящено числам. Впервые данный термин был предложен Т. Купмансом в 1951 году. Оптимальный план каждой линейной программы необходимо автоматически связывать с оптимальным уровнем цен, то есть с объективно обусловленными оценками.
Линейное программирование: методы
При помощи методики удается решить немалое количество экстремальных задач, что связаны с экономикой. В данном случае обычно требуется найти крайние значения некоторых функций переменной величины. В качестве основы линейного программирования выражено решение системы преобразуемых в уравнения и неравенства. Данный вид программирования характеризуется математической формулировкой переменных величин, последовательностью и определенным порядком расчетов, а также логическим анализом. Это применимо:
Если имеется математическая определенность и количественная ограниченность между изучаемыми факторами и переменными величинами;
Если имеется взаимозаменяемость факторов благодаря последовательности расчетов;
В случае если математическая логика совмещена с пониманием сущности явлений, которые изучаются.
Линейное программирование в способствует исчислению оптимальной производительности всех машин, поточных линий, агрегатов, а также решению задач рационального применения имеющихся материалов.
В сельском хозяйстве при помощи данного метода определяется минимальная стоимость рациона кормежки с учетом имеющегося количества корма. При этом учитываются виды и содержание в них определенных полезных веществ.
В литейном производстве данная методика позволяет найти решение транспортной задачи и задачи о смесях, которые входят в состав металлургической шихты. Суть транспортной задачи в данном случае подразумевает оптимальное прикрепление потребляющих предприятий к предприятиям, которые заняты производством продукции.
Линейное программирование: задачи
Отличительной чертой всех экономических задач, которые решаются посредством методики линейного программирования, является выбор определенных вариантов решения, а также ограничивающих условий. Благодаря решению такой задачи удается найти оптимальное решение из всех альтернативных вариантов.
Значительной ценностью использования методики линейного программирования в экономике служит выбор самого оптимального варианта из большого количества всех вариантов, которые считаются допустимо возможными. Подобные задачи почти нереально решить иными способами, так как только они позволяют найти степень рациональности применения При помощи линейного программирования разрешается такая основная задача, как транспортная, которая должна минимизировать грузооборот продукции широкого потребления в процессе их доставки от производителя.
Линейное программирование в Excel
В процессе решения таких задач для начала необходимо составить модель, что подразумевает формулировку условий на математическом языке. После этого этапа можно найти решение посредством графического метода. Для этого в программе Excel существует специальная функция «Поиск решения».
Как уже понятно из вышесказанного, линейное программирование имеет весьма обширную сферу применения.
Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .Решение происходит в три этапа:
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
| F(x) → min
|
F(x) → max
 |
Ведущий (разрешающий) элемент
– коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка
– строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец
– столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными
или зависимыми
. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными
или независимыми переменными
.
Базисное решение
называется допустимым базисным решением
, если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой
допустимого множества S задачи линейного программирования и называется иногда опорным планом
.
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным
(вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной
.
Пример №1
. Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП
.
Расширенная матрица системы ограничений-равенств данной задачи:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
| 4-(0 3):-2 | 3-(-2 3):-2 | -1-(5 3):-2 | 1-(0 3):-2 | 0-(-1 3):-2 | 10-(3 3):-2 |
| 0: -2 | -2: -2 | 5: -2 | 0: -2 | -1: -2 | 3: -2 |
| 1-(0 0):-2 | 0-(-2 0):-2 | 2-(5 0):-2 | 0-(0 0):-2 | 0-(-1 0):-2 | 9-(3 0):-2 |
| 4 | 0 | 6 1 / 2 | 1 | -1 1 / 2 | 14 1 / 2 |
| 0 | 1 | -2 1 / 2 | 0 | 1 / 2 | -1 1 / 2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
| 4-(1 6 1 / 2):2 | 0-(0 6 1 / 2):2 | 6 1 / 2 -(2 6 1 / 2):2 | 1-(0 6 1 / 2):2 | -1 1 / 2 -(0 6 1 / 2):2 | 14 1 / 2 -(9 6 1 / 2):2 |
| 0-(1 -2 1 / 2):2 | 1-(0 -2 1 / 2):2 | -2 1 / 2 -(2 -2 1 / 2):2 | 0-(0 -2 1 / 2):2 | 1 / 2 -(0 -2 1 / 2):2 | -1 1 / 2 -(9 -2 1 / 2):2 |
| 1: 2 | 0: 2 | 2: 2 | 0: 2 | 0: 2 | 9: 2 |
| 3 / 4 | 0 | 0 | 1 | -1 1 / 2 | -14 3 / 4 |
| 1 1 / 4 | 1 | 0 | 0 | 1 / 2 | 9 3 / 4 |
| 1 / 2 | 0 | 1 | 0 | 0 | 4 1 / 2 |
Пример №2
. Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0
Если в задаче линейного программирования имеется только две переменные, то ее можно решить графическим методом.
Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1)
;
(1.2)
Здесь ,
есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки ,
так и знаки .
Графический метод решения задачи (1) следующий.
Вначале мы проводим оси координат и и выбираем масштаб. Каждое из неравенств системы ограничений (1.2) определяет полуплоскость, ограниченную соответствующей прямой.
Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой .
С одной стороны от этой прямой ,
а с другой стороны .
На самой прямой .
Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).
Тоже самое выполняем для остальных неравенств системы (1.2). Так мы получим заштрихованных полуплоскостей. Точки области допустимых решений удовлетворяют всем неравенствам (1.2). Поэтому, графически, область допустимых решений (ОДР) является пересечением всех построенных полуплоскостей. Заштриховываем ОДР. Она представляет собой выпуклый многоугольник, грани которого принадлежат построенным прямым. Также ОДР может быть неограниченной выпуклой фигурой, отрезком, лучом или прямой.
Может возникнуть и такой случай, что полуплоскости не содержат общих точек. Тогда областью допустимых решений является пустое множество. Такая задача решений не имеет.
Можно упростить метод. Можно не заштриховывать каждую полуплоскость, а вначале построить все прямые
(2)
Далее выбрать произвольную точку, не принадлежащую ни одной из этих прямых. Подставить координаты этой точки в систему неравенств (1.2). Если все неравенства выполняются, то область допустимых решений ограничена построенными прямыми и включает в себя выбранную точку. Заштриховываем область допустимых решений по границам прямых так, чтобы оно включало в себя выбранную точку.
Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).
Итак, мы имеем заштрихованную область допустимых решений (ОДР). Она ограничена ломаной, состоящей из отрезков и лучей, принадлежащих построенным прямым (2). ОДР всегда является выпуклым множеством. Оно может быть как ограниченным множеством, так и не ограниченным вдоль некоторых направлений.
Теперь мы можем искать экстремум целевой функции
(1.1)
.
Для этого выбираем любое число и строим прямую
(3)
.
Для удобства дальнейшего изложения считаем, что эта прямая проходит через ОДР. На этой прямой целевая функция постоянна и равна .
такая прямая называется линией уровня функции .
Эта прямая разбивает плоскость на две полуплоскости. На одной полуплоскости
.
На другой полуплоскости
.
То есть с одной стороны от прямой (3) целевая функция возрастает. И чем дальше мы отодвинем точку от прямой (3), тем больше будет значение .
С другой стороны от прямой (3) целевая функция убывает. И чем дальше мы отодвинем точку от прямой (3) в другую сторону, тем меньше будет значение .
Если мы проведем прямую, параллельную прямой (3), то новая прямая также будет линией уровня целевой функции, но с другим значением .
Таким образом, чтобы найти максимальное значение целевой функции, надо провести прямую, параллельную прямой (3), максимально удаленную от нее в сторону возрастания значений , и проходящую хотя бы через одну точку ОДР. Чтобы найти минимальное значение целевой функции, надо провести прямую, параллельную прямой (3) и максимально удаленную от нее в сторону убывания значений , и проходящую хотя бы через одну точку ОДР.
Если ОДР неограниченна, то может возникнуть случай, когда такую прямую провести нельзя. То есть как бы мы ни удаляли прямую от линии уровня (3) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.
Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через одну вершину многоугольника ОДР. Из графика определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
.
Решением задачи является
.
Также может встретиться случай, когда прямая параллельна одной из граней ОДР. Тогда прямая проходит через две вершины многоугольника ОДР. Определяем координаты и этих вершин. Для определения максимального (минимального) значения целевой функции, можно использовать координаты любой из этих вершин:
.
Задача имеет бесконечно много решений. Решением является любая точка, расположенная на отрезке между точками и ,
включая сами точки и .
Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида - 10 м, третьего вида - 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В - 300 ден. ед.
Составить план производства, обеспечивающий фирме наибольший доход. Задачу решить графическим методом.
Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
и .
Доход от произведенных платьев составит:
(ден. ед.)
Тогда экономико-математическая модель задачи имеет вид:
Решаем графическим методом.
Проводим оси координат и .
Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).
Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).
Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).
Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.
(П1.1)
.
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).
Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и .
Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания ,
и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Решение задачи: ;
.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.
Решить задачу линейного программирования графическим методом.
Решаем графическим методом.
Проводим оси координат и .
Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).
Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).
Строим прямую .
Строим прямую (ось абсцисс).
Область допустимых решений (ОДР) ограничена построенными прямыми. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:
Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.
Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и ,
то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания ,
и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Решение задачи: ;
Решить графически задачу линейного программирования. Найти максимальное и минимальное значение целевой функции.
Решаем задачу графическим методом.
Проводим оси координат и .
Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).
Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).
Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).
Прямые и являются осями координат.
Область допустимых решений (ОДР) ограничена построенными прямыми и осями координат. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:
Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.
Строим произвольную линию уровня целевой функции, например,
(П3.1)
.
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .
Чтобы найти максимум, нужно провести параллельную прямую, максимально удаленную в сторону возрастания , и проходящую хотя бы через одну точку области ABCDE. Однако, поскольку область неограниченна со стороны больших значений и , то такую прямую провести нельзя. Какую бы прямую мы не провели, всегда найдутся точки области, более удаленные в сторону увеличения и . Поэтому максимума не существует. можно сделать сколь угодно большой.
Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания ,
и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:
Максимального значения не существует.
Минимальное значение
.
