Тема 5. Використання excel для розв’язання задач лінійного програмування

Задачі лінійного програмування можна розв’язувати за допомогою програми Solver, яка входить у надбудови EXCEL пакета Microsoft Office.

Але спочатку треба впевнитись у тому, що ця програма завантажена: меню Tools (Сервис) à Add-Ins (Надстройки)… à діалогове вікно Add-Ins (Надстройки), встановити флажок V Solver Add-in, OK à Програма Solver завантажується. Якщо завантаження не виконується, то це означає, що треба виконати з CD ROM більш повне завантаження EXCEL.

Перед пуском програми Solver, початкові дані повинні бути оформлені у вигляді таблиці EXCEL. Її оформлення відрізняється від задачі ЛП, бо спочатку у окремій таблиці EXCEL визначаються суми, і лише потім окремо вказуються потрібні обмеження для цих сум.

ПРИКЛАД. Розглянемо задачу ЛП у стандартній формі: отримати максимальний виторг від виробництва Товару 1 і Товару 2. При вказаних у табл. 5.1 даних отримуємо математичну модель.

Цю математичну модель ми повинні оформити у вигляді таблиці 2 на робочому аркуші EXCEL,

F à 10 X₁ + 15 X₂ à max; (5.1)

0,5 X₁ + 0,3 X₂ 30; (5.2)

0,4 X₁ + 0,8 X₂ 50; (5.3)

Таблиця 5.1. Дані задачі ЛП.

Матеріал	Ресурс	Норма витрат, кг/шт.
Товар 1	Товар 2
Мідь	30 кг	0,5 кг/шт.	0,3 кг/шт.
Деревина	50 кг	0,4 кг/шт.	0,8 кг/шт.
Кількість,шт.	-	Х1	Х2
Вартість, грн	-

 

Якщо у EXCEL завантажена програма Solver, то на базі моделі (5.1) – (5.3) у наведених нижче рівняннях (5.4)-(5.7) ми спочатку визначаємо суми відповідних виразів (зліва у цих рівнянь вказані адреси комірок, у які вводяться відповідні формули; обмеження у вигляді “F à max”, “ 30”, ” 50” спочатку не враховуються):

$C$7=F=$C$4 + $C$5=10 X1 + 15 X2; (5.4)

$D$7=$D$4 + $D$5=0,5 X1 + 0,3 x2; (5.5)

$E$7=$E$4 + $E$5=0,4 X1 + 0,8 X2; (5.6)

$B$7=$B$4 + $B$5=X1 + X2. (5.7)

Формули (5.4)-(5.7) ми вносимо у відповідні комірки (див. табл.5.2).

 

Таблиця 5.2. Дані задачі ЛП у робочому аркуші EXCEL

	А	В	С	D	E
	Рішення задачі лінійного програмування
	НАЗВА	КІЛЬКІСТЬ	ВИТОРГ	МІДЬ	ДЕРЕВИНА
	Товар 1	=X1	=10*$B$4	=0,5*$B$4	=0,4*$B$4
	Товар 2	=X2	=15*$B$5	=0,3*$B$5	=0,8*$B$5
	Підсумок	=$B$4+$B$5	=$C$4+$C$5	=$D$4+$D$5	=$E$4+$E$5

 

Але у дійсності у комірки $B$4 та $B$5 табл. 5.2 ми повинні внести не “=X1” та “=X2”(як це показано на них), а відповідно “=0” та “=0” (це означає, що початкові значення змінних “X1=0” та “X2=0”, а потім програма Solver надасть їм оптимальні величини; значення “=X1” та “=X2” введені у комірки $B$4 та $B$5 навмісно - з метою інформації, де будуть виводитись рішення системи Solver щодо оптимальної величини цих змінних). Після заповнення комірок табл. 5.2 формулами, всі комірки вказують нульові значення (це тому, що X1 = 0 та X2 = 0).

