МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

ВВЕДЕНИЕ

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

В общем виде математическая постановка задачи математического программирования (ЗПМ) такова: среди всех решений системы ограничений (2)

Найти то или те, которые доставляют максимум или минимум функции (1).

 

      f(x₁, x₂, ..., x_n) → max (min),                                       (1).

      g_i(x₁, x₂, ..., x_n)< = b_i(> =b_i),                                                                    (2)

 

где f и g_i  - заданные функции, а b_i – заданные действительные числа, i = 1…m.

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

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

ОБЩАЯ ПОСТАНОВКА ЗЛП

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

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

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

Примеры ЗЛП

Задача 1 — об использовании ресурсов. Из сырья двух видов:
S₁ и S₂, запасы которого ограничены и составляют соответственно
b₁ и b₂, единиц. изготавливается продукция трех видов: Р₁, Р₂ и
Р₃. Известно количество единиц сырья каждого вида, необходимое для производства единицы каждого вида продукции. Введем обозначение a_ij –количества единиц i – го вида сырья, необходимое для производства единицы продукции p_j  , где i = 1, 2; j = 1, 2, 3. известен доход от реализации единицы каждого вида продукции – c_j j = 1, 2, 3.

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

Полезно для понимания смысла задачи поместить данные в таблицу (табл.1).

Таблица 1

Вид ресурса	Число единиц ресурса, затрачиваемых на изготовление единицы продукции			Запас ресурсов
	P1	P2	P3
S1	a11	a12	a13	b1
S2	a21	a22	a23	b2
Прибыль от единицы	c1	c2	c3

        

Решение.

1. Выберем переменные. Пусть x_j  -число единиц продукции вида P_j  , запланированное к производству, j = 1, 2, 3.

2. Очевидно, x_j > =0.                                                                             (1)

3. Цель – получение наибольшей суммарной прибыли. Суммарная прибыль f составит сумму c₁x₁ денежных единиц от реализации запланированной продукции P₁ , c₂x₂ –от продукции P₂, c₃x₃ – от продукции P₃, т.е.

                    f= c₁x₁+c₂x₂+c₃x₃ → max…                                          (2)

4. Для изготовления запланированного объема продукции потребуется (a₁₁x₁+a₁₂x₂+a₁₃x₃) единиц ресурса S₁ для S₂ – аналогично. Так как потребление ресурсов не должно превышать их запасов, соответственно b₁ и b₂, то связь между потреблением ресурсов и их запасами выразится системой неравенств:  

                                                                  (3)

Постановка математической задачи: среди всех неотрицательных решений системы неравенств (3) найти то или те, при которых функция (2) принимает максимальное значение.

Так как функция (2) линейная, асистема (3) содержит только линейные неравенства, то задача (1) – (3) является задачей линейного программарования.

Задача 2. Транспортная задача (ТЗ) по критерию стоимости.

Пусть имеются два пункта отправления А1 и А2, в которых сосредоточено соответственно а1, а2 единиц однородного груза. Весь этот груз следует перевезти в три пункта назначения: В1, В2, В3. Причем потребности пунктов назначения известны и составляют соответственно b₁, b₂, b₃ единиц этого груза. Стоимость перевозки единицы груза из каждого пункта отправления А_i в каждый пункт назначения B_j известно; обозначим её c_ij  - денежных единиц.

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

                                             

                                     а₁+а₂=b₁+b₂+b₃                                                 (4)

 

Решение.

1. Выберем переменные. Пусть x_ij - количество единиц груза, предназначенного для перевозки из пункта отправления А1 в пункт назначения В_j; i = 1, 2; j = 1, 2, 3.

2. Очевидно,

                            x_ij> =0, i=1, 2, j= 1, 2, 3.                                                  (5)

Таблица 2

Пункты отправления	Стоимость перевозки единицы груза в пункты назначения			Запасы груза
	B1	B2	B3
