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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₄. В 2-м неравенстве смысла (≤) вводим базисную переменную x₅:

0.5x₁ + 0.7x₂ + 0.6x₃ + 1x₄ + 0x₅ = 370

0.1x₁ + 0.3x₂ + 0.2x₃ + 0x₄ + 1x₅ = 90

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

Решим систему уравнений относительно базисных переменных: x₄, x₅.

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0, 0, 0, 370, 90)

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (0.3) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x₅ в план 1 войдет переменная x₂. Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=0.3.

На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (0.3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

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

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.27) и находится на пересечении ведущего столбца и ведущей строки:

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 2 войдет переменная x₁. Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=0.27.

На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

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

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Оптимальный план можно записать так:

x₁ = 600 (партий);

x₂ = 100 (партий).

F(X) = 5 • 600 + 8 • 100 = 3800 (усл.ед.).

3. Построим двойственную задачу по следующим правилам.

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.

2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

Расширенная матрица A:

Транспонированная матрица A^T:

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Неравенства, соединенные стрелочками (↔), называются сопряженными.

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Выясним экономический смысл двойственной задачи. Заметим, что каждое слагаемое в левой части ограничений должно измеряться в тех же единицах, что и правая.

у₁ – цена одной единицы первого ресурса (1 часа работы продавца).

у₂ – цена одной единицы второго ресурса (1 м² площади торгового зала).

0, 5y₁+0, 1y₂ – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого вида.

0, 7у₁+0, 3у₂ это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий второго вида.

370y₁+90y₂ – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого и второго вида.

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

Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на x_j:

0.5y₁+0.1y₂≥ 5

0.7y₁+0.3y₂≥ 8

0.6y₁+0.2y₂≥ 6

370y₁+90y₂ → min

y₁ ≥ 0, y₂ ≥ 0.

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

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из первой теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис:

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 8.75;

y₂ = 6.25.

Z(Y) = 370*8.75+90*6.25 = 3800 (усл.ед.)

4. Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

0.5*600 + 0.7*100 + 0.6*0 = 370 = 370

0.1*600 + 0.3*100 + 0.2*0 = 90 = 90

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁> 0).

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₂> 0).

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

5. Обоснование эффективности оптимального плана.

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

0.5*8.75 + 0.1*6.25 = 5 = 5

0.7*8.75 + 0.3*6.25 = 8 = 8

0.6*8.75 + 0.2*6.25 = 6.5 > 6

1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый продукт экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₁> 0).

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый продукт экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂> 0).

3-ое ограничение выполняется как строгое неравенство, т.е. продукцию 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₃ = 0.

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

При этом разница между ценами (6.5 - 6 = 0.5) показывает величину изменения целевой функции F(x) при введении дополнительной единицы x_i.

Анализ устойчивости оптимального плана.

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

Чувствительность решения к изменению коэффициентов целевой функции.

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

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

Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

1-ый параметр целевой функции может изменяться в пределах:

∆ c₁^- = min [y_k/d_1k] для d_1k> 0.

∆ c₁⁺ = |max [y_k/d_1k]| для d_1k< 0.

где в знаменателе коэффициенты столбцов свободных переменных в оптимальном плане (коэффициенты структурных сдвигов, элементы обратной матрицы к базису оптимального плана).

Таким образом, 1-параметр может быть уменьшен на 2.33 или увеличен на 0.71.

Интервал изменения равен:

(c₁ - ∆ c₁^-; c₁ + ∆ c₁⁺)

[5-2.33; 5+0.71] = [2.67; 5.71]

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

2-ый параметр целевой функции может изменяться в пределах:

∆ c₂^- = min [y_k/d_2k] для d_2k> 0.

∆ c₂⁺ = |max [y_k/d_2k]| для d_2k< 0.

Таким образом, 2-параметр может быть уменьшен на 1 или увеличен на 7.

Интервал изменения равен:

(c₂ - ∆ c₂^-; c₂ + ∆ c₂⁺)

[8-1; 8+7] = [7; 15]

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