Решение задач графическим методом. Симплекс-метод решения ЗЛП

Задание. Решить графическим способом последующие задачки:

Задачка 1. Задачка 2. Задачка 3.
Задачка 4. Задачка 5
Симплекс-метод решения ЗЛП Цель занятия: овладение студентами симплекс-методом решения ЗЛП. Задачки занятия: - исследование правил построения симплекс-таблицы; - получение навыка решения ЗЛП при помощи симплекс-таблиц. Методические указания Симплекс способ – основной, универсальный способ, которым можно решить всякую задачку Решение задач графическим методом. Симплекс-метод решения ЗЛП ЛП. Симплекс способ представляет собой схему перехода от 1-го базового решения к другому, третьему и т.д., пока не будет найдено

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

Симплекс способ представляет собой схему перехода от 1-го базового решения к другому, третьему и т.д., пока не будет Решение задач графическим методом. Симплекс-метод решения ЗЛП найдено наилучшее решение или не будет установлено, что система ограничений противоречива.

Применение симплексного способа разбивается на два шага.

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

Разглядим на примере определение базового решения

Пример 1.

Любые “m” переменных из m уравнений с n переменными (m < n) именуются основными, если определитель из коэффициентов при их отличен от нуля

Х1,Х2 – главные переменные, а Х3, Х4, Х5 – неосновные. Базовыми именуются решения системы из m уравнений с n неведомыми (m Решение задач графическим методом. Симплекс-метод решения ЗЛП < n), в каких неосновные переменные имеют нулевые значения. Выразим главные переменные через неосновные. Оставим слева только главные переменные, а все другие перенесем на право

домножим 1-ое и 2-ое уравнения на дополнительные множители

и способом алгебраического сложения получим:

1-ое базовое решение (3;1;0;0;0)

Проверим Х1 и Х3 в качестве главных

Проверим Х1 и Решение задач графическим методом. Симплекс-метод решения ЗЛП Х4 в качестве главных

Х1,Х4 – главные переменные, а Х2, Х3, Х5 – неосновные.

2-ое базовое решение (3;0;0; ;0)

Аналогично найдем еще четыре базовых решения:

(0;1; 0;0;0); (0;1;0;0;1); (0;0; ; ;0); (0;0;0; ;1)

Выделим посреди базовых решений те, где составляющие неотрицательны – оно именуется допустимым (опорным). Если хотя бы одна компонента отрицательна, то решение именуется недопустимым.

Отыскать без помощи других базовые Решение задач графическим методом. Симплекс-метод решения ЗЛП решения системы и указать допустимые либо доделать дома.

Пример 2. Даны системы ограничений 3-х задач ЛП:

Отыскать допустимое базовое решение.