A1	c11	c12	c13	a1
A2	c21	c22	c23	a2
Потребности в грузе	b1	b2	b3	a1= b1

3. Цель – минимальная суммарная стоимость перевозок. Суммарная стоимость перевозок f складывается из стоимостей перевозок всех запланированных объемов. Так, если из пункта А1 в пункт В1 следует перевезти х₁₁ единиц груза, причем стоимость перевозки единицы груза с₁₁ денежных единиц, то оказанная перевозка оценивается в с₁₁х₁₁ денежных единиц. Суммируя, получаем:

     f=c₁₁x₁₁+c₁₂x₁₂+c₁₃x₁₃+c₂₁x₂₁+c₂₂x₂₂+c₂₃x₂₃.                                  (6)

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

 

 

                    х₁₁+х₁₂+х₁₃ = а₁

                    х₂₁+х₂₂+х₂₃ = а₂.                                                              (7)

 

Систему уравнений (7) называют ограничениями по запасам.

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

 

        х₁₁+х₂₁ = b₁

               х₁₂+х₂₂ = b₂                                                                                            (8)

        х₁₃+х₂₃ = b₃                       

 

 

Систему уравнений (8) называют ограничениями по потребностям.

Постановка математической задачи: среди всех неотрицательных решений системы уравнений (7), (8) найти то или те, при которых функция (6) достигает минимума.

Задача 3. – задача о смесях. При откорме животных каждое животное ежедневно должно получать не менее 60 ед. питательного вещества А, не менее 50 ед. питательного вещества В и не менее 12 ед. питательного вещества С. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных веществ в одном кг каждого из видов корма приведено в следующей таблице.

Таблица 3

Питательные вещества	Количество ед. питательных веществ в 1 кг корма
	1 вида	2 вида	3 вида
А	1	3	4
В	2	4	2
С	1	4	3

Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1 кг корма одного вида составляет 9 денежных единиц, корма 2 вида – 12 денежных единиц и корма 3 вида – 10 денежных единиц. Составить математическую модель.

Решить задачу самостоятельно.

Ответ:   f = 9x₁+12x₂+4x₃→ min;

 

                                                                                                                        

Общая формулировка ЗЛП. Основные определения.

Определение. Общей ЗЛП называется задача, которая состоит в определении максимального или минимального значения функции

f= c_jx_j → max(min)                               (1)

при условиях

	(2)
	(3)

где a_{i j}, b_i, c_j - заданные постоянные величины и k≤ m.

Определение. Стандартной или симметричной ЗЛП называется задача, которая состоит в определении максимального (минимального) значения функции

f= с_jx_j → min (max)                                      (4)

 при условиях

	(5)
	(6)

  Определение. Основной или канонической ЗЛП называется задача, которая состоит в определении минимального значения функции

 

                     f = c₁x₁+c₂x₂+…..c_nx_n → min                                     (7)

и условиях

	(8)
	(9)

Определение. Функция (1), экстремум которой ищется, называется целевой функцией или функцией цели ЗЛП. Системы неравенств (2), или уравнений (3) называются системами ограничения ЗЛП.

Определение. Совокупность чисел х = (х₁, х₂, ….х_n), удовлетворяющей системе ограничений (2), (3), называется допустимым решением или планом ЗЛП.

Определение. Совокупность всевозможных допустимых решений ЗЛП называется областью допустимых решений ЗЛП.

Определение. Допустимое решение задачи, при котором целевая функция принимает свое максимальное (минимальное) значение называется оптимальным решением или оптимальным планом ЗЛП.

Указанные выше 3 формы записи ЗЛП эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть переписана в форме другой задачи. Это означает, что если имеется способ нахождения решений одной из указанных задач, то тем самым может быть определен оптимальный план любой из 3 задач.

 Чтобы перейти от одной формы записи ЗЛП к другой, нужно в общем случае уметь, во-первых, сводить задачу максимизации функции к задаче минимизации, во-вторых, переходить от ограничений – неравенств к ограничениям – равенствам и наоборот, в-третьих, заменять переменные, которые не подчинены условию неотрицательности.

