Формы записи задач линейного программирования и

Резюме

Общая распределительная задача

Сбалансированная транспортная задача

Задача оптимального планирования

Задача составления рациона или как экономно питаться

Примеры задач линейного программирования

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

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

Обозначим:

х_i – количество i -го продукта в рационе,

a_ij – содержание i -го питательного вещества в единице j -го продукта,

b_i – потребность в ингредиенте (норма).

Чтобы не загромождать модель большим числом данных, ограничимся тремя ингредиентами, но для общности возьмем разные варианты задания нормы. Все исходные данные удобно представить в таблице (табл. 1).

Таблица 1

Ингредиенты	Продукты	Норма
				min	max
Жиры	a 11	a 12	a 13	a 1 4		b 1
Белки	a 21	a 22	a 23	a 2 4	b 2
Витамины	a 31	a 32	a 33	a 3 4	b^` 3	b^`` 3
Цена	C 1	C 2	C 3	C4

Как следует из условий задачи, в качестве критерия, по которому определяется лучший вариант рациона, нужно взять суммарные затраты на продукты. Ограничения должны отражать требования по количеству ингредиентов в рационе: левая часть – фактическое поступление с продуктами, правая – норму, а отношение между ними определяется видом задания нормы (не меньше или не больше). Неотрицательность переменных очевидна из их физического смысла. В итоге приходим к следующей модели:

при условиях:

Построение модели завершено.

Предприятие выпускает несколько видов продукции.

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

Представим данные в виде таблицы (табл. 2):

Таблица 2

Виды сырья	Продукция	Количество сырья
Прибыль

Во втором и третьем столбцах указаны нормы расхода сырья на единицу продукции.

Очевидно, что критерием качества плана является прибыль. Введем переменные x ₁ и x ₂ – количество продукции 1-го и 2-го вида. Тогда модель задачи будет иметь вид

Необходимо найти такие х ₁ и х ₂, которые удовлетворяют всем условиям и доставляют максимум критерию L.

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

В качестве примера рассмотрим задачу с двумя пунктами отправления и тремя пунктами назначения, схема которой показана на рис.4.1. Здесь а ₁ и а ₂ – количество груза, которым располагают пункты отправления, b ₁, b ₂, b ₃ – потребности в грузе пунктов назначения.

Задача является сбалансированной, если суммарная потребность равна суммарной возможности. В нашем примере это значит, что

Если ввести обозначения:

x_ij - количество груза, перевозимого из i- го пункта отправления в j -й пункт назначения;

С_ij – затраты на перевозку единицы груза из i -го пункта отправления в j -й пункт назначения,

то исходные данные вместе с переменными можно представить в одной таблице (табл. 3):

Таблица 3

Пункты	B1	B2	B3	Количество груза
A1	С 11 Х 11	С 12 Х 12	С 13 Х 13	a 1
A2	С 21 Х 21	С 22 Х 22	С 23 Х 23	a 2
Потребность в грузе	b 1	b 2	b 3

Так как необходимо минимизировать суммарные затраты по перевозке, то целевая функция запишется в виде

L=C ₁₁ x ₁₁ + C ₁₂ x ₁₂ + C ₂₃ x ₂₃ → min.

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

B₁: x ₁₁ +x ₂₁ =b ₁;

B₂: x ₁₂ +x ₂₂ =b ₂;

B₃: x ₁₃ +x ₂₃ =b ₃.

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

А₁: х ₁₁ +х ₁₂ +х ₁₃ =а ₁;

А₂: х ₂₁ +х ₂₂ +х ₂₃ =а ₂.

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

" x_ij³0.

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

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

Как и в предыдущих примерах, исходные данные задачи можно представить в виде таблицы, где C_ij – доход, прибыль или затраты при выделении единицы ресурса i -го вида на j -ю работу (табл. 4):

Таблица 4

Виды ресурсов	Работы (операции)	Количество ресурсов
		…	n
	С 11	С 12	…	С 1 n	a 1
	С 21	С 22	…	C 2 n	a 2
…	…	…	…	…	…
m	Cm 1	Cm 2	…	Cmn	am
Потребность	b 1	b2	…	bn

Если C_ij – прибыль или выигрыш, то имеем задачу максимизации, если же C_ij – затраты или убытки, то задачу минимизации.

К распределительным задачам относятся и транспортные задачи. Пример такой задачи приведен выше. Нетрудно видеть, что в транспортной задаче единицы измерения ресурсов и потребностей одинаковы. Если же единицы измерения не совпадают, то имеет место общий случай задачи распределения.

Другим важным частным случаем задачи распределения (и транспортной задачи) является задача о назначениях или задача выбора. Она отличается от общего случая тем, что по условиям задачи с каждым ресурсом можно оперировать только как с единым целым, он либо направляется на работу, либо нет. Работе также требуется только один вид ресурса, причем целиком. Иначе говоря,. потребности и ресурсы неделимы. Следовательно, в задаче о назначениях всегда a_i =1, b_j =1 и x_ij – булевы, " ij.

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

Рассмотрим пример общей распределительной задачи.

Пусть с железнодорожной станции необходимо отправить n видов грузов в количестве b_j, j =1, 2, …, n. Станция может использовать m видов вагонов в количестве a_i, i =1, 2, …, m. Для каждого вида вагона известна норма загрузки i –го вагона j – м грузом - B_ij. Известны затраты на погрузку i -го вагона j -м грузом - С_ij. Необходимо организовать отправку груза наилучшим образом, т.е. с минимальными затратами на погрузку.

Как видно, здесь ресурсы – вагоны разных типов (единицы измерения - штуки), а потребность – груз (тонны или м³). Единицы измерения разные, следовательно, это задача общего вида.

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

Тогда приходим к модели задачи, которая включает:

критерий

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

ограничения-неравенства, учитывающие ограниченное число вагонов каждого вида,

и условия неотрицательности переменных

x_ij ³0, " i,j.

Размерность задачи определяется значениями n и m.

Принципиальное отличие данной модели от транспортной содержится в первой группе ограничений – это наличие коэффициентов B_ij. Если бы все B_ij равнялись единице, мы имели бы модель несбалансированной транспортной задачи (и тогда размерности x_ij, b_j и a_i совпадают).

Рассмотренные модели задач объединяет одно свойство: все функции, входящие в модель (целевая и ограничения), являются линейными относительно искомых переменных. Нетрудно видеть, что задача описывается линейной моделью, если справедливы 3 свойства:

· аддитивности (сложение составляющих затрат, прибыли, времени и т.д.);

· пропорциональности (прибыль, расход пропорциональны количеству продкукции, услуг);

· непрерывности переменных.

Несмотря на сходство в главном, приведенные модели отличаются по виду экстремума (max или min) и/или по виду ограничений (равенства, неравенства, знаки неравенств). Возможны также задачи, в которых часть переменных не имеет ограничений по знаку (например, температура в градусах Цельсия, величина дебаланса, отклонение от заданного значения и т.п.). Чтобы абстрагироваться от этих несущественных отличий при использовании методов решения линейных задач, модели приводят к некоторому единому виду. Основными являются две формы представления задач ЛП, которые рассматриваются ниже.

Дата добавления: 2014-01-11