Решение. (а) Введем дополнительные переменные Х4 и Х5 (со знаком плюс, потому что все неравенства вида ( ) и представим данную систему неравенств в виде эквивалентной системы уравнений

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

Х4 и Х5.

1 шаг.Главные переменные - Х4 ,Х5 ; неосновные переменные Х1 ;Х2 и Х3 . Выражая главные переменные через неосновные, получим

Приравнивая к нулю неосновные переменные Х1;Х2 и Х3 найдем базовое решение (0;0;0;12;4), которое является допустимым.

(б) Введем дополнительные переменные Решение задач графическим методом. Симплекс-метод решения ЗЛП Х4 и Х5 ( со знаком минус, т.к. все неравенства вида ( ) . Получим

Тут в качестве главных переменных брать дополнительные переменные Х4 и Х5 нерентабельно: они входят в левые части уравнений с отрицательными компонентами.

Целенаправлено в качестве главных взять переменную Х3 и дополнительную переменную Х5. Переменная Х3 также Решение задач графическим методом. Симплекс-метод решения ЗЛП заходит исключительно в одно уравнение системы, но, в отличие от Х4 с положительным коэффициентом. Это приведет также к недопустимому базовому решению, но только с одной отрицательной компонентой.

1 шаг.Главные переменные – Х3 ,Х5 ; неосновные переменные Х1 ;Х2 и Х4 . Выражая главные переменные через неосновные, получим

базовое решение (0;0;4;0;-4) – недопустимое.

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

Если переводить в главные переменную Х1 , то ее наибольшее значение определяется из условия

В данном случае выделяется 2-ое уравнение и в неосновные переводится переменная Х5.

Если переводить Решение задач графическим методом. Симплекс-метод решения ЗЛП в главные переменную Х2, то ее наибольшее значение определяется из условия

Т.е. выделяется 1-ое уравнение и в неосновные переводится переменная Х3.

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

Итак, переводим в главные переменную Х1. При Х1=2, как видно из уравнения , переменная Х5 = 0 перебегает в число неосновных.

2 шаг. Главные переменные – Х1 ,Х3 ; неосновные переменные Х2 ;Х4 и Х5 .

Выражаем новые Решение задач графическим методом. Симплекс-метод решения ЗЛП главные переменные через новые неосновные, начиная с последнего:

либо

2-ое базовое решение (2;0;3;0;0) – допустимое.

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

(в) Вводя дополнительные переменные Решение задач графическим методом. Симплекс-метод решения ЗЛП, приведем систему ограничений к виду

1 шаг.Главные переменные – Х4 ,Х5; неосновные переменные Х1 ;Х2 и Х3 . Выражая главные переменные через неосновные, получим

1-ое базовое решение (0;0;0;-9;-8) – недопустимое.

Переводим в главные, к примеру, переменную Х1 (она заходит с положительным коэффициентом в выражение для главных переменных Х4 ,Х5 содержащие отрицательные свободные члены). Найдем

т Решение задач графическим методом. Симплекс-метод решения ЗЛП.е. выделяем 1-ое уравнение

При Х1 = 3 переменная Х4 = 0 и перебегает в число неосновных.

2 шаг. Главные переменные – Х1 ,Х5 ; неосновные переменные Х2 ;Х3 и Х4 .После преобразования получим

2-ое базовое решение (3;0;0;0;-5) – недопустимое, но лучше первого, потому что содержит на одну отрицательную компоненту меньше. По суждениям, приведенным в предшествующей задачке, в главные Решение задач графическим методом. Симплекс-метод решения ЗЛП можно перевести или переменную Х3, или Х4. Переводим в главные переменные Х4, так как это позволяет упростить преобразования:

( для первого уравнения отношение равным , т.к.

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

Х4 = 15 переменная Х5 = 0 перебегает Решение задач графическим методом. Симплекс-метод решения ЗЛП в число неосновных.

3 шаг. Главные переменные – Х3 ,Х4; неосновные переменные Х1 ;Х2 и Х5 . Третье базовое решение (8;0;0;15;0) – допустимое.

Пример 3. Дана система ограничений одной из задач ЛП (в канонической форме):

Показать, что данная система несовместна.

Р е ш е н и е.1 шаг. Главные переменные – Х3 ,Х4; неосновные переменные Решение задач графическим методом. Симплекс-метод решения ЗЛП Х1 ;Х2.

1-ое базовое решение (0;0;-8;2) –недопустимое.

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

Выделяем 2-ое уравнение. При Х2 = 2 переменная Х4 = 0 и перебегает в число неосновных.

2 шаг. Главные переменные – Х2 ,Х3; неосновные переменные Х1 ;Х2 .

2-ое базовое решение (0;2;-4;0) вновь недопустимое, потому Решение задач графическим методом. Симплекс-метод решения ЗЛП что выделенным на 1 шаге оказалось уравнение с отрицательным свободным членом. Но получить наилучшее решение уже нельзя, так как во 2-м уравнении и свободный член, и коэффициенты при всех неосновных переменных отрицательны. Как следует, задачка не имеет ни 1-го допустимого базового решения, т.е. система ее ограничений несовместна.

В т Решение задач графическим методом. Симплекс-метод решения ЗЛП о р о й э т а п.Нахождение рационального решения.

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

Решим три задачки на нахождение минимума, в каких 1-ый шаг решения Решение задач графическим методом. Симплекс-метод решения ЗЛП уже завершен:

Окончить решение задачки.

Р е ш е н и е. (а) Базовое решение (0;0;2;0) – вырожденное (основная переменная Х4 = 0) и не наилучшее, потому что переменная Х1 заходит в выражение линейной функции с отрицательным коэффициентом. Чтоб минимизировать линейную функцию переведем переменную Х1 в главные. Тогда

1-ое отношение считаем условно равным Решение задач графическим методом. Симплекс-метод решения ЗЛП , потому что переменная Х1

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

Выделяем 2-ое уравнение. При Х1 = 0 переменная Х4 = 0 и перебегает в число неосновных. Делаем последующий шаг.

Главные переменные – Х1 ,Х3; неосновные переменные Решение задач графическим методом. Симплекс-метод решения ЗЛП - Х2 ;Х4

Получили новое базовое решение (0;0;2;0) – такое же, как и на прошлом шаге (только сейчас равна нулю основная переменная Х1). Соответственно не поменялось и значение линейной функции. И это естественно, потому что переменная Х1 как и раньше равна нулю, хотя сейчас и является основной. Но таковой формальный Решение задач графическим методом. Симплекс-метод решения ЗЛП шаг с переводом Х1 в главные является принужденным для предстоящего решения задачки.

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

Направьте внимание на то, что и в этом случае 1-ое отношение считается условно равным : хотя свободный член в первом уравнении и Решение задач графическим методом. Симплекс-метод решения ЗЛП равен нулю, но переменная Х2 заходит в это уравнение с положительным коэффициентом, т.е. 1-ое уравнение не ограничивает рост переменной Х2 . Выделяем 2-ое уравнение. При Х2 =2 переменная Х3 =0; переведем ее в число неосновных, а потом перебегаем к последующему шагу.

Главные переменные – Х1 ,Х2; неосновные переменные - Х3 ;Х Решение задач графическим методом. Симплекс-метод решения ЗЛП4 . После преобразований

Новое базовое решение (4;2;0;0) является хорошим, т.к. в выражении линейной функции нет главных переменных с отрицательными коэффициентами. Находим оптимум линейной функции: при рациональном базовом решении (4;2;0;0).

б) Базовое решение (0;0;2;6) – среднее, т.к. выполнен аспект оптимальности (для варианта минимизации линейной функции). Оптимум линейной функции В выражении для линейной функции отсутствует Решение задач графическим методом. Симплекс-метод решения ЗЛП неосновная переменная Х1, то среднее решение не единственное (т.е. существует нескончаемое огромное количество хороших решений, посреди которых конечное число базовых хороших решений). Получим эти решения.

Какой бы ни была переменная Х1 , удовлетворяющая данной системе ограничений, при Х2=0 наилучшее значение линейной функции одно и тоже: Переменная Х1 ,может принимать значения

Для Решение задач графическим методом. Симплекс-метод решения ЗЛП получения всех хороших решений выразим все переменные через Х1 , считая, что Х2=0, и полагая что Х1 =С.

Ответ. при хороших решениях

b) Базовое решение (0;0;4;3) - не среднее, т.к. не выполнен аспект оптимальности. Переведем в число главных переменную Х2, которая заходит в выражение для линейной функции с отрицательным коэффициентом. Найдем Решение задач графическим методом. Симплекс-метод решения ЗЛП

Приобретенные дела означают, что оба уравнения не ограничивают рост переменной Х2, т.е. линейная функция F, будучи отрицательной по знаку, неограниченно увеличивается по абсолютной величине. Итак, задачка не имеет конечного оптимума, т.е.

Разглядим метод решения задач симплексным способом.

1. Математическая модель задачки должна бать канонической. Если она неканоническая, то Решение задач графическим методом. Симплекс-метод решения ЗЛП ее нужно привести к каноническому виду.

2. Находим начальное опорное решение и проверяем его на оптимальность. Для этого заполняем симплекс-таблицу. Все строчки таблицы 1-го шага, кроме строчки Dj (индексная строчка), заполняем по данным системы ограничений и мотивированной функции. Симплексная таблица будет иметь последующий вид:

сi Сj С1 с2 &frac Решение задач графическим методом. Симплекс-метод решения ЗЛП14; сm сm+1 ¼ сn f(`X)
Базовая переменная (БП) x1 x2 ¼ xm xm+1 ¼ xn b1
c1 x1 ¼ h1, m+1 ¼ h1n l1
c2 x2 ¼ h2, m+1 ¼ h2n l2
¼ ¼ ¼ ¼ ¼ ¼ ¼ ¼ ¼ ¼
cm xm ¼ hm, m Решение задач графическим методом. Симплекс-метод решения ЗЛП+1 ¼ hmn lm
Dj ¼ Dm+1 ¼ Dn f(`X1)

Индексная строчка (Dj) для переменных находится по формуле

и для свободного члена по формуле

.

При всем этом вероятны последующие случаи решения задачки на максимум:

- если все оценки Dj ³ 0, то отысканное решение наилучшее;

- если хотя бы одна оценка Dj Решение задач графическим методом. Симплекс-метод решения ЗЛП £ 0, но при соответственной переменной нет ни 1-го положительного коэффициента, решение задачки прекращают, потому что f(X) ® ¥, т.е. мотивированная функция не ограничена в области допустимых решений;

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

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

Пусть одна оценка Dk £ 0 либо большая по абсолютной величине Dk £ 0, тогда k-й столбец принимают за разрешающий. За разрешающую строчку принимают ту, которой соответствует малое Решение задач графическим методом. Симплекс-метод решения ЗЛП отношение свободных членов (bi) к положительным коэффициентам k-го столбца. Элемент, находящийся на скрещении главных строчки и столбца, именуют главным (разрешающим) элементом.

3. Наполнение симплексной таблицы 2-го шага:

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

- заполняют базовые столбцы;

- другие коэффициенты таблицы находят по правилу «прямоугольника». Оценки можно считать по Решение задач графическим методом. Симплекс-метод решения ЗЛП приведенным выше формулам либо по правилу «прямоугольника». Выходит новое опорное решение, которое проверяется на оптимальность и т.д.

Примечание. Если мотивированная функция f(X) просит нахождения малого значения, то аспектом оптимальности задачки является неположительность оценок Dj при всех .

Правило «прямоугольника» состоит в последующем. Пусть главным элементом 1-го шага является Решение задач графическим методом. Симплекс-метод решения ЗЛП элемент 1-й строчки (m+1)-го столбца h1, m+1. Тогда элемент i-й строчки (m+2)-го столбца 2-го шага, который обозначим , по правилу «прямоугольника» определяется по формуле

,

где h1, m+1, hi, m+1, hi, m+2 – элементы 1-го шага.

Пример 4. Разберем решение примера 1 симплекс-методом

Запишем систему ограничений в канонической форме:

Найдем Решение задач графическим методом. Симплекс-метод решения ЗЛП 1-ое решение главные переменные, а неосновные. Пусть неосновные переменные равны нулю, тогда решение допустимое, т.к. все координаты положительны. Можно перебегать ко второму шагу – оптимизации. Построим такую таблицу:

сi сj Примечания
Базовые переменные (БП) х1 х2 х3 х4 bi
х3
х4
Dj -2 -4

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

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

Все элементы первой строчки разделим на разрешающий, получим:

сi сj Примечания
Базовые переменные (БП) х1 х2 х3 х4 bi
х3
х4
Dj -2 -4
х2 1/2 1/2
х4
Dj

х2 – переводим в Решение задач графическим методом. Симплекс-метод решения ЗЛП базис, означает в других уравнениях х2 = 0. Чтоб заполнить вторую строчку до конца воспользуемся правилом прямоугольника.

сi сj Примечания
Базовые переменные (БП) х1 х2 х3 х4 bi
х3
х4
D1 -2 -4
х2 1/2 1/2
х4 3/2 -1/2
D2

Во 2-ой индексной строке нет отрицательных значений, означает отысканное значение среднее, а .

Дома сделать последующие задания

4. Для Решение задач графическим методом. Симплекс-метод решения ЗЛП производства шифанеров и буфетов деревообрабатывающий комбинат применяет древесную породу 4-х видов. Припасы древесной породы по каждому виду ограничены и составляют соответственно 120, 160, 120, 80 единиц. Количество единиц древесной породы каждого вида, нужное для производства 1-го шкафа и 1-го буфета, также прибыль от реализации даны в табл.

Таблица 1

Вид древесной породы Решение задач графическим методом. Симплекс-метод решения ЗЛП Припас древесной породы Количество единиц древесной породы, нужное для производства ед. продукции
Шкафы Буфеты
I II III IV
Прибыль

Составить математическую модель задачки и решить ее симплекс способом.


reshenie-tomskogo-oblastnogo-suda.html
reshenie-transportnoj-zadachi.html
reshenie-trigonometricheskih-neravenstv.html