В том случае, когда требуется найти максимум функции  

f = c₁x₁+с₂x₂+…+с_nx_n → max,                                                (19)

можно перейти к нахождению минимума функции

f = -f = - c₁x₁-c₂x₂-…..-c_nx_n → min                                      (20)

при этом

                   max(f)= - min (-f).                                            (21)

Ограничения неравенства, имеющий вид «≤ », можно преобразовать в ограничения-равенства добавлением к левой части дополнительной неотрицательной переменной. А ограничения-неравенства вида «≥ » - в ограничение-равенство вычитанием из левой части дополнительной неотрицательной переменной. Эти дополнительные переменные называют балансовыми, и в конкретных задачах они имеют вполне определённый экономический смысл. Таким образом, ограничение-неравенство

a₁₁x₁+a₁₂x₂+…..­+a_1nx_n ≤ b₁                                  

преобразуется в ограничение-равенство

a₁₁x₁+a₁₂x₂+…..­+a_1nx_n+x_n+1 =b₁, x_n+1≥ 0,                         

а ограничение-неравенство

a₁₁x₁+a₁₂x₂+…..­+a_1nx_n+x_n+1 ≥ b₁-                        

в ограничение-равенство

a₁₁x₁+a₁₂x₂+…..­+a_1nx_n-x_n+1 =b₁, x_n+1≥ 0.

Пример. Преобразовать постановку данной задачи в каноническую:

f=-2x₁+x₂+5x₃→ max;

   

       

Решить пример самостоятельно.

Ответ:

f=2x₁-x₂-5x₃→ min;

   

       

Для того, чтобы записать ограничения-равенства в виде ограничений-неравенств, необходимы сведения из линейной алгебры. Рассмотрим конкретный пример. Преобразовать постановку данной задачи в симметричную.

f=9x₁+3x₂-5x₃+5x₄→ max;

   

       

 

ОСНОВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗЛП

Постановка ТЗ.

В главе 1 была дана постановка ТЗ по критерию стоимости, для
двух поставщиков и трех потребителей. Обобщая эту задачу на m
поставщиков и п потребителей, получим следующую математическую
постановку ТЗ:   

ТЗ представляет собой задачу линейного программирования с числом переменных m*n и числом ограничений равенств m + n. Усло­вие (23) гарантирует полный вывоз груза из всех пунктов отправле­ния, а условие (24) означает полное удовлетворение спроса.

Если

то ТЗ называется задачей с правильным балансом или закрытой задачей, в противном случае ТЗ называется задачей с неправильным ба­лансом или открытой задачей.

Равенство (26) является необходимым и достаточным условием совместности системы уравнений (24), (25) в области допустимых решений и, следовательно, разрешимости задачи.

Рассмотрим закрытую ТЗ. Эта задача может быть решена симп­лекс-методом, как любая ЗЛП. Однако, специфичная форма системы ограничений данной задачи позволяет существенно упростить обычный симплекс-метод и разработать более эффективные вычислительные методы. Модификация симплекс-метода применительно к ТЗ называется распределительным методом.

Некоторые определения и теоремы:

Определение. Набор переменных {x_ij}, удовлетворяющих условиям (23) - (25), записывается в виде матрицы:

Матрица называется планом перевозок, а переменные х_ij - перевозками.

Определение. Всякое неотрицательное базисное решение системы линейных уравнений (23), (24), определяемое матрицей , называет­ся опорным планом ТЗ.

Определение. Опорный план , при котором функция (22) при­нимает свое минимальное значение, называется оптимальным опорным планом или просто оптимальным планом ТЗ.

Определение. Матрица, составленная из стоимостей на перевоз­ку единицы груза от i-го поставщика к j-му потребителю, называет­ся матрицей стоимостей (матрицей коэффициентов затрат, матрицей тарифов, матрицей транспортных издержек).

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

