Файл: информационные технологии.doc

Задачи линейного программирования (ЛП) являются математическими моделями многих практических задач, возникающих в экономике, планировании, управлении и других областях. Кроме того, в ряде случаев решение задачи линейного программирования является этапом решения более сложной задачи оптимизации (например, задачи целочисленного линейного программирования) [1,3,6,7].

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

Общая постановка задачи ЛП:

где под знаком “#” понимается любой из знаков “≤”, “≥” и “=”, причем в одной задаче ЛП могут встречаться знаки всех трех типов.

Классическим примером содержательной задачи, математической моделью

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

Для решения задач ЛП малой и средней размерности (десятки и сотни переменных) используются стандартные программные продукты. Для решения задач ЛП большой размерности (тысячи переменных) требуется разработка специального программного обеспечения.

Далее рассмотрим решение задач ЛП в пакетах MathCAD [5] и MS Excel [4] на примере задачи с двумя переменными, которые, без ограничения общности, будем обозначать x и y.

Решение задачи линейного программирования в Microsoft Excel. Рассмотрим решение задачи ЛП

Требуется найти максимум целевой функции

f (x) = 4x + 2y  max,

2x + 3y ≤ 18,

-x + 3y ≤ 9,

2x - y ≤ 10,

x  0, y  0.

Сначала выделим ячейки под значения под значения переменных x и y, например, ячейки С3 и С4. Далее в ячейку С6 введем целевую функцию

= 4*С3 + 2*С4.

В ячейки В9 : В11 введем левые части ограничений

= 2*C3 + 3*C4,

= - 1*C3 + 3*C4,

= 2*C3 - 1*C4,

а в ячейки С9 : С11 – правые части ограничений (см. рис.2).

Рис. 2. Диапазоны, отведенные под переменные, целевую функцию и ограничения.

После этого выберем в главном меню команду Сервис, Поиск решения. Если в меню Сервис этого пункта нет, нужно установить надстройку. Для этого выберем в меню Сервис пункт Надстройки. В диалоговом окне "Надстройки" нужно найти в списке надстроек "Поиск решения" и установить слева от него флажок. Загрузится Решатель. В дальнейшем при запуске Ехсеl Решатель будет загружаться автоматически, пока не будет снят флажок в окне "Надстройки".

Заполним открывшееся диалоговое окно Поиск решения, как показано на рис. 3.

Рис. 3. Диалоговое окно Поиск решений.

После нажатия на кнопку Выполнить открывается окно Результаты поиска решения, которое сообщает, что решение найдено (рис. 4).

Рис.4. Диалоговое окно Результаты поиска решения.

Оптимальное решение находится в ячейках C3 и C4, а оптимальное значение целевой функции – в ячейке C6 (рис. 5).

Рис.5. Результаты решения.

Задачи ЛП в общем случае решаются аналогично в обоих пакетах.

Варианты заданий. Решить задачи ЛП в MS Excel.

1) 3x₁ + 4x₂ → max

6x₁ + 11x₂ ≤ 50

12x₁ + 6x₂ ≤ 54

6x₁ − 3x₂ ≥ 15

28x₁ + 56x₂ ≥ 112

x₁, x₂≥ 0.

2) 8x₁ + 2x₂ → max

22x₁ + 7x₂ ≤ 77

4x₁ + 9x₂ ≥ 18

15x₁ + 10x₂ ≤ 60

4x₁ + 8x₂≤ 16

x₁, x₂≥ 0.

3) 15x₁ +13x₂ → max

12x₁ + 6x₂ ≤ 32

8x₁ ≤ 9

6x₁ +14x₂ ≤ 39

4x₁ +15x₂ ≤ 18

x₁, x₂≥ 0.

4) 12x₁ + 4x₂ → max

11x₁ + 5x₂ ≤ 31

7x₁ ≤ 7

2x₁ −16x₂ ≥ 6

9x₁ + 3x₂ ≤ 38

x₁, x₂≥ 0.

5) 7x₁ + 6x₂ → max

16x₁ − 2x₂ ≤ 18

8x₁ + 4x₂ ≤ 20

13x₁ + 3x₂ ≤ 4

x₁, x₂≥ 0.

6) 7x₁ + 5x₂ → max

4x₁ + 4x₂ ≤ 26

3x₁ − 16x₂ ≥ −18

14x₁ − 2x₂ ≤ 10

18x₁ + 16x₂ ≤ 8

x₁, x₂≥ 0.

