Дослідження операцій (стр. 6 )

і	Базис	С	Х	3	2	5	0	0	0
Р1	Р2	Р3	Р4	Р5	Р6
1	Р2	2	189/2	1/4	1	0	0	0	1/4
2	Р3	5	230	3/2	0	1	0	1/2	0
3	Р4	0	11	-1	0	0	1	-1/2	-1/2
m+1			1339	5	0	0	0	5/2	1/2

Отже, за одну ітерацію отримано новий оптимальний план прямої

Х = (0,189/2,230) та двоїстої λ* = (0,5/2,1/2) задач, при яких Z(Х*) = Т(λ*)=1339.

Приклад: Розв'язання задач лінійного програмування на ПЕОМ.

Розв'язання задач лінійного програмування потребує громіздких обчислень, що зв'язані з обробкою симплекс-таблиць. Цей процес, як правило, займає багато часу й потребує уваги, що не дає зосередитися на змістовній суті задачі. Тут на допомогу може прийти табличний процесор "Місrоsоft Ехсеl", який має спеціальний інструмент - надбудову Поиск решения, що дає можливість розв'язати вельми складні оптимізаційні за­дачі. Але треба зауважити, що використання цього інструменту зв'язане, по-перше, із суттєвими витратами часу на його освоєння, і, по-друге, ПЕОМ видає зразу кінцевий результат, що в деяких випадках може бути небажаним, оскільки студент не має можливо­сті приймати участь у ітеративному процесі розв'язування задачі.

Продемонструємо, як застосовується інструмент Поиск решения на прикладі такої задачі:

Фірма "Латекс" спеціалізується на виробництві меблів за індивідуальними заказами та за каталогами. Вона може виробляти кухні, офісні меблі, шафі-купе для готелів, що потребує різних витрат праці на кожній стадії виробництва. Вихідні дані наведені в таблиці 3.21.

Таблиця 3.21. – Вихідні дані

Виробнича дільниця	Витрати праці, люд.-год.
Кухні	Офісні меблі	Шафи-купе
Лісопильня	1	2	4
Складальний цех	2	4	2
Обробний цех	1	1	2

Протягом тижня можна планувати роботу на лісопильні - на 360 люд.-год, у складальному цеху - на 520 люд.-год. і в обробному цеху - на 220 люд.-год. Прибуток від реалізації однієї одиниці кухні, офісних меблів та шафи-купе складає відповідно 90, 110 і 150 грн. Скласти такий план виробництва, який дає максимальний прибуток.

Позначивши через х1 щотижневе виробництво кухонь, через х2 - офісних меблів, а через х3 - шафів-купе, отримаємо таку математичну модель задачі:

Z = 90х1 + 110х2 + 150х3 - mах,

1х1 + 2х2+4х3 ≤ 360,

2х1 + 4х2+2х3 ≤ 520,

1х1 + 1x2 + 2х3 ≤ 220,

х1 ≥ 0,

х2 ≥ 0,

х3 ≥ 0.

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

Отже, відкривши робочий лист Ехсеl, треба виконати наступні операції:

-  в інтервал комірок А2:А6 введіть найменування цехів та інші показники, які фігу­рують у задачі;

-  в інтервал комірок В1:D1 введіть позначення змінних;

-  в інтервал комірок В2:D4 введіть коефіцієнти при змінних у лівій частині нерівностей;

-  в інтервал комірок F2:F4 введіть праві частини нерівностей;

-  в інтервал комірок В5:D5 введіть коефіцієнти цільової функції;

-  в комірку Е2 введіть формулу

=СУММПРОИЗВ(В2:D2;$В$6:$D$6)

і скопіюйте її в комірки ЕЗ, Е4 та Е5.

Для цього на панелі інструментів "Стандартная" треба клацнути кнопку ƒ (Вставка функций), в результаті чого заявиться діалогове вікно Мастер функиий, в якому серед функцій треба знайти функцію СУММПРОИЗВ. Клацнувши кнопку ОК, дістаємо діалогове вікно для введення функції СУММПРОИЗВ().

В результаті виконання перелічених операцій отримуємо таблицю, наведену на рис. 3.2.

А	В	С	D	Е	F
1. Цех	Х1	Х2	Х3
2. Лісопильний	1	2	4	0	360
3. Складальний	2	4	2	0	520
4. Обробний	1	1	2	0	220
5. Прибуток	90	110	150	0
6. Розв'язок

Рисунок 3.2

Для введення умов задачі треба виконати такі операції:

-  вибрати в меню Сервис команду Поиск решения та клацнути клавішу ОК - відкри­ється діалогове вікно Поиск решения;

-  встановити курсор у вікно введення Установить целевую ячейку, що розташована у верхній частині діалогового вікна:

-  клацнути мишкою у комірці Е5 робочого місця таблиці - у вікну введення Уста­новить целевую ячейку запишіться адреса комірки, в яку буде занесено шукане значення цільової функції;

-  ввести напрям цільової функції Максимальному значенню, клацнувши мишкою на цьому надпису;

-  у вікно введення Измененяя ячейки введіть адресу шуканих змінних В6:D6;

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

Введіть обмеження:

1х1 + 2х2+4х3 ≤ 360,

Для цього у вікну введення Ссылка на ячейку треба ввести $Е$2, розкрити спи­сок у центрі диалогового вікна Добавление ограничения та задати тип нерівності <=, а у вікно введення Ограничение ввести $F$2,

-  натиснути кнопку Добавить, після чого дані, що розміщені у діалоговому вікні Добавление ограничения, будуть розміщені у вікно Ограничения діалогового вікна По­иск решения, а на екрані з'явиться нове діалогове вікно Добавление ограничения;

-  поступаючи аналогічно, введіть інші обмеження

2х1 + 4х2 + 2х3 ≤ 520 $Е$3 <= $F$3,

1х1 + 1х2 + 2х3 ≤ 220 $Е$4 <= $F$4,

х1 ≥ 0 $В$6 =>0,

х2 ≥ 0 $С$6 =>0,

х3 ≥ 0 $D$6 =>0;

-  після введення останнього обмеження клацнете на кнопці ОК — на екрані заявиться діалогове вікно Поиск решения з введеними обмеженнями у вікні Ограничения.

Якщо при введенні умов задачі виникає необхідність змінити або вилучити вне­сені обмеження, то це здійснюється за допомогою кнопок Изменить або Удалить діало­гового вікна Поиск решения.

На етапі розв'язання задачі треба виконати такі операції:

-  клацнути мишкою на кнопці Параметры діалогового вікна Поиск решения - на екрані з'явиться діалогове вікно Параметры поиска решения. Вікно Параметры поиска решения має декілька параметрів. За допомогою полів Максимальное время та Предельное число итернаций можна вказати пошуку розв'язку, скільки зусиль він повинен прикласти для розв'язування задачі. Використовувані за умовчанням параметри, як правило, достатні для розв'язання більшості задач;

-  встановити прапорець Линейная модель діалогового вікна Параметри поиска ре­шения, що забезпечує застосування симплекс-методу;

-  клацнути мишкою на кнопці ОК - на екрані з'явиться діалогове вікно Поиск реше­ния;

-  клацнути мишкою на кнопці Выполнить - в таблиці з'являться результати ро­зв'язку і на екран буде виведене вікно Результаты поиска решения.

Крім вставлення оптимальних значень у змінювані комірки задачі, Поиск решения може представляти свої результати в трьох звітах: Результаты, Устойчивость і Пределы. Для генерації одного або кількох звітів треба вибрати назву звітів у вікні діалогового вікна. Результаты поиска решения і натиснути кнопку ОК. При виборі кількох звітів треба утримувати клавішу Сtrl. Кожний звіт зберігається на окремому аркуші в поточній книзі, а назва звітів відображається на ярличках.

Звіт Результаты містить цільову комірку, список змінюваних комірок й обме­жень. Цей звіт містить інформацію для кожного обмеження о таких параметрах, як ста­новище і різниця. Становище може бути Связанное, Не связанное або Не вьпюлненное. Значення різниці — це різниця між значеннями, що виведене в кормі ці обмеження при отриманні розв'язку, та числом, яке задано у правій частині обмеження. Зв'язане обмеження — це обмеження, для якого різниця дорівнює 0.

Звіт Устойчивость містить інформацію про те, наскільки цільова комірка чутлива до змінень в обмеженнях. Звіт складається з двох розділів: один для змінюваних комірок і другий для обмежень.

Якщо в діалогову вікні Параметри поиска решения встановлено прапорець Ли­нейная модель, то звіт Устойчивость має декілька додаткових стовпців інформації. Для змінюваних комірок стовпець Редуцированная стоимость показує збільшення значен­ня у цільовій комірці при зміненні значення у змінюваній комірці на одну одиницю, сто­впець Целевой коэффициент показує ступінь залежності між змінюваною коміркою та цільовою коміркою. Стовпці Допустимое увеличение та Допустимое уменьшение показують змінення цільового коефіцієнта до моменту збільшення або зменшення оптима­льних значень у змінюваних комірках.

Для обмежень стовпець Теневая цена показує збільшення цільової функції при збільшенні правої частини обмеження на одну одиницю. Стовпець Ограничение Пра­вая часть виводить значення обмежень, як' використовуються в задачі. Стовпці Допустимое увеличение та Допустимое уменьшение показують змінення значення обме­ження (що наведено в стопці Ограничение Правая часть) до моменту збільшення або зменшення оптимальних значень у змінюваних комірках.