Подобно тому, как это было в симплекс-методе, в распредели­тельном методе решение ТЗ состоит из следующих основных этапов:

- определение исходного допустимого базисного решения задачи
(первоначального распределения поставок, первоначального опорного
плана);

- оценка этого плана по критерию стоимости:

- переход к следующему, " лучшему" плану путем замены одной
из базисных переменных на свободную.

-

РАЗДЕЛ 3. КОНТРОЛЬНЫЕ ЗАДАНИЯ

Задание 1

1-20. Дана система линейных алгебраических уравнений.

1) Исследовать её на совместность.

2) Решить:

а) по правилу Крамера;

б) методом Гаусса;

в) матричным способом.

1.	2.
3.	4.
5.	6.
7.	8.
9.	10.
11.	12.
13.	14.
15.	16.
17.	18.
19.	20.

Задание 2

21-40. Исследовать систему на совместность (проверить выполнение теоремы Кронекера-Капелли) и найти все возможные базисные решения. Выбрать допустимые.

21.	22.
23.	24.
25.	26.
27.	28.
29.	30.
31.	32.
33.	34.
35.	36.
37.	38.
39.	40.

Задание 2

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

 

Задание 4

41-60. Решить графически задачу линейного программирования: найти наибольшее и наименьшее значения линейной функции. f=c₁x₁+c₂x₂ при соответствующих ограничениях на переменные x₁ и x₂.

 

41. f=x1+x2;	42. f=2x1+3x2;
43. f=6x1+x2;	44. f=x1+9x2;
45. f=x1+7x2;	46. f=7x1+x2;
47. f=x1+8x2;	48. f=x1+3x2;
49. f=3x1+x2;	50. f=8x1+5x2;
51. f=3x1+4x2;	52. f=7x1+2x2;
53. f=9x1+2x2;	54. f=x1+5x2;
55. f=5x1+7x2;	56. f=5x1+3x2;
57. f=3x1+2x2;	58. f=9x1+2x2;
59. f=5x1+3x2;	60. f=4x1+3x2;

Задание 5

Придумать ЗЛП, реализующую следующие частные случаи:

а) оптимального решения нет (f_max → ~, f_min → ~);

б) оптимальных решений бесчисленное множество (альтернативные решения).

Решить их.

Задание 6

61-70. Для изготовления изделий А и В используются три вида сырья. На производство единицы изделия А требуется затратить сырья первого вида а₁ кг, сырья второго вида – а₂ кг, сырья третьего вида – а₃ кг. На производство единицы изделия В требуется затратить сырья первого вида b₁ кг, сырья второго вида – b₂ кг, сырья третьего вида – b₃ кг.

Производство обеспечено сырьём первого вида в количестве p₁ кг, сырьём второго вида – в количестве p₂ кг, сырьём третьего вида – в количестве p₃ кг.

Прибыль от реализации единицы готового изделия A составляет a у.е., а изделия B - b у.е.

Составить план производства изделий A и B, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом.