x₁ + 3x₂ → max

−3x₁ + 16x₂ ≤ 32

5x₁ + 6x₂ ≤ 17

14x₁ + 5x₂ ≤ 30

4x₁ + 4x₂ ≤ 5

x₁, x₂≥ 0.

8) −2x₁ → max

5x₁ + 5x₂ ≤ 39

−2x₁ + 14x₂ ≤ 5

2x₁ − 12x₂ ≥ 6

−x₁ + 10x₂ ≤ 6

x₁, x₂≥ 0.

4x₁ + 7x₂ → max

5x₁ + 15x₂ ≤ 16

2x₁ + 3x₂ ≥ −1

− x₁ + 14x₂ ≤ 7

− x₁ + 4x₂ ≥ 1

x₁, x₂≥ 0.

9x₁ + 2x₂ → max

11x₁ +2x₂ ≤ 42

−2x₁ + 8x₂ ≤ 19

14x₁+ 6x₂ ≤ 38

13x₁+ 2x₂ ≤ 26

x₁, x₂≥ 0.

11) 3x₁ + 5x₂ → max

15x₁ + 10x₂ ≤ 60

2x₁ − 3x₂ ≥ 1

28x₁ + 56x₂ ≥ 112

10x₁ + 15x₂≤ 45

x₁, x₂≥ 0.

12) 2x₁ + 11x₂ → max

16x₁ + x₂ ≤ 19

13x₁ + 20x₂ ≤ 14

10x₁ + 6x₂ ≤ 13

6x₁ − 3x₂ ≤ 6

x₁, x₂≥ 0.

13) 13x₁ + 8x₂ → max

9x₁+ 3x₂ ≤ 28

9x₁ + 8x₂ ≤ 35

x₁ + 8x₂ ≤ 40

2x₁ + 7x₂ ≤ 20

x₁, x₂≥ 0.

14) 5x₁ + 9x₂ → max

8x₁ − 5x₂≤ −3

−3x₁ + 12x₂ ≤ 42

2x₁ + x₂ ≤ 44

5x₂ ≤ 11

x₁, x₂≥ 0.

15) x₁ + 6x₂ → max

14x₁ + 21x₂ ≤ 28

20x₁ + 35x₂ ≤ 70

12x₁ − 9x₂ ≥ 12

21x₁ + 15x₂ ≤ 75

x₁, x₂≥ 0.

16) 2x₁ + 3x₂ → max

8x₁ + 9x₂ ≤ 36

10x₁ +14x₂ ≥ 12

4x₁ + 8x₂ ≤ 16

6x₁ − 3x₂ ≤ 9

x₁, x₂≥ 0.

17) 2x₁ + x₂ → max

14x₁ + 10x₂ ≤ 23

2x₁ + 8x₂ ≤ 25

15x₁ + 6x₂ ≤ 32

18x₁ − 5x₂ ≤ 26

x₁, x₂≥ 0.

18) 5x₁ + 6x₂ → max

13x₁ + 5x₂ ≤ 18

3x₁ + x₂ ≤ 4

4x₁+ 8x₂ ≤ 10

2x₁+11x₂ ≥ 6

x₁, x₂≥ 0.

19) 4x₁+ x₂ → max

x₁ + 5x₂ ≤ 6

16x₁ + 4x₂ ≤ 12

10x₁ + x₂ ≤ 6

3x₁ − 3x₂ ≤ 43

x₁, x₂≥ 0.

20) 4x₁ + 5x₂ → max

9x₁ ≤ 15

15x₂≤ 6

−2x₁ + 13x₂ ≤ 31

2x₁ + 3x₂ ≤ 39

x₁, x₂≥ 0.

21) 7x₁ + 2x₂ → min

3x₁ + 12x₂ ≤ 30

10x₁ + 3x₂ ≤ 24

9x₁ − 2x₂ ≥ 12

11x₁ + 24x₂ ≥ 48

x₁, x₂≥ 0.

22) 3x₁ + 2x₂ → min

2x₁ + 7x₂ ≤ 17

4x₁ + x₂ ≥ 8

5x₁ + 10x₂ ≤ 20

3x₁ + 5x₂≤ 15

x₁, x₂≥ 0.

23) 5x₁ + 7x₂ → max

2x₁ + 8x₂ ≤ 24

6x₁ ≤ 9

3x₁ +10x₂ ≤ 30

4x₁ +12x₂ ≤ 35

x₁, x₂≥ 0.