Звіт Пределы надає інформацію про те, в яких межах значення змінюваних комі­рок можуть бути збільшені або зменшені без порушення обмежень задачі. Для кожної змінної звіт дає оптимальне значення, а також найменше й найбільше значення, які мо­же приймати змінна без порушення обмежень.

ІНФОРМАЦІЙНО-МЕТОДИЧНЕ ЗАБЕЗПЕЧЕННЯ

1.  Основы исследования операций. – М.: Мир, 1971.

2.  П Теория массового обслуживания в промышленности. - М: "Экономика", 1970.

3.Бажин системы менеджмента. – М.: ГУ-ЗШЭ, 2000.

4. Боровик ідження операцій в економіці. – К.: ЦНЛ, 2007.

5. Брагін іко-математичне моделювання. – К.: НМК ВО, 1990.

6. Букан Дж., Научное управление запасами. - М.: Наука, 1967

7. Основы исследования операций: в 3-х томах - М.: Мир, .

8. Вентцель операций. - М: Сов. радио, 1972.

9. Вентцель операций. Задачи, принципы, методология. - М.: Наука, 1980.

10. Воробьев игр для економистов-кибернетиков. – М.: Наука, 1985.

11. , , Дорохов -математические методы и модели в планировании и управлении в отрасле связи: Учебник – 3-е изд. – М.: Радио и связь, 1993.

12. Дегтярев операций. - М.: Высшая школа, 1986. – 320 с.

13. , Нефедов операций в планировании и управлении. - К.: Вища шк., 1991.

14. , Савченко технологии в экономике и менеджменте. - Луганск, ВУГУ, 1999.

15. , Суздаль в прикладную теорию игр. – М.: Наука, 1981.

16. Зайченко ідження операцій. – К.: Віпол, 2000.

17. Математические методы оптимизации и экономическая теория. – М.: Прогресс, 1975.

18. Исследование операций: В 2-х томах / Под ред. Дж. Моудера, С. Элмаграби. – М.: Мир, 1981.

19. Исследование операций в экономике. Под редакцией - М.: ЮНИТИ, 2000.

20. , – Математическое оптимальное программирование в экономике. М.: Знание, 1968.

21. Карагодова ідження операцій. – К.: ЦНЛ, 2007.

22. Конюховский методы исследования операций. – Спб.: Питер, 2001.

23. Конюховский методы исследования операцій экономике. – Спб.: Питер, 2002.

24. Сетевые методы планирования и их применение. - М.: Прогресс, 1968.

25. Крушевский игр. – К.: Вища шк., 1977.

26. , Швецов программирование и моделирование в экономике. – К.: Вища шк., 1979.

27. Леснікова І. Ю. Дослідження операцій у середовищі електронних таблиць ЕХСЕL. – К.: ЦНЛ, 2007.

28. Ларіонов Ю. І. Математичні методи системного аналізу та дослідження операцій - К.: ІСДО, 1994.

29. Ларіонов Ю. І., Левикін В. М., Хажмурадов ідження операцій в інформаційних системах: Навчальний посібник. – 2-е вид. – Харків: Компанія СМІТ, 2005.

30. Ларіонов Ю. І., , Хажмурадов ідження операцій. ч.1: Навчальний посібник. – Х.: ВД "ІНЖЕК", 2004.

31. Ларіонов Ю. І., , Хажмурадов ідження операцій. ч.2: Навчальний посібник. – Х.: ВД "ІНЖЕК", 2005.

32. Лопатников -математический словарь. – М.: Наука, 1987.

33. Лукин массового обслуживания. - М.: Воениздат, 1980.

34. Математические методы и модели в планировании и управлении горным производством. – М.: Недра, 1985.

35. , Петухов вопросы теории массового обслуживания. - М.: Сов. радио, 1969.

36. Охріменко ідження операцій. – К.: ЦНЛ, 2006.

37. , и др. Сетевые графики в планировании. - М: Высш. шк., 1981.

38. , Прохоров такое теория массового обслуживания. - М: Сов. радио, 1965.

39. Справочник по оптимизационным задачам в АСУ. – Л.: Машиностроение, 1994.

40. Таха X. Введение в исследование операций: В 2-х книгах - М.: Изд. дом «Вильямс», 2001.

41. Ржевський теорії дослідження операцій. – К.: В-во Європейського у-ну,1999.

42. Фомин методы и модели в коммерческой деятельности. - М.: Финансы и статистика, 2001.

43. М Теория массового обслуживания и ее применение в экономике. - М: Статистика, 1971.

44. Чуев операций в военном деле. - М.: Воениздат, 1970.