Розв’язок задач лінійного програмування за допомогою EXCEL

1. Цель лабораторной работы.. 3

2. Основные действия пользователя при работе в ОС.. 3

3. Формат команд ОС Unix. 3

4. Порождение имен файлов. 4

5. Базовый пользовательский набор команд. 4

5.1. Получение справки о команде (команда man) 4

5.2. Переход из каталога в каталог (команда cd) 5

5.3. Определение имени текущего каталога (команда pwd) 6

5.4. Просмотр содержимого каталогов (команда ls) 7

5.5. Создание каталога (команда mkdir) 11

5.6. Удаление каталога (команда rmdir) 11

5.7. Копирование файлов и каталогов (команда cp) 11

5.8. Перемещение (или переименование) файлов (команда mv) 12

5.9. Удаление файлов (команда rm) 13

5.10. Просмотр содержимого файлов (команды cat и more) 13

5.11. Установка и изменение прав доступа к файлам.. 14

5.12. Поиск файлов (команда find) 16

6. Дополнительные возможности интерпретатора команд. 17

6.1. Перенаправление ввода-вывода. 18

6.2. Конвейеры.. 19

6.3. Фоновые команды.. 20

6.4. Группирование команд. 20

7. Создание файлов с помощью текстовых редакторов. 21

7.1. Редактор vi 21

7.2. Редактор joe. 22

Задание по лабораторной работе. 24

Отчет о работе. 24

Приложение 1. Примеры использования команды find. 25

Литература. 25

Розв’язок задач лінійного програмування за допомогою EXCEL

Постановка задач математичного програмування (ЗМП) в загальному вигляді: Нехай задана функція і відомо, що належать деякій множині G, де G – область обмежень, або область допустимих значень задачі. називається цільовою функцією. Суть задачі полягає в знаходженні екстремума (максимума або мінімума) фукції f.

Найчастіше множину G задають у вигляді розв’язків деякої системи нерівностей виду:

Якщо функції лінійні, тобто кожна з них має вигляд:

, то це задача лінійного програмування.

Якщо функції нелінійні, то це задача нелінійного програмування.

Якщо функції містять випадкові величини, то це задача стохастичного програмування.

Якщо функції містять змінні, які змінюються в часі, то це задача динамічного програмування.

Ми будемо працювати з задачами лінійного програмування.

Розглянемо приклад:

Підприємство виготовляє продукцію 2-х видів: А та В. Наприклад підприємство легкої промисловості (це швейна фабрика) і вона шиє жіночі та дитячі картки. Для виготовлення продукції А та В необхідно три типи сировини (тканина, підкладка, замки).

Для виготовлення одного виробу типу А необхідно сировини першого типу а₁ одиниць, другого типу а₂ одиниць, третього типу а₃ одиниць.

Для виготовлення одного виробу типу В необхідно сировини першого типу b₁ одиниць, другого типу b₂ одиниць, третього типу b₃ одиниць.

Запаси сировини першого типу складають d₁ одиниць, другого типу d₂ одиниць, третього типу d₃ одиниць.

Нехай с₁ це прибуток від реалізації одного виробу виду А і нехай с₂ це прибуток від реалізації одного виробу виду В.

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

Тоді економіко-математична модель задачі має наступний вигляд:

Нехай с₁ це витрати на виробництво одного виробу виду А і нехай с₂ це витрати на виробництво одного виробу виду В.

Тоді економіко-математична модель задачі має наступний вигляд:

Приклад:

Дану задачу можна розв’язати трьома способами: графічно, аналітично (симплекс метод) та застосовуючи функцію “Поиск решений”.

Графічний розв’язок:

1. Побудова допустимої області G:

Кожну з нерівностей системи перетворюємо у рівності і будуємо їх графіки за двома точками:

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

Спільна область, яка задовольняє всі нерівності є область G, тобто будь-яка точка цієї області є розв’язком заданої системи рівнянь. Далі серед множини цих точок необхідно знайти одну єдину точку, при якій цільова функція приймала б максимальне значення. Це і буде оптимальний розв’язок.

Отже наступним етапом знаходження оптимального розв’язку є побудова вектора градієнта.

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

Наступним етапом знаходження оптимального розв’язку є побудова лінії рівня.

Лінія рівня – це перпендикуляр до вектора градієнта. Отже, будуємо перпендикуляр, передвигаємо отриману лінію рівня паралельно побудованій в допустиму область, а потім для знаходження максимуму передвигаємо її дала у напрямку вектора-градієнта та знаходимо крайню точку, де лінія рівня перетинається з допустимою областю. Це і є точка максимуму. Для знаходження мінімума лінію рівня передвигаємо у напрямку, протилежному вектору градієнту, і також знаходимо крайню точку, де лінія рівня перетинається з допустимою областю.

Допустима область може бути відкрита, тоді задача не має розв’язку, або сходиться в одній точці – тоді задача має єдиний розв’язок.

Побудова допустимої області на комп’ютері:

1. Табулюємо х₁.

2. Виражаємо х₂ через х₁ для кожного з рівнянь.

За отриманими значеннями будуємо допустиму область.

Знаходження розв’язку за допомогою фукції “Поиск решения”.

Розташувати дані задачі на робочому листі Excel.

Ставимо курсор в цільову комірку С1, Сервіс, Поиск решений.

Для знаходження цілочисельного розв’язку необхідно додати у вікно обмежень ще два обмеження: х₁ целое, х₂ целое.