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

24 вариант

Задачи линейного программирования решаются графическим способом, если количество переменных меньше или равно 2.

Исходные данные:

Решить систему неравенств графическим методом. Определить ОДЗ. Проверить решение. Найти максимальное и минимальное значение целевой функции графическим и математическим способом:

Z = 4х₁ + 8х₂

1,5х₁ + 4х₂ ≥ 4500

х₁ + 3х₂ ≤ 7000

5,7х₁ – 1,5х₂ ≥ 80

х₁ ≥ 0

х₂ ≥ 150

Последовательность решения:

1. Для решения задается система координат.

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

1 уравнение: 1,5х₁ + 4х₂ ≥ 4500 → 1,5х₁ + 4х₂ = 4500

х₁ = 0 → х₂ = 1125

х₂ = 0 → х₁ = 3000

2 уравнение: х₁ + 3х₂ ≤ 7000 → х₁ + 3х₂ = 7000

х₁ = 1000 → х₂ = 2000

х₂ = 0 → х₁ = 7000

3 уравнение: 5,7х₁ – 1,5х₂ ≥ 80 →5,7х₁ – 1,5х₂ = 80

х₁ = 0 → х₂ = - 53,33

х₂ = 0 → х₁ = 14,04

4 уравнение: х₁ ≥ 0 → х₁ = 0

5 уравнение: х₂ ≥ 150 → х₂ = 150

Рассматривая каждое из уравнений, одну из переменных приравниваем к 0, и по решению уравнения находим решение второй переменной. Затем вторую переменную приравниваем к 0 и находим значение первой переменной. По двум найденным точкам строится прямая и обозначается ОДЗ.

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

17 вариант

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

Такие задачи содержат много переменных и ограничений, ОДЗ этих задач представляет собой выпуклый многогранник.

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

Исходные данные: 100Х₁ + 250Х₂ + 150Х₃ → max

Х₁ + Х₂ + Х₃ ≤ 240

210Х₁ + 104Х₂ + 478Х₃ ≤ 140

280Х₁ - 190Х₂ ≤ 0

Х₁ + Х₃ ≤ 177

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

Х₁ + Х₂ + Х₃ + S₁ = 240

210Х₁ + 104Х₂ + 478Х₃ + S₂ = 140

280Х₁ - 190Х₂ + S₃ = 0

Х₁ + Х₃ + S₄ = 177

Z = 100Х₁ + 250Х₂ + 150Х₃ + S₁+ S₂ + S₃+ S₄→ max

Нахождение оптимального базисного плана

Формальным признаком оптимального плана является содержание индексной строки. При решении задач на max, план считается оптимальным, когда отсутствуют оптимальные коэффициенты, наличие в индексной строке отрицательных коэффициентов свидетельствует о необходимости улучшения плана, т.е. в план необходимо ввести переменную, которая улучшит функционал. Для этого по коэффициентам индексной строки выбираем главный столбец. Главный столбец показывает, какая переменная должна войти в план. При решении на max главный столбец выбирается по наименьшей абсолютной величине среди отрицательных коэффициентов,в моем варианте это -250, значит Х ₂ войдет в план. Определить на какое место в план должна войти переменная, т.е. в главную строку. Главная строка выбирается по симплексному отношению – это отношение свободных членов на соответствующие элементы главного столбца, и выбирается наименьшее, положительное, не равное 0, симплексное отношение, в моем варианте это S₁. Пересечение главного столбца и главной строки определяет главный элемент, в моем варианте это 104. Главный элемент необходим для пересчета следующей симплексной таблицы. Пересчет новой симплексной таблицы начинается с коэффициентов строки, которая в предыдущей таблице была главной.

Рассчитываем коэффициенты главного столбца. При этом применяем новую процедуру – метод Гаусса. Все элементы главного столбца принимаем за 0. Далее заполняются все коэффициенты, которые не вошли ни в столбец, ни в строку по правилу «прямоугольника»:

Таблица 1 - Первая симплексная таблица

Оценка баз.переменной	Баз. переменная	Значение баз.переменной	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
			100	250	150	0	0	0	0