24) 9x₁ + 4x₂ → max

13x₁ + 2x₂ ≤ 22

4x₁ ≤ 7

4x₁ −10x₂ ≥ 5

7x₁ + 13x₂ ≤ 38

x₁, x₂≥ 0.

25) 2x₁ + 6x₂ → max

11x₁ − 4x₂ ≤ 22

6x₁ + 4x₂ ≤ 21

3x₁ + x₂ ≤ 14

x₁, x₂≥ 0.

26) 3x₁ + 2x₂ → max

5x₁ + 4x₂ ≤ 16

3x₁ − 10x₂ ≥ −11

4x₁ − 5x₂ ≤ 10

3x₁ + 10x₂ ≤ 8

x₁, x₂≥ 0.

27) x₁ + 7x₂ → max

−2x₁ + 13x₂ ≤ 26

4x₁ + 9x₂ ≤ 28

12x₁ + 5x₂ ≤ 32

x₁ + 2x₂ ≤ 5

x₁, x₂≥ 0.

28) 3x₁ → max

7x₁ + 5x₂ ≤ 29

−4x₁ + 12x₂ ≤ 5

2x₁ − 9 x₂ ≥ 6

−x₁ + 13x₂ ≤ 7

x₁, x₂≥ 0.

29) 4x₁ + 7x₂ → max

5x₁ + 15x₂ ≤ 16

2x₁ + 3x₂ ≥ −1

− x₁ + 14x₂ ≤ 7

− x₁ + 4x₂ ≥ 1

x₁, x₂≥ 0.

30) 3x₁ + 2x₂ → max

12x₁ +7x₂ ≤ 32

−4x₁ + 8x₂ ≤ 15

12x₁+ 6x₂ ≤ 38

10x₁+ 2x₂ ≤ 26

x₁, x₂≥ 0.

Задание 2. Решение транспортной задачи в пакете MS Excel.

Транспортная задача – это задача о минимизации транспортных расходов, связанных с обеспечением пунктов потребления определенным количеством однородной продукции, производимой в нескольких пунктах производства [1, 3, 7]. В общем виде задача может быть сформулирована следующим образом.

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

Примем следующие обозначения: i – номер пункта производства, j –номер пункта потребления, – количество продукта, имеющееся в i-ом пункте производства, – количество продукта, необходимое для j-го пункта потребления, – стоимость перевозки единицы продукта из i-го пункта производства в j-й пункт потребления, – количество груза, планируемого к перевозке из i-го пункта производства в j-й пункт потребления, i=1,2,…,m; j=1,2,…,n. Математическая модель транспортной задачи будет выглядеть следующим образом:

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

с₁₁ с₁₂… с₁_n

. . .

с_m₁ с_m₂… с_mn

a₁

…

a_m

b₁ b₂… b_n

Рассмотрим решение транспортной задачи в табличном процессоре MS Excel. Так как транспортная задача является частным случаем задачи линейного программирования, то эту задачу можно решать так, как описано выше. Однако благодаря свойствам задачи, ее можно записать в более компактной форме.

Рассмотрим транспортную задачу, матрица планирования которой имеет вид:

B_j A_i	B₁	B₂	B₃	B₄	B₅
A₁	14	25	18	19	23	33
A₂	2	17	16	24	2	25
A₃	29	3	7	15	22	25
A₄	5	20	17	23	10	17
	33	11	11	11	34	b_ja_i

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

Рис.6. Исходные данные транспортной задачи.

В ячейки B2 : F5 введем стоимость перевозок. Ячейки B8 : F11 отведены под значения объемов перевозок, пока неизвестные. В ячейки H8 : H11 введены объемы производства, а в ячейки B13 : F13 - потребности (спрос) в продукции в пунктах потребления.

В ячейку G12 вводится целевая функция

= СУММПРОИЗВ (B2 : F5; B8 : F11) .

В ячейки B12 : F12 вводятся формулы

= СУММ (B8 : B11),

= СУММ (C8 : C11),

= СУММ (D8 : D11),

= СУММ (E8 : E11),

= СУММ (F8 : F11),

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

G8 : G11 введены формулы

= СУММ (B8 : F8),

= СУММ (B9 : F9),

= СУММ (B10 : F10),

= СУММ (B11 : F11),

характеризующие объем продукции, вывозимой из пунктов производства.

Далее выбираем команду Сервис, Поиск решения и заполняем открывшееся диалоговое окно Поиск решения, как показано на рис.7.