Методы оптимальных решений (стр. 8 )

21.  Составляем все равенства по задействованным ячейкам. Берем первую ячейку А1М1, в ней цена 2 руб., значит сумма потенциалов данного поставщика и магазина.

а1 + m1 = 2 и т. д.

22.  а1 + m1 = 2; если а1 =0, то → m1 = 2

а2 + m1 = 1; если m1=2, то → а2 = -1

a1+ m3 =3; если а1 = 0, то → m3 = 3

a3+ m3=5; если m3 = 3, то → a3 = 2

a3+ m4 = 8; если а3=2, то → m4 = 6

a4 + m4 = 3; если m4 = 6, то → a4 = -3

a4 + m2 = 1.5; если a4 = -3, то → m2 = 4.5

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

	М1 m1=2	М2 m2=4,5	М3 m3=3	М4 m4=6
А1 а1=0	220	4-0,5	3100 IV	5-1 I
А2 а2=-1	1 80	3-0,5	42	72
А3 а3=2	62	70,5	5130 III	870 II
А4 а4=-3	34	1.550	44	3100

23.  Из незадействованных в перевозках ячеек вычитаем соответствующие им потенциалы. Записываем в матрицу (сверху). Например, из ячейки А1М2 вычитаем соответственно потенциалы a1 и m2. И так далее, из всех незадействованных.

24.  Если в результате есть отрицательные значения, то маршрут неоптимальный. Требуется оптимизация плана перевозок. Если отрицательных много, то выбираем самое максимальное по модулю (самое отрицательное). В нашем случае ячейка А1М4 имеет максимальное по модулю отрицательное значение.

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

26.  Для нахождения такого цикла необходимо проанализировать все возможные варианты. Встать в начальную ячейку и выбрать все направления движения. В нашем случае есть два направления – вниз и влево. Если пойти по прямой вниз до конца, то придем в А4М4, из нее попадаем только в А4М2, а из нее по прямой никуда не сможем шагнуть. Значит возвращаемся в исходную позицию и идем вниз, но только до А3М4. Из нее можно на шаг влево A3M3, оттуда вверх в А1М3 и в исходную. Если цикл найден, то можно дальше не анализировать, он всегда один.

27.  В нашем случае это маршрут по ячейкам A1M4 – A3M4 – A3M3 – A1M3 –A1M4.

	М1 m1=2	М2 m2=4,5	М3 m3=3	М4 m4=6
А1 а1=0	220	4-0,5	330 IV	5-170 I
А2 а2=-1	1 80	3-0,5	42	72
А3 а3=2	62	70,5	5200 III	80 II
А4 а4=-3	34	1.550	44	3100

28.  Пронумеруем ячейки цикла по порядку (римские цифры). Из четных ячеек этого маршрута выбираем ту, где перевезено меньше всего муки. У нас это точка II, А3М4 = 70 кг. Исключаем ее из плана перевозок. Для этого из четных ячеек маршрута вычтем 70 кг, а к нечетным ячейкам прибавим 70. А1М4 делаем задействованной, а А3М4 наоборот освобождаем.

29.  Корректируем стоимость перевозок по изменённым ячейкам. Первый, второй, третий, пятый маршруты остались без изменений. Четвертый изменился, стало 30 кг х 3 руб. = 90 руб. Шестой стал 200 кг х 5 руб. = 1000 руб. Седьмой стал 0 руб. Добавился маршрут A1M4 = 70 кг. х 5 руб. = 350 руб.

30.  Общая стоимость доставки стала: 80+75+40+90+300+1000+350 = 1935 руб. Она снизилась на 70 руб. от первоначального варианта. Значит данный план перевозки более оптимальный.

31.  Снова проверяем его на оптимальность аналогичным образом. Для этого надо найти значения потенциалов и оценок всех незадействованных ячеек. Если среди нет не будет отрицательных – план оптимизирован.

Ищем потенциалы: Снова примем а1=0.

	М1 m1=2	М2 m2=3,5	М3 m3=3	М4 m4=5
А1 а1=0	220	40,5	330	570
А2 а2=-1	1 80	30,5	41	73
А3 а3=2	62	71.5	5200	81
А4 а4=-2	33	1.550	43	3100

32.  a1 =0

а1 + m1 = 2; → m1 = 2

а2 + m1 = 1; → а2 = -1

a1+ m3 =3; → m3 =3

a1+ m4 =5; → m4 =5

a3+ m3=5; → a3 =2

a4 + m4 = 3; → a4 = -2

a4 + m2 = 1.5; → m2 = 3.5

33.  Ищем оценки свободных ячеек: от тарифа в ячейке отнимаем все связанные с ней потенциалы. Отрицательных значений нет. Решение по доставке муки оптимальное. Стоимость доставки 1935 руб.

Задача для самостоятельного решения дома

Имеем четыре склада с досками. Их запасы 10, 15, 24 и 18 шт. соответственно. Имеем четырех покупателей с запросами 12, 22, 19 и 14 соответственно. Тарифы на доставку одной доски от склада к потребителю приведены в таблице.

	Потребители
Склад №	1	2	3	4
1	10	15	21	20
2	8	11	14	12
3	16	20	12	14
4	18	20	22	19

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

Ответ: 908 руб. стоимость оптимального плана перевозок.

9. оптимизация инвестиционного плана

У собственника есть три предприятия, которые приносят ему доход 1, 2 и 1 млн. в год соответственно. Известно, что если он вложит в первое 20 млн., то доходность его станет 5 млн., если во второе – то доходность станет 4 млн., если в третье, то доходность станет 5 млн. Аналогично, если его вложения составят 40 млн., доходности предприятий станут 8, 7, 20 млн. соответственно. Если 60 млн., то 15, 18 и 24 соответственно. И если 80 млн, то 20, 21, 37 млн. соответственно. Как оптимально вложить эти суммы денег с максимальной доходностью?

