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

Процесс построения математической модели начинается с ответов на следующие вопросы:

1. Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные задачи?

2. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?

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

Рассмотрим некоторые общие модели и задачи.

Задача производственного планирования.

Некоторый экономический объект (предприятие, цех, фирма) может производить п видов некоторой продукции. В процессе производства используется т видов ресурсов (сырья). Применяемые технологии характеризуются нормами затрат сырья на единицу производимого продукта – a_ij – норма расхода сырья i-го вида производство единицы продукции j-го вида. Известны ограничения на ресурсы, которые расходуются в процессе производства – b_i – запас сырья i-го вида, а также доход от единицы продукции j-го вида – с_j. Определить план производства, который принесет наибольший суммарный доход экономическому объекту.

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

Таблица 2.1

Обозначим через х_j – количество выпускаемой продукции j-го вида.

В рамках описанных выше технологий на производство всей продукции первого вида расход сырья первого вида составит а₁₁х₁, на производство всей продукции второго вида – а₁₂х₂, и, так далее, на производство всей продукции п-го вида – а_1пх_п. Общие затраты сырья первого вида можно представить в виде суммы:

а₁₁х₁ + а₁₂х₂ + … + а_1пх_п.

Поскольку запасы сырья ограничены, то эта сумма не должна превышать величину запаса сырья первого вида – b₁, т.е.

а₁₁х₁ + а₁₂х₂ + … + а_1пх_п b₁.

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

а₂₁х₁ + а₂₂х₂ + … + а_2пх_п b₂,

……………………………….

а_т1х₁ + а_т2х₂ + … + а_тпх_п b_т.

К системе ограничений также должны быть добавлены естественные ограничения на неотрицательность переменных х₁, х₂, … , х_п, поскольку количество продукции любого вида не может быть отрицательным:.

Доход, получаемый от производства всей продукции первого вида равен с₁х₁, от производства всей продукции второго вида – с₂х₂, и так далее, от производства всей продукции п-го вида – с_пх_п . Суммарный доход равен

с₁х₁ + с₂х₂ + … + с_пх_п.

Таким образом, задача заключается в нахождении таких переменных х₁, х₂, …, х_п , которые удовлетворяют системе ограничений

и обращают функцию дохода z = с₁х₁ + с₂х₂ + … + с_пх_п в максимум.

Задача оптимальной загрузки оборудования.

Предприятию нужно выпустить продукции П₁ по плану N₁ единиц, продукции П₂ – N₂ единиц, и так далее, продукции П_k – N_k единиц. Продукция обрабатывается на взаимозаменяемом оборудовании В₁, В₂, …, В_т различной мощности. Также известны следующие величины: a_ij – норма времени на обработку единицы продукции i-го вида на оборудовании j-го вида; А_j – фонд времени оборудования j-го вида, с_ij – себестоимость обработки продукции i-го вида на оборудовании j-го вида. Спланировать выпуск продукции П_j, чтобы себестоимость ее была наименьшей и план выпуска продукции был выполнен.

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

Таблица 2.2

Обозначим х_ij – количество продукции i-го вида, которая обрабатывается на оборудовании j-го вида.

Фактические затраты времени на обработку всей продукции П₁ на оборудовании В₁ составят а₁₁х₁₁, на обработку всей продукции П₂ на оборудовании В₁ – а₁₂х₁₂, и, так далее, на обработку всей продукции П_k – а_1пх_1п. Общие затраты времени на обработку всей продукции на оборудовании В₁ можно представить в виде суммы:

а₁₁х₁₁ + а₁₂х₁₂ + … + а_1kх_1k.

Поскольку фактические затраты времени не могу превышать отведенные фонды, то эта сумма не должна превышать А₁, т.е.

а₁₁х₁₁ + а₁₂х₁₂ + … + а_1kх_1k А₁.

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

а₂₁х₂₁ + а₂₂х₂₂ + … + а_2kх_2k А₂,

……………………………….

а_т1х_т1 + а_т2х_т2 + … + а_тkх_тk А_т.

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

х₁₁ + х₂₁ + … + х_m1 = N₁.

х₁₂ + х₂₂ + … + х_m2 = N₂,

…………………………

х_1т + х_2т + … + х_тk = N_k.

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

Общая себестоимость обрабатываемой продукции равна

z = c₁₁х₁₁+c₁₂х₁₂+…+c_1kх_1k+c₂₁х₂₁+c₂₂х₂₂+…+c_2kх_2k+…+c_т1х_т1+c_т2х_т2+…+c_тkх_тk.

Таким образом, задача заключается в нахождении таких переменных х₁, х₂, …, х_п , которые удовлетворяют системе ограничений

и обращают функцию себестоимости в минимум.

Задача о смесях.

К таким задачам относится класс математических моделей, касающийся экономических проблем, связанных с изготовлением различных смесей (сплавов металлов, химических веществ, производства нефтепродуктов и др.).

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

Пусть х_i – количество i-го вида сырья в смеси; т – количество видов сырья; п – количество ингредиентов в смеси; а_ij – количество ингредиента j-го вида, содержащегося в единице i-го вида сырья; b_j – минимальное количество ингредиента j-го вида, содержащегося в единице смеси; с_i – стоимость единицы сырья i-го вида; q – минимальный общий вес смеси, используемый фирмой.

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

Таблица 3