Далі переходимо до введення обмежень на отримані суми у табл. 5.2: виділити отриману таблицю на робочому аркуші EXCEL à Меню Tools à Solver… à ДВ Solver Parameters. У ДВ Solver Parameters виконати такі дії:

■ у вікні Set Target Cell ввести адресу функції мети ($C$7);

■ серед перемикачів “Equal To:” вибрати перемикач Max;

■ у вікні By Changing Cells вказати, у яких комірках треба щоб програма змінювала значення для отримання оптимального результату; з цією метою введіть курсор у це вікно і на робочому аркуші виділіть комірки $B$4, $B$5, щоб вони автоматично вписались у це вікно як $B$4:$B$5;

■ при натисненні кн. Guess виділяється діапазон комірок, на які є посилання у функції мети; кн. Change, Delete змінюють або вилучають введені обмеження;

■ у вікні Subject to the Constraints треба ввести потрібні обмеження задачі ЛП: для цього 1ЛКМ на кн. Add à

■ ДВ Add Constraint (Додати обмеження), у полі Cell Reference ввести адресу комірки, у якій зберігається сума функції мети ($C$7), у полі Constraint ввести MAX (в результаті ми повинні отримати у цьому ДВ вигляд “$C$7 à MAX”. Кн. Add. à

■ У попередньому ДВ Solver Parameters з’явиться таке ж обмеження “$C$7 à MAX”;

Далі ДВ Add Constraint залишається відкритим, і ми повинні ввести у ньому наступне обмеження: у полі Cell Reference зробити посилання на комірки $B$4, $B$5 і вибрати операцію INT (ціле число), кн. Add à

У ДВ Solver Parameters з’являться обмеження “$B$4: $B$5 = INTEGER”.

Таким же чином за допомогою ДВ Add Constraint ми задаємо обмеження $D$7 <= 30; $E$7 <=50.

Для збереження заданих параметрів у ДВ, треба зберегти книгу EXEL.

Для ініціалізації розрахунків виконати такі дії: виділити отриману таблицю на робочому аркуші EXCEL à Меню Tools à Solver… à ДВ Solver Parameters, кн. Solve à у табл. 5.3 з’являються результати розрахунків з повідомленням про виконання роботи. На цьому розрахунки завершуються.

Якщо потрібно внести у табл. 5.2 нові розрахунки для нових даних, то виконують такі дії: виділити отриману таблицю на робочому аркуші EXCEL à Меню Tools à Solver… à ДВ Solver Parameters, кн. Options… à ДВ Solver Options, встановити опцію Keep Solver Solution. В результаті таблиця буде оновлена, але початкові значення зберігаються і їх можна відновити (але при встановленні опції Restore Original Value і відсутності завдання на складання звіту, попередні дані будуть вилучені).

В результаті розрахунків ми отримали інформацію про початкові і розраховані значення параметрів; зберігаються також всі попередні розрахунки.

Рішення Solver можна зберегти як сценарій: виділити отриману таблицю на робочому аркуші EXCEL à Меню Tools à Solver… à ДВ Solver Parameters, кн. Options…à ДВ Solver Options:

Кн. Save Model – зберігається сукупність параметрів та обмежень сумісно з робочим листом: відкривається ДВ Save Model, у якому вказують область адрес моделі. Модель зберігається у вертикальному інтервалі комірок, який починається з виділеної комірки.

Кн. Load Model завантажує модель.

 

 

ПИТАННЯ ДЛЯ КОНТРОЛЮ ЗНАНЬ:

1. Який план називається допустимим?

2. Що таке базисний розв’язок? Що таке базисні та вільні члени?

3. У якій формі має бути записана задача лінійного програмування, щоб скористатися симплексним методом для рішення цілочисельних задач?

4. Схема запису вихідної задачі симплексних перетворень.

5. Як вибирають провідний рядок, стовпець, елемент, якщо за одиничного базису всі вільні члени додатні?

6. Як вибирають провідний рядок, стовпець, елемент, якщо за одиничного базису серед вільних членів є від’ємні величини?

7. Як пересвідчитися, чи досягнутий план можна поліпшити, чи він є оптимальним?

8. Як визначаються поняття цілої та дробової частини нецілого числа?

9. Що таке правильне відтинання в задачі цілочисельного програмування?

10. Основні засади методу Гоморі розв’язання задач цілочисельного програмування.

11. Яка задача математичного програмування називається цілочисельною?

12. Чим задача цілочисельного програмування відрізняється ві від задачі лінійного програмування і нелінійного?

13. Наведіть приклади задач, які можуть бути розв’язані як цілочисельні.

14. Як геометрично можна інтерпретувати розв’язок задачі лінійного цілочисельного програмування?

15. Що означає правильне відтинання? Як воно записується?

16. Що таке цілочисельне програмування?

17. Які бувають задачі цілочисельного програмування?

18. Проблеми,які вирішують задачі цілочисельного програмування.

19. Групи методів рішення задач цілочисельного програмування.

20. Які існують варіанти методу Гоморі? Чим вони відрізняються?

21. Сформулюйте підхід рішення цілком цілочисельних задач за 1-им методом Гоморі.

22. Що є ознакою відсутності рішення?

23. Нелінійне програмування. Загальна постановка задачі нелінійного програмування.

24. Нелінійне програмування. Метод множників Лагранжа.

25. Опукле програмування. Необхідні і достатні умови існування сідлової точки.

26. Опукле програмування. Теорема Куна-Танкера.

27. Квадратичне програмування. Необхідні і достітні умови додатньо (від'ємно) визначених квадратичних функцій.

28. За якої умови точка називається сідловою точкою функції Лагранжа?

29. Сформулюйте теорему Куна-Таккера.

30. Яка функція зветься додатно- визначеною, від’ємно-визначеною, невизначеною?

31. Який вигляд має квадратична функція?

32. Сформулюйте необхідні і достатні умови того, щоб квадратична функція була додатно (від'ємно) визначеною?

33.: Сформулюйте теорему про умови, які необхідні, щоб квадратична функція була опуклою (угнутою).

34. В чому суть геометричного розв’язання задач НЛП?

35. Загальна постановка задачі НЛП.

36. Запишіть функцію Лагранжа в загальному вигляді

37. Нелінійне програмування. Загальна постановка задачі нелінійного програмування.

38. Нелінійне програмування. Метод множників Лагранжа.

39. Опукле програмування. Необхідні і достатні умови існування сідлової точки.

40. Опукле програмування. Теорема Куна-Танкера.

41. Квадратичне програмування. Необхідні і достатні умови додатно (від’ємно) визначених квадратичних функцій.

42. Наближені методи розв’язання задач НЛП. Градієнтні методи. Метод Франка - Вульфа.

43. Запишіть задачу нелінійного програмування в загальному вигляді; дайте класифікації таких задач, наведіть змістовні приклади.

44. Що таке допустима множина, цільова функція, її лінії рівня?

45. Що таке глобальний і локальний максимуми (мінімуми) критерію, оптимальне рішення?

46. Сформулюйте необхідні умови оптимальності з використанням функції Лагранжа. У яких випадках вони є і достатніми?

 

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

1.Аллен Рой. Математическая экономия. – М.: Мир, 1964.
2.Бадевиц З. Математическая оптимизация в социалистическом сельском хозяйстве / Пер. с нем. Н.А. Чупеева; под ред. и с предисл. Р.Г. Кравченко.– М.: Колос, 1982.
3.Гасс С. Линейное программирование (методы и приложения). –М.: Госуд. изд-во физ. – мат. лит-ры, 1961.
4.Гатаулин А.М. Издержки производства сельскохозяйственной продукции (методология измерения и пути снижения). – М.:Экономика, 1983.
5.Гатаулін А.М., Гаврилов Г.В., Харитонова Л.А. Економіко – матиматичні методи в плануванні сільськогосподарського виробництва. – К.: Вища шк., 1989.
6.Гатулин А.М., Гаврилов Г.В., Харитонова Л.А. Экономико –математические методы в планировании сельскохозяйственного производства. – М.: Агропромиздат,1986.
7.Гранберг А.Г. Математические модели социалистической економики. – М.: Экономика, 1978.
8.Данциг Дж. Линейное программирование, его обобщение и применение. – М.: Прогресс, 1966.
9.Канторович Л.Г., Горстко А.Б. Оптимальные решения в економике. – М.:Наука, 1972.
10.Лотов А.В. Введение в экономико – математическое моделирование. – М.: Наука, 1984.
11.Кузнецов Ю.Н., Кузнецов В.И., Волощенко А.Б. Математическое программирование. – М.: Высш. шк., 1976.
12.Математическое моделирование экономических процессов в сельском хозяйстве / А.М Гатаулин., Г.В.Гаврилов, Т.М.Сорокина и др., под ред. А.М. Гатаулина. -–- М.: Агропромиздат,1990.
13.Моделирование народнохозяйственных процессов: Учеб. пособие / Под ред. И.В. Котова, 2-е изд., испр. и допол. – Ленинград: Изд. Ленингр. ун-та, 1990.
14.Немчинов В.С. Экономико – математические методы и модели. –М.: Наука, 1967.
15.Новожилов В.В. Проблемы измерения затрат и результатов при оптимальном планировании. – М.: Экономика, 1967.
16.Пастернак П.П. Системное моделирование экономических процессов в АПК. – М.: Агропромиздат,1985.
17. Практикум по математическому моделированию экономических процессов в сельском хозяйстве / Под ред. А.Ф. Карпенко. – М.:Агропромиздат, 1985.
18.Степанюк В.В. Методи математичного програмування. – К.: Вища шк., 1984.
19.Тунеев М.М., Сухачов В.Ф. Экономико – математические методы в организации и планировании сельскохозяйственного производства. – М.: Колос, 1986.

Додаткова література

1.Браверман Э.И., Левин М.И. Неравновесные модели экономических систем. – М.: Наука, 1981. – 304 с.
2.Вагнер Г. Основы исследования операций. Том 2 и 3. – М.:Мир.1973.
3.Вагнер Г. Основы исследования операций. - Том 1. – М.:Мир,1972.–335с.
4.Ермаков С.М., Жиглявский А.А. Математическая теория оптимального експеримента. – М.: Наука, 1987. – 320 с.
5.3айченко Ю.П. Исследование операций. – Киев: Высш.шк., 1988–552 с.
6.Зайченко Ю.П. Исследование операций: Нечеткая оптимизация. – К: Вища шк., 1991. – 191 с.
7.Исследование операций. – М.: Мир, 1981. Т. 1. – 712 с., Т. 2. –677с.
8.Казаков Е.И., Гладков Д.И. Методы оптимизации стохастических систем – М.: Наука, 1987. – 304 с.
9.Мирзоахмедов Ф.М. Математические модели и методы управления производством с учетом случайных факторов. – К.: Наукова думка, 1991. – 224 с.
10.Нейлор Т. Машинные имитационные эксперименты с моделями экономических систем. – М.: Мир,1975. – 500 с.
11.Сытник В.Ф. Основы машинной имитации производственных и организационно – экономических
систем. – К.: УМК ВО, 1988. – 188 с.
12.Федото А.М. некорректные задачи со случайными ошибками в данных. - Новосибирск: Наука. – 1989. – 280 с.
13.Хедли Дж. Нелинейное и динамическое программирование. – М.: Мир, 1967. – 506 с.
14.Юдин Д.Б.. Математические методы управления в условиях не полной информации. – М.: Сов. радно, 1974. –400с.