Графический метод решения злп пример. Графические методы
На этом уроке будем знакомиться с графическим методом решения задач линейного программирования , то есть, таких задач, в которых требуется найти такое решения системы линейных уравнений и (или) неравенств (системы ограничений), при котором функция цели - линейная функция - принимает оптимальное значение.
Ввиду того, что наглядность графического решения достигается лишь на плоскости, мы можем познакомиться с графическим представлением задачи только в двумерном пространстве. Это представление пригодно для системы ограничений-неравенств с двумя переменными или для систем уравнений, в которых число переменных на 2 превышает число уравнений, то есть число свободных переменных равно двум.
Поэтому графический метод имеет такие узкие рамки применения, что о нём как об особом методе решения задач линейного программирования говорить нельзя.
Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования .
Теоретические основы графического метода
Итак, задача линейного программирования. Требуется найти неотрицательные значения переменных и , удовлетворяющих системе неравенств
при которых линейная форма принимает оптимальное значение.
Пример 3.
Пример 4. Решить графическим методом задачу линейного программирования, в которой требуется найти минимум функции при ограничениях
Продолжаем решать задачи графическим методом вместе
До сих пор полученные выводы были основаны на том, что множество решений задачи линейного программирования сконфигурировано так, что оптимальное решение конечно и единственно. Теперь рассмотрим примеры, когда это условие нарушается. В этих примерах многоугольник решений строится так, как показано в предыдущих примерах, остановимся же на признаках, которые отличают эти исключительные примеры.
Пример 5. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
Решение. На рисунке изображены: неограниченная многогранная область решений данной системы ограничений, исходная линия уровня (чёрного цвета), вектор (бордового цвета), указывающий направление движения исходной линии уровня для нахождения максимума целевой функции.
Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что .
Пример 6. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
Графические методы связаны прежде всего с геометрическим изображением функциональной зависимости при помощи линий на плоскости. Графики используются для быстрого нахождения значения функций по соответствующему значению аргумента, для наглядного изображения функциональных зависимостей.
В экономическом анализе применяются почти все виды графиков: диаграммы сравнения, диаграммы временных рядов, кривые распределения, графики корреляционного поля, статистические картограммы. Особенно широко распространены в анализе диаграммы сравнения - для сравнения отчетных показателей с плановыми, предшествующих периодов и передовых предприятий отечественных или зарубежных. Для наглядного изображения динамики экономических явлений (а в анализе с динамическими рядами приходится иметь дело очень часто) используются диаграммы временных рядов.
С помощью координатной сетки строятся графики зависимости, например, уровня издержек от объема произведенной и реализованной продукции, а также. графики, на которых можно изображать и корреляционные связи между показателями. В системе осей координат изображение показывает влияние различных факторов на тот или иной показатель.
Широко применяется графический метод для исследования производственных процессов, организационных структур, процессов программирования и т. д. Например, для анализа эффективности использования производственного оборудования строятся расчетные графики, в том числе графики множественных факторов.
Обозначения: каждый круг считается одной из вершин графика; цифра в верхнем секторе каждой вершины означает ее порядковый номер; нз номеров двух соседних вершин складывается шифр работы; цифра в нижнем секторе каждой вершины является порядковым номером предшествующей вершины, а линия, соединяющая эти две вершины, означает определенную работу. Внизу под линией записана плановая продолжительность данной работы; цифра в левом секторе каждой вершины означает общую продолжительность всех предшествующих работ, цифра в правом секторе отличается от цифры в левом на величину резерва (запаса времени). Такнм образом, для вершин, лежащих на критическом пути, цифры в левом и правом секторах вершины совпадают, поскольку запас времени равен 0.
В математически формализованной системе анализа, планирования и управления особое место занимают сетевые графики. Они дают большой экономический эффект при строительстве и монтаже промышленных и других предприятий.
Сетевой график (рис. 6.1) позволяет выделить из всего комплекса работ наиболее важные, лежащие на критическом пути, и сосредоточить на них основные ресурсы строительномонтажных организаций, устанавливать взаимосвязь между различными специализированными организациями и координировать их работу. Работы, лежащие на критическом пути, требуют наиболее продолжительного ожидания поступления очередного события. На стадии оперативного анализа и управления сетевой график дает возможность осуществлять действенный контроль за ходом строительства, своевременно принимать меры по устранению возможных задержек в работе.
Применение сетевых графиков анализа, планирования и управления обеспечивает, как показывают многие примеры, сокращение сроков строительства на 20-30%, повышение производительности труда на 15-20%.
При анализе, осуществляемом непосредственно на стройках, использование материалов сетевого планирования и управления способствует правильному определению причин, влияющих на ход строительства, и выявлению предприятий, не обеспечивающих выполнение порученных им работ или поставку оборудования в сроки, установленные графиком.
Разработка сетевого графика в строительстве осуществляется при наличии: норм продолжительности строительства и срока ввода в действие объекта или комплекса объектов, проектно-сметной документации, проекта организации строительства и производства работ, типовых технологических карт, действующих норм затрат труда, материалов и работы машин. Кроме того, при составлении графика используются опыт выполнения отдельных работ, а также данные о производственной базе строительных и монтажных организаций.
На основе всех этих данных составляется таблица работ и ресурсов, где в технологической последовательности производства работ указываются их характеристика, объем, трудоемкость в человеко-днях, исполнитель (организация и бригада), численность рабочих, сменность, потребность в механизмах и материалах, источники их поступления, общая продолжительность выполнения работы в днях, а также предшествующее задание, после окончания которого можно начинать данную работу. Исходя из показателей такой таблицы, подготавливают сетевой график, который может иметь различную степень детализации в зависимости от принятой схемы произ
водства работ и уровня руководства; кроме общего графика исполнители разрабатывают график выполняемых ими работ.
Основные элементы сетевого графика: событие, работа, ожидание, зависимость.
При анализе хода строительства объекта следует устанавливать, правильно ли составлен сетевой график, не допущено ли при этом завышение критического пути, учтены ли при оптимизации графика все возможности его сокращения, нельзя ли какие-либо работы выполнять параллельно или сократить время, затрачиваемое на них, путем увеличения средств механизации и др. Это особенно важно в тех случаях, когда продолжительность работ по графику не обеспечивает окончание строительства в срок.
Основным материалом сетевого планирования, используемого при анализе, является информация о ходе работ по графику, который обычно составляется не реже одного раза в декаду. В качестве примера приводится карта задания и информации о ходе работы по объекту строительства, осуществляемому по сетевому графику (табл. 6.1). По данным карты, критические работы выполнялись в начале месяца с опережением графика, однако затем было допущено отставание монтажа подкрановых балок по ряду Б, а последующая работа - монтаж подкрановых балок по ряду А - закончена с отставанием на один день.
Оптимизация сетевых графиков осуществляется на стадии планирования посредством сокращения критического пути, т. е. минимизации сроков выполнения строительных работ при заданных уровнях ресурсов, минимизации уровня потребления материальных, трудовых и финансовых ресурсов при фиксированных сроках выполнения строительных работ. Возможен и смешанный подход: для одной части работ (более дорогостоящих) - минимизировать уровень потребления ресурсов при фиксированных сроках выполнения работ, для другой - минимизировать сроки при фиксированном уровне ресурсов.
Решение оптимизационных задач существенно облегчается наличием пакетов прикладных программ (ППП), приспособленных к составлению оптимальных сетевых графиков на ЭВМ.
В зарубежной практике системного анализа распространен графо-математический метод, получивший название «дерево решений». Суть этого метода заключается в следующем.
Путем предварительной оценки потребностей, предварительного анализа возможных организационных, технических или технологических условий намечаются все предполагаемые варианты решения данной задачи. Вначале разрабатываются
| | Задание | | Информация | Резерв времени по работам | Чис тый |
|||||||
| Наименование работ | шифр | дата начала | дата оконча | плановая продол | Ре зерв вре | % тех- | требуемое время для | при чина | фактическая дата | находя щимся | не находящимся | резерв времени с |
| | работ | работ (план) | ния работ (план) | житель ность, дней | мени | кой готов ности | оконча ния работ, дней | задер жки | оконча ния работ | на критическом пути | аа критическом пути | начала месяца, дней |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| Разработка грунта | 1-2 | 1/IV | 6/IV | 5 | 0 | 100 | - | - | 6/IV | ¦- | - | - |
| Бетонирование фундаментов под котлы | 2-3 | 7/IV | 17/1V | 9 | 0 | 100 | 14/IV | 2 | 2 |
|||
| Бетонирование фундаментов по ряду А | 2-4 | 7/IV | 14/1V | 7 | 2 | 100 | 14/IV | | | |
||
| То же по ряду Б | 2-5 | 7/IV | 14/IV | 7 | 2 | 100 | - | - | 14/IV | | | |
| Устройство трубной разводки | 6-18 | 18/IV | 21/IV | 4 | 19 | 100 | - | - | 29/IV | -7 |
||
| Устройство обратной засыпки | 6-7 | 18/IV | 19/IV | 2 | 0 | 100 | 17/IV | 2 | 2 |
|||
| Монтаж сборных железобетонных ко | | | | | | | | | | | | |
| лонн: по ряду Б | 7-8 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | _ | - | - |
| по ряду А | 7-9 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | - | - | - |
Устройство подкрановых путей и монтаж башенного крана 7-10
Установка опорных рам на фундамент под оборудование 7-16 Монтаж подкрановых балок:
по ряду Б 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2
по ряду А 10-12 25/IV 26/IV
Монтаж первой части балок и плит покрытия 12-13 27/IV 4/V
Монтаж подкрановых путей мостового lt;3 крана 12-14 27/IV 3/V
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 0 | 100 | - | - | 22/IV | 1 | - | 1 |
| 14 | 100. | - | - | 29/IV | - | -5 | - |
| 1 | 100 | за- | 27/IV | -2 |
27/IV -1
держ- ка с поставкой ж/б конструкций
- 100 -
укрупненные варианты. Затем по мере введения дополнительных условий каждый из них расчленяется на ряд вариантов. Графическое изображение этих вариантов позволяет исключить менее выгодные из них и избрать наиболее приемлемый.
Этот метод может найти у нас применение при определении порядка обработки тех или иных деталей на нескольких станках в целях минимизации общего времени обработки; при установлении размеров ресурсов для минимизации общих производственных издержек; при распределении капиталовложений и других ресурсов по промышленным объектам; при решении транспортных и других задач.
В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).
Назначение сервиса . С помощью данного сервиса можно в онлайн режиме решить задачу линейного программирования геометрическим методом, а также получить решение двойственной задачи (оценить оптимальность использования ресурсов). Дополнительно создается шаблон решения в Excel .
Инструкция . Выберите количество строк (количество ограничений).
Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x 1 ≤ 4 , то оно разбивается на два: x 1 ≥ 1 , x 1 ≤ 4 (т.е. количество строк увеличивается на 1).Построить область допустимого решения (ОДР) можно также с помощью этого сервиса .
Вместе с этим калькулятором также используют следующие:
Симплексный метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Вычисление пределов
Решение задачи линейного программирования графическим методом включает следующие этапы :
- На плоскости X 1 0X 2 строят прямые.
- Определяются полуплоскости.
- Определяют многоугольник решений;
- Строят вектор N(c 1 ,c 2), который указывает направление целевой функции;
- Передвигают прямую целевую функцию c 1 x 2 + c 2 x 2 = 0 в направлении вектора N до крайней точки многоугольника решений.
- Вычисляют координаты точки и значение целевой функции в этой точке.
Пример
. Компания изготавливает два вида продукции - П1 и П2. Для производства продукции используются два вида сырья - С1 и С2. Оптовые цены единицы продукции равна: 5 д.е. для П1 и 4 д.е. для П2. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице.
Таблица - Расход сырья на производство продукции
Требуется определить:
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?
- Сформулировать математическую модель задачи линейного программирования.
- Решить задачу линейного программирования графическим способом (для двух переменных).
Сформулируем математическую модель задачи линейного программирования.
x 1 - производство продукции П1, ед.
x 2 - производство продукции П2, ед.
x 1 , x 2 ≥ 0
Ограничения по ресурсам
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
Ограничения по спросу
x 1 +1 ≥ x 2
x 2 ≤ 2
Целевая функция
5x 1 + 4x 2 → max
Тогда получаем следующую ЗЛП:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1 , x 2 ≥ 0
5x 1 + 4x 2 → max
Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое из неравенств задачи ЛП определяет на координатной плоскости (х 1 ,х 2 ) некоторую полуплоскость (рис. 1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена, выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.
Примечание № 1. Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство
a il x 1 +a i 2 x 2 =b
можно представить в виде системы двух неравенств (рис. 1)
A i 2 x 2 <Ь 1э +a i 2 x 2 >bj.
ЦФ L(x)= с1х1 + с2х2 при фиксированном значении L(х)=L определяет на плоскости прямую линию с1х1 + с2х2 = L. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси х2 (начальная ордината), а угловой коэффициент прямой tgа = -- останется постоянным (рис. 1).
Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор C = (c1;c2) с координатами из коэффициентов ЦФ при х1 и х2 перпендикулярен к каждой из линий уровня (см. рис. 1). Направление вектора С совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора С.
Суть графического метода заключается в следующем. По направлению (против направления) вектора С в ОДР производится поиск оптимальной точки X = (х1; х2). Оптимальной считается точка, через которую проходит линия уровня L max (L min), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.
Допустимая область - полуплоскость
Рисунок 1
1.2. Методика решения задач лп графическим методом
I. Вограничениях задачи замените знаки неравенств на знаки точных равенств и постройте соответствующие прямые.
II. Найдите и заштрихуйте полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого подставьте в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверьте истинность полученного неравенства.
Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку х1 и х2 должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси х 1 и правее оси х2, т.е. в 1-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой, поэтому выделите на графике такие прямые.
Определите ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделите ее. При отсутствии ОДР задача не имеет решений, о чем сделайте соответствующий вывод.
Если ОДР - не пустое множество, то постройте целевую прямую, т.е. любую из линий уровня с 1 х 1 + с 2 х 2 = L, где L - произвольное число, например, кратное с 1 и с 2 , т.е. удобное для проведения расчетов. Способ построения аналогичен построению прямых ограничений.
V. Постройте вектор C = (c 1 ,с 2), который начинается в точке (0;0), заканчивается в точке (c 1 ,с 2). Если целевая прямая и вектор С построены верно, то они будут перпендикулярны.
VI. При поиске max ЦФ передвигайте целевую прямую в направлении вектора С, при поиске min ЦФ - против направления вектора С. Последняя по ходу движения вершина ОДР будет точкой max или min ЦФ. Если такой точки (точек) не существует, то сделайте вывод о неограниченности ЦФ на множестве планов сверху (при поиске шах) или снизу (при поиске min).
Определите координаты точки max (min) ЦФ X = (х1 * ; х2 * ) и вычислите значение ЦФ l(x *). Для вычисления координат оптимальной точки X * решите систему уравнений прямых, на пересечении которых находится X * .
Задача 1
Найдем оптимальное решение задачи, математическая модель которой имеет вид
L(Х) = 3x 1 + 2x 2 → max
х 1 + 2х 2 < 6, (1)
2х 1 + х 2 < 8, (2)
Х 1 +х 2 <1, (3)
х 2 < 2, (4)
х 1 >0,х 2 >0.
Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис. 2).
х 1 + 2х 2 = 6,(1)
2х1 + х2= 8,(2)
(1) х1=0, х1=6, х2=3, х2=0,
(2) х1=0, х1=4, х2=8, х2=0,
(3) х1=0, х1=-1, х2=1, х2=0,
Прямая (4) проходит через точку х 2 = 2 параллельно оси L(Х).
Рис. 2. Графическое решение задачи
Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим 0 < 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (рис. 2). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF.
Целевую прямую можно построить по уравнению
Строим вектор С из точки (0;0) в точку (3;2). Точка Е- это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора С. Поэтому Е -это точка максимума ЦФ. Определим координаты точки Е из системы уравнений прямых ограничений (1) и (2)
Х1 +2х 2 =6, (1) х1=10/3=3 1/3, х2=4/3=1 1/3
2 Х1 +х 2 =8, (2) Е 3 1/3; 1 1/3
Максимальное значение ЦФ равно L(E) = 3*10/3+2*4/3 = 12 2 / 3
Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .Решение происходит в три этапа:
- Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
- Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
- Решение симплексным методом;
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .Проиллюстрируем этот факт графически:
| 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 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 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 |
3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 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 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или
Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max
Пример №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