Дискуссионное исследование действующего и перспективного законодательства


Линейное программирование



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



Главная >> Высшая математика >> Линейное программирование



image

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


Нужно обойти антиплагиат?
Поднять оригинальность текста онлайн?
У нас есть эффективное решение. Результат за 5 минут!



Составляющие математической модели

 

Для решения экономических задач применяются математические модели.

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

Составление математической модели включает:
  • выбор переменных задачи
  • составление системы ограничений
  • выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, кᴏᴛᴏᴩые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2,...,Xn).

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

Целевой функцией задачи называют функцию переменных задачи, кᴏᴛᴏᴩая характеризует качество выполнения задачи и экстремум кᴏᴛᴏᴩой требуется найти.

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

Математическая модель

Данная запись означает следующее: найти экстремум целевой функции (1) и ϲᴏᴏᴛʙᴇᴛϲᴛʙующие ему переменные X=(X1, X2,...,Xn) при условии, что данные переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности. Материал опубликован на http://зачётка.рф

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при кᴏᴛᴏᴩом целевая функция достигает экстремума.

Пример составления математической модели

Задача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

  • bi ( i = 1,2,3,...,m) — запасы каждого i-го вида ресурса;
  • aij ( i = 1,2,3,...,m; j=1,2,3,...,n) — затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
  • cj ( j = 1,2,3,...,n) — прибыль от реализации единицы объема j-го вида продукции.

Требуется составить план производства продукции, кᴏᴛᴏᴩый обеспечивает максимум прибыли при заданных ограничениях на ресурсы (сырье).

Решение:

Введем вектор переменных X=(X1, X2,...,Xn), где xj ( j = 1,2,...,n) — объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, по϶ᴛᴏму ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj , по϶ᴛᴏму целевая функция равна:

Ответ - Математическая модель имеет вид:

Математическая модель

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

 

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

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

Она может быть представлена в координатной, векторной и матричной записи.

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

Каноническая форма

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

Матричная запись

Здесь:

  • А — матрица коэффициентов системы уравнений
  • Х — матрица-столбец переменных задачи
  • Ао — матрица-столбец правых частей системы ограничений

Нередко могут быть использованы задачи линейного программирования, называемые симметричными, кᴏᴛᴏᴩые в матричной записи имеют вид:

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

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

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

Возьмем линейное неравенство a1x1+a2x2+...+anxn≤b и прибавим к его левой части некᴏᴛᴏᴩую величину xn+1 , такую, что неравенство превратилось в равенство a1x1+a2x2+...+anxn+xn+1=b. При ϶ᴛᴏм данная величина xn+1 будет неотрицательной.

Изучим все на примере.

Пример 26.1

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для ϶ᴛᴏго изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:









(С) Юридический репозиторий Зачётка.рф 2011-2016

Яндекс.Метрика