Материал: Економетрія - Навчальний посібник ( Лугінін О.Є.)


12.2. рішення задач лпу середовищі excel

На рис. 12.3 зображено загальна схема розміщення даних для рішення задачі ЛП довільного розміру. Викладемо коротко алгоритм дій користувача, який вирішує задачу ЛП.

Створити ЕТ, яка відповідає розміру вирішуваній задачі ЛП.

Оформити таблицю шапкою, заголовками рядків і стовпців у відповідності до рис. 12.3.

Заповнити ЕТ даними:

 

рядок 2 змінними задачі Х1, Х2,..^^ у загальному вигляді (блок клітинок В2:№);

блок В5:1ЧК коефіцієнтами лівих частин обмежень;

рядок  (К+1)   Цільова   фінкція   коефіцієнтами цільової фінкції у блоці клітинок В(К+1):]Ч(К+1);

стовпець N2 Права частина коефіцієнтами правих чстин обмежень у блоці клітинок:^2)К.

Заповнити стовпець Ліва чстина формулами лівих   частин   обмежень,   які   обчислюються спеціальною функцією СУММПРОИЗВ, яка знаходиться у списку Математические Мастера функций. Аргументами функції є масиви змінних (х1, х2,...хп) і коефіцієнти при них (аьа2,...ап). Функція обчислює суму додатків масивів для кожного обмеження у вигляді (а1х1 +а2х2 +.+апхп).

Для автоматизації копіювання формул у стовпці N1 зручно використовувати абсолютні адреси 2-го рядка змінних, які не змінюються у формулах: В$2:Щ2. Значок $ використовується для того, щоб зробити посилання на ці клитинки однозначними, так як в нашому випадку в них знаходяться постійні значення змінних задачі у всіх обчисленнях. Тоді, наприклад, в клітинці (N1)5 ЕТ для лівої частини обмеження 1 записується формула

=СУММПРОИЗВ(В$2:Щ2,В5^5)

Аналогічно записуються формули для інших лівих частин обмежень, які копіюються в клітинки (N1)6: (М)К.

5. Заповнити клитинку Ш(К+1) Цільова функція формулою

=СУММПРОИЗВ(В$2:Щ2),В(К+1)^(К+1))

Відмітити клитинку N^+1) Цільова функція та ініціювати вікно Поиск решения, загальний вигляд якого показаний на рис. 12.4:

Поиск решения

 

Установить селевую

Выполнить

 

Равной:   (• максимальному значению     (~ значению: |п

Закрыть

 

Г" минимальному значению зменяя ячейки:—

 

~5Г

Предположить

 

-Ограничения:

Параметры |

 

Добавить

 

Изменить Удалить

 

Восстановить

 

 

Рисунок 12.4 Вікно Поиск решения

Справка

 

 

Заповнити строку Установить целевую функцію посиланням на клитинку цільової функції N(K+1) та вибрати один з варіантів оптимізації:

 

максимальне значення цільової функції (MAX);

мінімальне значення цільової функції (MIN).

Заповнити строку Изменения ячейки посиланням на блок ET Решение (блок B3:N3).

Заповнити вікно Ограничения лівими, правими частинами та знаками обмежень, для чого треба натиснути кнопку Добавить, відкривши діалогове вікно Добавление ограничения (рис. 12.5), і в цьому вікні для кожного обмеження

 

Добавление ограничения

 

■ ?|x

Ссылка на ячейку:

Ограничение:

 

Ii              U l<=

dl

 

 

 

 

OK Отмена

Добавить 1

Справка |

Рисунок 12.5 Діалогове вікно Добавление ограничения

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

в рядку Знак вибрати знак відношення, який відповідає розглянутому обмеженню (<, >, =);

заповнити стороку Ограничение, встановивши курсор на цей рядок та клацнувши мишею на відповідну клитинку стовпця Права частина обмежень ЕТ;

заповнення строки вікна Добавление ограничений закінчується натиском кнопки ОК, додавши тим самим обмеження до списку обмежень вікна Ограничение.

 

Відкрити діалогове вікно Параметры. Встановити в ньому режим Линейная модель и Неотрицательные значения (для змінних задачі).

Ініціювати рішення задачі, натиснувши кнопку Выполнить.

Якщо рішення задачі існує та знайдене, оптимальне значення цільової функції буде виведене в клітинку

Целевая функция, а оптимальне значення змінних у блок Решение.

За описаною схемою заповнення ЕТ (див. рис. 12.3) можуть бути реалізовані ряд оптимізаційних економіко-математичних задач, які описані у п. 3.1.2: задача оптимального використання ресурсів (оптимального планування); задача про суміші та ін. За аналогією можуть бути реалізовані такі напрями ЛП, як задача цілочисельного ЛП, двійчаста задача ЛП, що викладено в посібнику [23].

Крім того є широко розповсюджена в економічній практиці транспортна задача, яка може бути сформульована як частковий випадок задачі ЛП і вирішена сімплекс-методом. На відміну від запропаноної схеми заповнення ЕТ (див. рис. 12.3) більш зручним та наочним є схема, яка надана на рис. 12.6. Тому коротко опишемо процедуру рішення транспортної задачі з використанням цієї схеми [23].

Транспортна задача Матриця вартості     

 

N1 N1+1

Постача­льники

 

Подпись: N2 N2+1 Подпись: N3 N3+1
N3+2 N3+3
Подпись: Цільова функція
Формула
...         ...         п Споживачі

Рисунок 12.6 Загальна схема заповнення ЕТ транспортної

задачі

Нагадуємо, що сутність транспортної задачі полягає в тому, щоб забезпечити мінімальні транспортні витрати перевезень вантажу від постачальників до споживачів (цільова функція), і при цьому вантаж від постачальників має бути вивезеним (обмеження на спроможність постачальників), а потреби споживачів задовільнені (обмеження на потреби споживачів).

Рішення транспортної задачі на ПК проводиться за таким алгоритмом.

Оформити шапку та заголовки рядків і стовпців, як це показано на рис. 12.6.

Заповнити ЕТ: блоки Запаси (Ь2^2:(Ь2)Ю та Споживання В(Ю+2):Ь(Ю+2); Матриця вартості В3:ЦШ+1).

В клітинку Ь3(Ю+3) за допомогою Мастера функций записати формулу цільової функції

=СУММПРОИЗВ(В3:Ь(Ш+1), В(Ш):ЦГО))

для чого:

натиснувши на кнопку /х панелі інструментів Стандартная, ініціювати Мастер функций;

вибрати функцію Математическая/СУММПРОИЗВ;

встановити курсор у полі Матриця вартості, відмітити блок В3:Ь(М+1) та зафіксувати перший аргумент функції;

встановити курсор у полі Матриця рішення, відмітити блоки В^2):Ь(Ю) та зафіксувати другий аргумент функції;