В единице сырья первого вида содержится а₁₁ единиц первого ингредиента, а во всем сырье первого вида этого ингредиента будет а₁₁х₁. Этого же ингредиента в единице сырья второго вида содержится а₁₂ единиц, а во всем сырье второго вида этого ингредиента будет а₁₂х₂ и так далее, а_1nх_n – количество первого ингредиента в п-м виде сырья. Общее количество сырья первого вида, содержащегося во всех смесях равно

а₁₁х₁ + а₁₂х₂ + … + а_1nх_n.

Поскольку известно, что минимальное количество ингредиента первого вида, содержащегося в единице смеси должно быть b₁ , имеем следующее ограничение

а₁₁х₁ + а₁₂х₂ + … + а_1nх_nb₁ .

Рассмотрим второй вид ингредиента. Необходимо учесть содержание этого ингредиента во всем количестве смеси первого сырья, второго и т.д. до п-го вида сырья. Суммируя отдельные значения количества единиц второго вида ингредиента во всех смесях, получим общее количество второго вида ингредиента. Она должно быть не меньше минимального количества ингредиента второго вида, содержащегося в единице смеси b₂. Аналогично предыдущим рассуждениям, можно установить соотношения между содержанием ингредиента любого вида во всех смесях и минимальным количеством этого ингредиента в смеси. В результате придем к системе ограничений на питательность смеси:

Переменные х₁, х₂, …, х_n , представляющие собой количества ингредиента первого, второго и т.д., до п-го вида, не могут быть отрицательными. В случае, если какой-либо ингредиент не входит в состав смеси, то соответствующая переменная будет равно нулю. Таким образом, придем к системе ограничений на неотрицательность переменных

х₁ 0, х₂0, …, х_n 0.

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

х₁ + х₂ + … + х_n q.

Зная, что цена единицы сырья первого вида с₁, можем вычислить стоимость всего сырья первого вида – с₁х₁. Аналогично стоимость всего сырья второго вида – с₂х₂ и т.д., стоимость всего сырья п-го вида – с_nх_n. Суммарная стоимость всех видов сырья, используемых в приготовлении смеси, равна сумме всех этих стоимостей.

Таким образом задача о смесях заключается в нахождении величин х₁, х₂, …, х_n , удовлетворяющих ограничениям

и дают минимум целевой функции

z = с₁х₁ + с₂х₂ +…+ с_nх_n.

Транспортная задача.

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

Транспортная задача принадлежит к специальному классу распределительных задач линейного программирования. Пусть нужно перевезти однородный груз из m пунктов отправления А₁, А₂,…,А_т в n пунктов потребления B₁, B₂,…, B_п. Известно количество груза a_i (запасы), находящееся у i-го поставщика (постоянно), а также объемы потребностей в нем b_j (заявки) j-го потребителя. Известны также затраты на перевозку единицы груза от i-го поставщика к j-му потребителю – тариф – с_ij. Необходимо распределить груз таким образом, чтобы затраты на его перевозку были минимальными.

Обозначим х_ij – количество груза, перевозимого из i-го пункта отправления в j-го пункт назначения.

Решение (план перевозок) определяется матрицей размерности ()

.

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

х₁₁ + х₁₂ + … + х_1п а₁.

х₂₁ + х₂₂ + …+ х_2п а₂,

……………………….

х_т1 + х_т2 + … + х_тп а_т.

Заявки, поданные пунктами потребления, должны быть выполнены:

х₁₁ + х₂₁ + … + х_m1 = b₁.

х₁₂ + х₂₂ + … + х_m2 = b₂,

…………………………

х_1т + х_2т + … + х_тп = b_п.

Естественно, что все неизвестные не могут принимать отрицательные значения, т.е. .

Общая стоимость перевозок равна

z = c₁₁х₁₁+c₁₂х₁₂+…+c_1пх_1п+c₂₁х₂₁+c₂₂х₂₂+…+c_2пх_2п+…+c_т1х_т1+c_т2х_т2+…+c_тпх_тп.

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

и обращают функцию транспортных расходов в минимум.

Обобщая рассмотренные примеры, можно сделать следующие выводы:

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

• линейная функция может стремиться как к максимуму, так и к минимуму.

• переменные в задачах всегда неотрицательны.

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

В задаче линейного программирования (ЗЛП) нужно найти экстремум (максимум или минимум) линейной целевой функции :

, (2.1.1)

при ограничениях:

(2.1.2)

В формулах (2.1.1), (2.1.2) – заданные постоянные величины, причем ; символ означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или другую сторону).

ЗЛП (2.1.1), (2.1.2) можно записать в следующих формах: канонической, векторной, матричной.

Каноническая форма ЗЛП имеет вид (2.1.3), (2.1.4):

, (2.1.3)

, (2.1.4)

Векторная форма ЗЛП имеет вид (2.1.5), (2.1.6):

, (2.1.5)

, (2.1.6)

,

где .

Матричная форма ЗЛП имеет вид (2.1.7), (2.1.8):

, (2.1.7)

,, (2.1.8)

где - матрица размера ,, .

Для решения ЗЛП приведем на следующие утверждения.

Теорема 1. Область допустимых решений задачи линейного программирования является выпуклым множеством.

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

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

2.2. Графический метод решения задачи линейного

программирования

Графический метод решения ЗЛП основан на утверждениях, приведенных в пункте 2.1. Согласно теореме 2, оптимальное решение находится в вершине многоугольника решений и поэтому решить ЗЛП – найти вершину многоугольника решений, координаты которой дают оптимальное значение целевой функции.

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