61.	a1=16, a2=8, a3=5,	b1=4, b2=7, b3=9,	p1=784, p2=552, p3=567,	a=4, b=6.
62.	a1=12, a2=10, a3=3,	b1=3, b2=5, b3=6,	p1=684, p2=590, p3=558,	a=6, b=2.
63.	a1=8, a2=7, a3=4,	b1=3, b2=6, b3=9,	p1=864, p2=864, p3=945,	a=2, b=3.
64.	a1=11, a2=8, a3=5,	b1=3, b2=4, b3=3,	p1=671, p2=588, p3=423,	a=5, b=2.
65.	a1=15, a2=11, a3=9,	b1=4, b2=5, b3=10,	p1=1095, p2=865, p3=1080,	a=3, b=2.
66.	a1=9, a2=7, a3=4,	b1=5, b2=8, b3=16,	p1=1431, p2=1224, p3=1328,	a=3, b=2.
67.	a1=6, a2=5, a3=3,	b1=3, b2=10, b3=12,	p1=714, p2=910, p3=948,	a=3, b=9.
68.	a1=9, a2=6, a3=3,	b1=4, b2=7, b3=8,	p1=801, p2=807, p3=768,	a=3, b=2.
69.	a1=3, a2=4, a3=3,	b1=5, b2=8, b3=11,	p1=453, p2=616 p3=627,	a=2, b=3.
70.	a1=10, a2=5, a3=4,	b1=9, b2=11, b3=15,	p1=1870, p2=1455, p3=1815,	a=7, b=9.

 71-80. Для производства двух видов изделий A и B используются три типа технологического оборудования. На производство единицы изделия A оборудование первого типа используется a₁ ч, оборудование второго типа – a₂ ч, а оборудование третьего типа – a₃ ч. На производство единицы изделия B оборудование первого типа используется b₁ ч, оборудование второго типа – b₂ ч, а оборудование третьего типа – b₃ ч.

На изготовление всех изделий администрация предприятия может предоставить оборудование первого типа не более чем на t₁ ч, оборудование второго типа – не более чем на t₂ ч, оборудование третьего типа – не более чем на t₃ ч. Прибыль от реализации единицы готового изделия A составляет a у.е., а изделия B – b у.е.

Составить план производства изделий A и B, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом.

71.	a1=5, a2=3, a3=2,	b1=2, b2=3, b3=3,	t1=505, t2=393, t3=348,	a=7, b=4.
72.	a1=7, a2=6, a3=1,	b1=3, b2=3, b3=2,	t1=1365, t2=1245, t3=650,	a=6, b=5.
73.	a1=6, a2=4, a3=3,	b1=2, b2=3, b3=4,	t1=600, t2=520, t3=600,	a=6, b=3.
74.	a1=5, a2=4, a3=3,	b1=3, b2=3, b3=4,	t1=750, t2=630, t3=700,	a=5, b=6.
75.	a1=8, a2=6, a3=3,	b1=2, b2=3, b3=2,	t1=840, t2=870, t3=560,	a=6, b=2.
76.	a1=3, a2=3, a3=2,	b1=2, b2=3, b3=5,	t1=273, t2=300, t3=380,	a=4, b=5.
77.	a1=2, a2=3, a3=3,	b1=1, b2=6, b3=7,	t1=438, t2=747, t3=812,	a=7, b=5.
78.	a1=4, a2=3, a3=2,	b1=3, b2=4, b3=6,	t1=480, t2=444, t3=546,	a=2, b=4.
79.	a1=4, a2=3, a3=3,	b1=3, b2=4, b3=5,	t1=440, t2=393, t3=450,	a=6, b=5.
80.	a1=2, a2=3, a3=2,	b1=3, b2=6, b3=8,	t1=428, t2=672, t3=672,	a=3, b=8.

Задание 7

Поставить задачу, двойственную задаче задания 6. Решить исходную задачу графическим способом. Построить решение двойственной задачи, используя теоремы двойственности. Решить двойственную задачу симплекс-методом. Сравнить результаты.

Задание 8

Решить симплекс-методом задачи, придуманные в пунктах а) и б) задания 5.

Задание 9

81-100. Имеются три пункта поставки одного груза: А₁, А₂, А₃ и пять пунктов B₁, B₂, B₃, B₄, B₅, потребления этого груза. На пунктах: А₁, А₂ и А₃ находится груз соответственно в количестве а₁, а₂ и а₃ т. В пункты B₁, B₂, B₃, B₄ и B₅ требуется доставить соответственно b₁, b₂, b₃, b₄ и b₅ т груза. Расстояние между пунктами доставки и пунктами потребления приведено в следующей матрице-таблице:

 

Пункты поставки

Пункты потребления