0	S1	240	1	1	1	1	0	0	0
0	S2	140	210	104	478	0	1	0	0
0	S3	0	280	-190	0	0	0	1	0
0	S4	177	1	0	1	0	0	0	1
Индексная строка	Z	0	-100	-250	-150	0	0	0	0

Симплексное отношение, находим главную строку: 240 /1 = 240; 140/104 = 1,346; 0/(-190) = 0; 177/0-не делится, отсюда следует главный элемент = 104. Пример расчета остальных коэффициентов:

240 – = 238,65

0 – = 255,77

0 – = 336,5

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

Таблица 2 - Вторая симплексная таблица

Оценка баз.переменной	Баз. переменная	Значение баз.переменной	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
			100	250	150	0	0	0	0
0	S1	238,65	-1,02	0	-3,60	1	-0,01	0	0
250	Х2	1,346	2,02	1	4,60	0	0,01	0	0
0	S3	255,77	663,65	0	873,27	0	1,83	1	0
0	S4	177	1	0	1	0	0	0	1
Индексная строка	Z	336,5	404,81	0	999,04	0	2,40	0	0

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

Проверка:

100Х₁ + 250Х₂ + 150Х₃ = 336,5

100*0 + 250*1,346 + 150*0 = 336,5

336,5 = 336,50 (верно)

Х₁ + Х₂ + Х₃ ≤ 240

0 + 1,346 + 0 ≤ 240

1,346 ≤ 240 (верно)

210Х₁ + 104Х₂ + 478Х₃ ≤ 140

210*0 + 104*1,346 + 478*0 ≤ 140

139,98 ≤ 140 (верно)

280Х₁ - 190Х₂ ≤ 0

280*0 – 190*1,346 ≤ 0

-255,74 ≤ 0 (верно)

Х₁ + Х₃ ≤ 177

0 +0 ≤ 177

0 ≤ 177 (верно)

Анализ последней симплексной таблицы и двойственных оценок:

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

В последней симплексной таблице имеются коэффициенты замещения.

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

Предположим, что ресурс Х₁ увеличивается на одну единицу, тогда:

Коэффициент -1,02 показывает, что объем недоиспользованного ресурса S₁ увеличится и будет равен 239,67.

Коэффициент 2,02 мы не можем ввести в базис, потому что условие Х_n ≥ 0 не соблюдается, Х₂ =1,346 – 2,02*1 = -0,7.

Коэффициент 663,6 мы не можем ввести в базис, потому что условие Х_n ≥ 0 не соблюдается, S₃ = 255,77 – 663,6*1 = -407,9.

Коэффициент 1 показывает, что объем недоиспользованного ресурса S₄ уменьшится и будет равен 176.

Коэффициент 404,81 мы не можем ввести в базис, потому что условие Х_n ≥ 0 не соблюдается, Z = 336,5 – 404,81*1 = -68,3.

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

Свойства двойственных оценок.

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

В нашем случае одна дополнительная переменная S₂ имеет ненулевую двойственную оценку 2,40 соответственно, это говорит о том, что ограничение выполнено как строгое равенство, т.е. ресурсы дефицитны.

2. Второе связано с мерой влияния ограничения на функционал. Не нулевая оценка по ресурсам показывает, на сколько увеличится или уменьшится функционал при увеличении или уменьшении ресурса на 1.

3. Для двойственной оценки характерна определенная устойчивость к изменению параметров правой части модели и неустойчивость к изменению технико-экономических коэффициентов и коэффициентов целевой функции.

4. Взаимозаменяемость ресурсов или продуктов.

5. Мера рентабельности отдельных переменных вошедших в план.

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

Предположим, что необходимо ввести ресурс Х₁ = 1. Для корректировки используются коэффициенты столбца не базисной переменной Х₁. Новое решение рассчитывается по формуле: Хⁿ_j = X_j – k_i * T, где

Хⁿ_j – новое значение базисной переменной;

X_j – значение переменной полученное в оптимальном решении;

k_i – коэффициенты столбца переменной включаемые в базис;

T – величина переменной вводимой в базис;

Sⁿ₁ = 238,65 – (-1,02)*1 = 239,67

Sⁿ₄ = 177 – 1*1 = 176