Решение задачи линейного программирования - задачи о ресурсах

stify">       Функция f в задаче достигает своего минимального значения в точке F.

       Оптимальному  решению соответствует точке  F которой лежит на пересечении прямых: 

       

 

       Для определения координат точки  F решим систему:

       

 

       В результате получили: 

 и ,

. 

       Оптимальное решение:

соответствует значению целевой функции:

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

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

 

       

Рисунок 1 – Графическая модель задачи линейного программирования 

       Ответ: задача достигает своего максимального  значения в точке F , ей соответствует значение целевой функции ден.ед.

       Задача  достигает своего минимального значения в точке O , ей соответствует значение целевой функции  

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

       Прежде  чем решить задачу симплекс методом необходимо ее привести к канонической форме.

       Запишем задачу линейного программирования в канонической форме так как  целевая функция минимизируется для ее преобразовании умножаем обе части на минус единицу.

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

 

       Базисные  переменные:

       Небазисные переменные:

       Находим исходное базисное решение, для этого  базисные переменные приравниваем к  нулю и вычисляем значение базисных переменных: 

 

       Строим  и заполняем симплексную таблицу 2.

       В столбце «Базис» записываются базисные переменные: .

       В столбце С коэффициенты при базисных переменных целевой функции (C_i), в столбце «В» — свободные члены ограничений , т. е. значения базисных переменных. В столбцах небазисные переменные - , отражаются коэффициенты при небазисных переменных в ограничениях над переменными — коэффициенты при этих переменных, в целевой функции ( ). Строка «∆» в столбце «В» содержит значение целевой функции, которое рассчитывается по формуле: 

,

 

       Результат заносим в таблицу 2 

Таблица 2

 

столбцы этой же строки — значения относительных оценок , рассчитываемых по формуле:

.

       Получим: 

 

       Проверим  полученный базисный план на оптимальность по условию оптимальности.

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

       Необходимо  переходить к другому базисному плану. Для перехода к новому базисному плану в первую очередь из числа небазисных переменных с отрицательными оценками ∆_j выбирается переменная, которая вводится в базис. Введем в новый базис переменную х₁, которой соответствует наибольшая по абсолютной величине отрицательная оценка ∆_j:  

 

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

       Выбираем  переменную, которая выводится из базиса, ее индекс r находится из соотношения: 

. 

       Получим: 

 

       Выбираем  столбец в котором получено наименьшее положительное отношение:

– главная строка, связана с переменной , то есть – выводится из базиса.

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

       Рассчитаем  элементы главной строки по формуле (8) и (9): 

 

       Вычислим значение главного элемента по формуле (10): 

 

       Вычислим  элементы главного столбца по формуле (11): 

 

       Вычислим  все остальные элементы таблицы по формуле (13): 

 

       Получим по формуле (15):

       Результат заносим в таблицу 3 

Таблица 3

 

       Данный  базисный план является оптимальным, так  как отсутствует отрицательная относительная оценка. 

       2.5 Двойственная задача линейного программирования 

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

1. Целевая функция исходной задачи максимизируется, то целевая функция z двойственной – минимизируется и наоборот.
2. Количество ограничений ( ) исходной задачи равно количеству переменных двойственной, а количество переменных ( ) исходной равно количеству ограничений двойственной. Переменные двойственной задачи обозначим через

.

3. Поскольку переменные сходной задачи связаны с ограничениями двойственной, каждой переменной соответствует в двойственной задаче ограничениям вида « » (z max) или « », и наоборот.
4. Каждой переменной , не ограниченной по знаку, соответствует ограничение вида « » двойственной задачи, и наоборот.
5. Свободные члены ограничений исходной задачи в двойственной являются коэффициентами при переменных, в целевой функции, а коэффициенты при переменных в целевой функции исходной задачи являются свободными членами ограничений двойственной.
6. Матрица А коэффициентов при неизвестных в ограничениях исходной задачи в двойственной транспортируется (А^Т).

 

 

       Целевая функция исходной задачи max ( ), значит, целевая функция двойственной задачи будет min ( ). Количество ограничений в исходной задаче равно трем, значит, переменных в двойственной задаче будет три: Переменных в исходной задаче две, значит, ограничений в двойственной задаче будет два. Так как переменные исходной задачи неотрицательные, ограничения в двойственной задаче будут иметь вид неравенства. Так как двойственная задача min, значит, ограничения будут иметь вид неравенства « ». Правые части ограничений являются коэффициентами при переменных в целевой функции двойственной задачи, а коэффициенты в целевой функции исходной задачи будут правыми частями ограничений в двойственной задаче.