закінчити запис формули, клацнувши ОК.

В клітинах блоків ІЛ(Ш):ІЛ(Ю) та В(Ю+1):Ь(Ю+1) записуються формули сумування змінних відповідно за запасами постачальників та потребою споживачів.

5.         Зв'язати ЕТ з вікном Поиск решения, для чого:

відмітити клитинку Ь3(Ю+3) (Цільова функція), відкрити вікно Поиск решения;

заповнити рядок Установить целевую ячейку;

встановити режим Равной у стан Минимальному значению;

заповнити рядок Изменения ячейки посиланням на блок B(N2):L(N3);

заповнити вікно Ограничения обмеженнями за рядками та стовпцями змінних, що відповідає запасим постачальників та потребам споживачів;

у рядку Знак вибрати знак відношення розглядаємо! транспортної задачі (<, >, =);

заповнення рядків вікна Добавить закінчити натиском кнопки ОК;

натиснувши кнопку Параметры, встановити у вікні Параметры поиска решения режим Линейная модель та Неотрицательные значения; натиснути кнопку ОК.

6.         Ініціювати рішення задачі, натиснувши кнопку

Выполнить.

Слід зауважити, що рішення транспортної задачі відкритого типу можна получити, змінив у списку обмежень відповідні рівняння нерівностями [21].

Розглянемо приклади рішень задач ЛП на ПК у середовищі EXCEL за побудованими економіко-математичними моделями.

 

Приклад 12.1. Задача оптимального використання ресурсів. Необхідно скласти такий план випуску продукції декількох видів, щоб підприємство мало найбільший прибуток від їх реалізації при обмежених запасах ресурсів з використанням такої економіко-математичної моделі:

Z = 8х1 + 12х2 + 10х3 + 9х4 + 8х5 + 6х6 —> тах;

 

10х1

+ 2 х2

+ 3х3

+

3х4

+

4х5 +4хб

< 10,

2х1

+ 3х2

+ 6х3

+

4х4

+

8х5 +2х6

< 12,

5х1

+ 6 х2

+ 3х3

+

2 х4

+

3х^ +

< 20,

3х1

+ 5х2

+ 15х3

+

13х4

+

2х^ +

< 25,

4х1

+ 5х2

+ 12х3

+

10х4

+

5х^ +

< 20,

3х1

+ х2

+ 2х3

+

4х4

+

 

<5,

5х1

+ 8х2

+ 17х3

+

6 х4

+24х5 +4х6

< 40;

х,. > 0 (і = 1...6).

 

Алгоритм дій користувача

1.   Заповнити вхідні дані за формою рис. 12.3:

 

 

А        |В|С|0|Е|Р|Є|      Н І

J

1

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

 

2

 

 

 

 

 

 

 

 

 

 

3

Змінні

х1

х2

хЗ

х4

х5

 

 

 

 

4

Рішення

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

Матриця коефіцієнтів системи обмежень

Ліва частина

Права частина

 

 

Обмеження 1 Обмеження 2 Обмеження 3 Обмеження 4 Обмеження 5 Обмеження 6

10

2

3

3

4

4

 

10 

 

 

2

3

6

4

8

2

 

12 

 

 

5

6

3

2

3

5

 

20 

 

10 

 

3

5

15

13

2

3

 

25 

 

11 

 

4

5

12

10

5

3

 

20 

 

12 

 

3

1

2

4

2

1

 

 

13

Обмеження 7 Цільова функція

5

8

17

6

24

4

 

40 

 

14 

 

8

12

10

9

8

Є

 

МАХ 

 

15 

 

 

 

 

 

 

 

 

 

 

 

2. Для лівої частини обмеження 1 відповідна їй формула має такий вигляд:

=СУММПРОИЗВ(В4:С4, В7:С7)

і"

 

 

' І '

 

а 1-

~=| =

-= из | ^ \% иии ;« ^,5 | '=

 

СУММПРОИЗВ  1 -г X /

| =СУММПРОИЗВ(ВМ:6М;В7:67)

 

 

 

 

в

с

 

Е

 

е

н

1

 

 

1

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

 

2