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

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

ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Пусть для простоты заданы всего 4 месторождения М₁, М₂, М₃, М₄, причем их ежемесячная добыча составляет a₁, а₂, а₃, а₄ тонн угля. Предположим далее, что этот уголь надо доставить в пункты потребления b₁, b₂, b₃, b₄, b₅, соответственно с ежемесячными потребностями этих пунктов. Будем считать, что общее производство угля равно суммарной потребности в нем (сбалансированность планов): a₁, а₂, а₃, а₄ = b₁, b₂, b₃, b₄, b₅. Задача состоит в определении такого плана перевозок, при котором общая стоимость перевозок была бы наименьшей. Обозначим через x₁₁ количество угля (в тоннах), предназначенное к отправлению из M₁ в П₁; вообще через x_ij обозначим количество угля, отправляемого из месторождения M_i в пункт потребления П_j. Схема перевозок примет вид, изображенный в таблице 4.1.

Схема перевозок таблица 4.1

	ПН	в П1	в П2	в П3	в П4	в П5	Всего
ПО							отправлено
из М1	х11	х12	х13	х14	х15	a1
из М2	х21	х22	х23	х24	х25	а2
из М3	х31	х32	х33	х34	х35	а3
из М4	х41	х42	х43	х44	х45	а4
Всего привезено	b1	b2	b3	b4	b5

4.1

ìх11+х12+х13+х14+х15 = b1 ïх21+х22+х23+х24+х25 = b2 íх31+х32+х33+х34+х35 = b3 îх41+х42+х43+х44+х45 = b4

4.2

ìх11+х12+х13+х14+х15 = a1 ïх21+х22+х23+х24+х25 = a2 íх31+х32+х33+х34+х35 = a3 îх41+х42+х43+х44+х45 = a4

Общее количество угля, привозимое в пункт П₁ из всех месторождений, будет х₁₁₊х₁₂₊х₁₃₊х₁₄₊х_{15 =} b₁; в другие пункты - П₂, П₃ и т.д. и примет вид уравнений 4.1. общее количество угля, вывозимое из М₁, будет: х₁₁₊х₁₂₊х₁₃₊х₁₄₊х_{15 =} a₁, примет вид 4.2. предполагаем, что стоимость перевозки прямо пропорциональна количеству перевозимого угля, т.е. стоимость перевозки x_ij тонн угля равна:

x _{i j} = C _{i j} ^. X _{i j}

Общая стоимость S всех перевозок будет равна: (4.3)

S=c₁₁х₁₁+c₁₂х₁₂+c₁₃х₁₃+c₁₄х₁₄+c₁₅х₁₅+... +c₄₁х₄₁+c₄₂х₄₂+c₄₃х₄₃+c₄₄х₄₄+c₄₅х₄₅.

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

À эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;

Á при этих значениях некоторая линейная функция (линейная форма) от этих неизвестных обращалась в минимум (максимум);

 эти значения были неотрицательными.

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

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

Дана система линейных уравнений:

ìа₁₁x₁+а₁₂x₂+... +а_1nx_{n =} b₁

ïа₂₁x₁+а₂₂x₂+... +а_2nx_{n =} b₂

(I) í........................

îа_m1x₁+а_m2x₂+... +а_mnx_{n =} b_m

и линейная функция ¦=c₁x₁+c₂x₂+... +c_nx_n (II).

Требуется найти такие неотрицательные решения х₁ ³ 0, х₂ ³ 0... х_n ³ 0 (III) системы (I) при которых функция ¦ принимает наименьшее (наибольшее) значение.

Уравнения (I) называются ограничениями данной задачи, уравнение (II) называется линейной формой, а уравнение (III), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым. Допустимое решение, дающее минимум функции ¦, оптимальное решение (если оно существует) не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Наконец, саму функцию ¦ часто называют линейной формой или функцией цели.

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

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