Составляем матрицу доходности предприятий

	1 предприятие	2 предприятие	3 предприятие
0 млн.	1	2	1
20 млн.	5	4	5
40 млн.	8	7	20
60 млн.	15	18	24
80 млн.	20	21	37

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

1 предприятие 2 предприятие	0	20	40	60	80
1	5	8	15	20
0	2	3	7	10	17	22
20	4	5	9	12	19
40	7	8	12	15
60	18	19	23
80	21	22

В белых клетках – информация из условия. В серых клетках ищем совместную доходность. Если ничего не вкладывать, то доходность 2-х предприятий 3 млн. Ставим в клетку, соответствующую 0/0 доходность 3 млн.

Если будем вкладывать 20 млн, то два варианта: 20 в 1-ое и 0 во 2-ое, тогда доходность 7 млн. Вписываем в соответствующую клетку. Либо 0 в 1-ое и 20 млн. во 2-ое с доходностью 5 млн. Очевидно, что первый вариант прибыльнее. Выделяем его подчеркиванием.

40 млн. можно инвестировать тремя способами (0/40, 20/20 и 40/0 соответственно). Вписываем в таблицу доходность каждого способа. Из таблицы видно, что эффективнее всего вкладывать как 40/0, т. е. 40 млн. в первое предприятие, подчеркиваем максимальную доходность от 40 млнмлн.

Аналогично рассуждаем и для 60 млн. Здесь уже 4 варианта. (60/0, 40/20, 20/40, 0/60). Максимальная доходность 19 млн. достигается вложением 0/60.

Рассматриваем 80 млн. – 5 вариантов. 80/0, 60/20, 40/40, 20/60, 0/80. Максимальная доходность 23 млн. достигается при варианте 20/60.

Выписываем оптимальные варианты инвестирования в первые два предприятия с их доходностью и выбранным планом:

0	20	40	60	80
3	7	10	19	23
0/0	20/0	40/0	0/60	20/60

Составляем новую таблицу, добавляя третье предприятие, сверху берем наш оптимальный план 1 и 2 предприятия

1+2 предприятие 3 предприятие	0	20	40	60	80
3 (0/0)	7 (20/0)	10 (40/0)	19 (0/60)	23 (20/60)
0	2	5	9	12	21	25
20	4	7	11	14	23
40	7	10	14	17
60	18	21	25
80	21	24

Рассуждаем аналогично, выбирая максимальную доходность по каждой инвестируемой сумме и план инвестирования. В 0 один вариант 0/0/0 с доходностью 4 млн. на все три предприятия.

Если рассматривать 20 млн., то два варианта 20/0/0 с доходностью 9 млн. и 0/0/20 с доходностью 7 млн., первый вариант предпочтительнее.

Три варианта для 40 млн.: 40/0/0 с доходом 12 млн., 20/0/20 с доходом 11 млн. и 0/0/40 с доходом 10. Первый оптимальный.

Четыре варианта для 60 млн.: 0/60/0 и 0/0/60 с доходом 21 млн. одинаковые и самые прибыльные.

Пять вариантов для 80 млн., самые выгодные 20/60/0 и 20/0/60 с доходом 25 млн.

Окончательный вариант инвестиционного плана приведем в таблице:

0	20	40	60	80
5	9	12	21	25
0/0	20/0/0	40/0/0	0/60/0 0/0/60	20/60/0 20/0/60

Отсюда можно посчитать и процент прибыли. Вариант – инвестировать 20 млн. с доходностью 9 млн. дает инвестору 9/20= 0,45, т. е. 45% прироста начального капитала.

Для 40 млн. прирост капитала 12/40 = 0,3, т. е. 30%. Для 60 млн. прирост капитала 21/60 = 0,35 или 35%. Для 80 млн. прирост 25/80 = 0,31 или 31%.

Таким образом, самое невыгодное вкладывать 40 млн., самое выгодное вложение 20 млн.

Список литературы

1. Акулич программирование в примерах и задачах. – М.: Высшая школа, 1993.

2. , Бережной методы моделирования экономических систем. – М.: Финансы и статистика, 2001.

3. , Бережной -математические методы и модели в примерах и задачах. – Ставрополь: Интеллект-сервис, 1996.

4. Вентцель операций. – М.: Советское радио, 1972.

5. Кремер операций в экономике. – М.: ЮНИТИ, 1997.

6. Карпелевич линейной алгебры и линейного программирования. – М.: Наука, 1967.

7. Кузнецов программирование. – М.: Высшая школа, 1986.

8. Л Сборник задач по математическому программированию. – М.: Высшая школа, 1975.

9. Введение в исследование операций: В 2 кн. – М.: Мир, 1985.

10. Федосеев -математические методы и прикладные модели. – М.: ЮНИТИ, 1999.

11. Руководство к решению задач с экономическим содержанием по курсу высшей математики / Под ред. и . – М.: ВЗФЭИ, 1989.

Оглавление

Введение. 3

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

2. ОБЩАЯ И ОСНОВНАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 13

3. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 15

4. ЭКОНОМИЧЕСКИЙ ПРИМЕР РЕШЕНИЯ ЗЛП ГРАФИЧЕСКИМ СПОСОБОМ 19

5. ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗЛП С n ПЕРЕМЕННЫМ 21

6. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 23

7. ТАБЛИЧНЫЙ СИМПЛЕКСНЫЙ МЕТОД.. 31

8. ТРАНСПОРТНАЯ ЗАДАЧА.. 37

9. ПОДРОБНЫЕ ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ.. 46

10. ОПТИМИЗАЦИЯ ИНВЕСТИЦИОННОГО ПЛАНА.. 68

Список литературы.. 71