Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Методичні вказівки до виконання практичної роботи






Практична робота № 5

 

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

 

МЕТА: навчитися виконувати постановку задачі лінійного програмування та ров’язувати вихідну задачу симплекс-методом.

 

Хід роботи

 

1. Для виготовлення двох видів продукції П1 та П2 використовують три види ресурсів А1, А2, А3. Запаси ресурсів, норми їх витрат і прибуток від реалізації одиниці продукції для 30 варіантів задані в таблиці 1. Виконати постановку задачі лінійного програмування (скласти таблицю).

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

3. Виконати контроль обчислень на кожному кроці та проаналізувати правильність розв’язку задачі. Опорний план – це позитивне базисне рішення.

 

Методичні вказівки до виконання практичної роботи

 

Ідея симплекс методу:

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

1) Змінні задачі, котрі переходять з базисних у вільні обираються так, щоб зберігалася умова позитивності задачі.

2) На кожному кроці в базисі змінюється лише одна базисна і одна вільна невідомі.

Кожному опорному плану відповідає ОЗЛП з ОР. В залежності від обраного базиса форма її запису різна, але вона відповідає таким закономірностям:

1) Кожна базисна невідома входить тільки до одного рівняння системи з коеффіціентом – “1”. Якщо нумерація базисних невідомих збільшується, то система називається системою з базисом.

2) Вільні члени системи обмежень позитивні.

3) Цільова функція залежить тільки від вільних невідомих. ОЗЛП з ОР котра задовольняє умовам(1-3) називається канонічною.

Щоб задача була канонічною досить так вибрати базисні невідомі, щоб виконалась умова 1-2. Така система називається канонічною системою обмежень.

Якщо в цільову функцію входять базисні невідомі, а система рівнянь канонічна, то задачу називають майже канонічною.

Знайти найбільше значення цільової функції:

 

 

Z=x1+2x2+12

2x1+3x2+x3=12

x1+2x2+x4=16

xj≥ 0 j=

x3, x4 – базисні невідомі

x1, x2 – вільні невідомі

 

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

Властивості симплекс-методів:

1) Повнота:

а) чи є симплекс-метод однозначним;

б) як практично побудувати опорний план і чи буде останній опорний план її точним рішенням.

2) Сфера застосування:

а) для яких математичних виконується цей метод.

3) Властивість сходження:

а) чи завжди алгоритм забезпечує сходимість методів, чи завжди сходимість дає правильний результат;

б) скільки ітерацій потрібно для рішення задачі.

4) Вимоги до обчислень:

а) Наскільки громіздким є обчислення;

б) При якій точності досягається необхідний результат.

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

Користуючись симплекс-методом не будемо відрізняти, де обмеження, а де оптимізуюча (цільова) функція.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.