Приведение общей задачи линейного программирования к канонической форме

 

Задача 1. Рзссчитайте все возможные показатели производительности труда в стоимостном и натуральном измерении, объясните разницу между ними, оцените резервы ПТ. Дано:

Показатели	план	факт
Валовая продукция в отпускных ценах, млн.руб. Выработано кирпича, тыс. штук Численность рабочих, человек Отработано чел-дней Отработано чел-часов

Задача 2. На предприятии 2860 рабочих, годовой фонд времени одного рабочего равен I860 час. В результате совершенствования технологии намечено снизить трудоемкость в течение года 400 тыс. чел.-час. Определите возможный рост ПТ на предприятии, относительное высвобождение рабочих.

 

 

1) 2860 * 1860 = 5319600 – чел/час

2) 2319600 – 400000 = 4919600 – чел/час

3) 4919600 / 1860 = 2645 – человек рабочих

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

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство a₁x₁+a₂x₂+...+a_nx_n≤b и прибавим к его левой части некоторую величину x_n+1, такую, что неравенство превратилось в равенство a₁x₁+a₂x₂+...+a_nx_n+x_n+1=b. При этом данная величина x_n+1 является неотрицательной.

Рассмотрим все на примере.

Пример 26.1

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x₄ x₅

Переменная х₄ вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x₅ вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x₄ x₅ вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

Данные задачи решаются методом линейного программирования (Симплекс-метод)

 

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