ДРУГИЙ ЕТАП ДВОХЕТАПНОГО СИМЛЕКС-МЕТОДУ - Рішення оптимізаційної задачі лінійного програмування
Отже, як видно з Таблиці 4, всі штучні змінні вийшли з базису, штучна цільова функція обнулилася - значить, перший етап двохетапного симплекс-метода закінчений, знайдено початкове допустиме рішення: (Х1,X2,X3,X4,X5,X6) = (0,0,0,0,0,0), цільова функція Е=0. Тепер переходимо до реалізації другого етапу: викреслюємо з таблиці рядок штучної цільової функції і стовпці штучних змінних; над новою таблицею виконуємо звичайні процедури симплекс-метода, а саме: провідний стовпець визначається також, як і для першого етапу двохетапного симплекс-метода, єдина відмінність полягає в тому, що максимальний по модулю негативний коефіцієнт знаходимо по Е-рядку цільової функції. Розрахунок ведемо до тих пір, поки в Е-рядку не залишиться негативних коефіцієнтів:
БП |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
БР |
E |
0 |
0 |
-5 |
0 |
0 |
-5 |
0 |
0 |
0 |
X7 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
8 |
X8 |
-0,33 |
-0,33 |
1 |
0 |
0 |
2 |
0 |
1 |
8 |
X4 |
0,33 |
0 |
-0,33 |
1 |
0 |
-0,33 |
0 |
0 |
0 |
X5 |
0 |
0,33 |
-0,67 |
0 |
1 |
-0,67 |
0 |
0 |
0 |
Таблиця 5. Симплекс-таблиця №4.
Наше початкове допустиме рішення не є оптимальним, оскільки в Е-рядку містяться негативні коефіцієнти. Визначимо по Е-рядку нову змінну для включення в базис. Це змінна X3, оскільки -5 - максимальне по модулю негативне число (коефіцієнт Е-рядка при змінній X6 також рівний -5, тому вибрали будь-яку з цих змінних, наприклад X3). Стовпець X3 стає таким, що веде. По мінімальному сімплексному відношенню ( 8/1=8; 8/1=8) для виключення з базису вибираємо змінну Х7 (сімплексне відношення при змінній X8 також рівне 8, тому вибрали будь-яку з цих змінних). Провідний елемент рівний 1. Після проведених пересчетов отримуємо нову симплекс-таблицю:
БП |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
БР |
E |
5 |
5 |
0 |
0 |
0 |
-5 |
5 |
0 |
40 |
X3 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
8 |
X8 |
-1,33 |
-1,33 |
0 |
0 |
0 |
2 |
-1 |
1 |
0 |
X4 |
0,67 |
0,33 |
0 |
1 |
0 |
-0,33 |
0,33 |
0 |
2,67 |
X5 |
0,67 |
1 |
0 |
0 |
1 |
-0,67 |
0,67 |
0 |
5,33 |
Таблиця 6. Симплекс-таблиця №5.
Отже, як видно з таблиці, деякі з шуканих змінних, а саме Х3, Х4 і Х5, почали рости, що привело і до зростання значення цільової функції - з нульового значення вона прийняла значення 40. Це можна пояснити тим, що з точки початкового допустимого рішення ми перейшли до сусідньої кутової точки області допустимих рішень, причому в цій сусідній крапці зростання цільової функції максимальне. Проте в Е-рядку є ще негативний коефіцієнт, тому продовжимо розрахунки.
Визначимо по Е-рядку нову змінну для включення в базис. Це змінна X6, оскільки -5 - максимальне по модулю негативне число. Стовпець X6 стає таким, що веде. По мінімальному сімплексному відношенню ( 0/2=0) для виключення з базису вибираємо змінну Х8. Отримуємо нову симплекс-таблицю:
БП |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
БР |
E |
1,67 |
1,67 |
0 |
0 |
0 |
0 |
2,5 |
2,5 |
40 |
X3 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
8 |
X6 |
-0,67 |
-0,67 |
0 |
0 |
0 |
1 |
-0,5 |
0,5 |
0 |
X4 |
0,44 |
0,11 |
0 |
1 |
0 |
0 |
0,17 |
0,17 |
2,67 |
X5 |
0,22 |
0,55 |
0 |
0 |
1 |
0 |
0,33 |
0,33 |
5,33 |
Таблиця 7. Симплекс-таблиця №6.
Оскільки всі коефіцієнти E-рядка таблиці 7 позитивних, то оптимальне рішення знайдене. Оптимальний план полягає в тому, щоб токарний верстат працював над деталями типу 3 8 годин за зміну, тобто всю робочу зміну, і не працював над деталями типу 1 і 2 взагалі. Верстат-автомат повинен працювати за зміну 2,67 години над деталями типу 1 і 5,33 години над деталями типу 2 і не повинен працювати над деталями типу 3. При цьому за зміну випускатиметься максимально можлива кількість комплектів деталей, а саме 40 комплектів. Жоден з верстатів не простоюватиме.
Похожие статьи
-
ПЕРШИЙ ЕТАП ДВОХЕТАПНОГО СИМПЛЕКС-МЕТОДА - Рішення оптимізаційної задачі лінійного програмування
Отже, на першому етапі двохетапного методу відшукується початкове допустиме рішення. Для цього виконаємо наступні дії: Будуємо штучну цільову функцію -...
-
Цінність ресурсу - це величина збільшення значення цільової функції при збільшенні запасів даного ресурсу на одиницю (або відповідно величина зменшення...
-
ПОБУДОВА ШТУЧНОГО БАЗИСУ - Рішення оптимізаційної задачі лінійного програмування
Методи штучного базису призначені для побудови початкового базису (тобто для отримання початкового рішення) у випадках, коли його побудова безпосередньо...
-
ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ Для приведення даного завдання до стандартної форми необхідно лише перейти від обмежень - нерівностей до...
-
ВВЕДЕННЯ - Рішення оптимізаційної задачі лінійного програмування
В даний час оптимізація знаходить застосування в науці, техніці і в будь-якій іншій області людської діяльності. Оптимізація - цілеспрямована діяльність,...
-
Варіант 80. У цеху є токарний верстат і верстат-автомат. Цех випускає деталі 1,2 і 3 в комплекті: на кожну деталь 1 - по 2 деталі 2 і 3. Годинна...
-
Етапи рішення прикладних задач з використанням комп'ютерів 1) Формулювання задачі в термінах певної предметної галузі знань (математика, фізика,...
-
Табличный процессор Excel фирмы Microsoft предназначен для ввода, хранения, обработки и выдачи больших объемов, данных в виде, удобном для анализа и...
-
Докладний опис мови - Гнучка система інформаційної підтримки підвищення кваліфікації персоналу ДП №9
З точки зору системи типізації, PHP є мовою програмування з динамічною типізацією. Немає необхідності явного визначення типу змінних, хоча така...
-
Математична постановка задачі Для того, щоб розіграш лоту здійснився, необхідна одна з двох умов: кількість можливих білетів у розіграшу лоту набралась,...
-
Застосування масивів при розв'язанні задач у Visual Basic 6.0
- Для створення відкритого масиву (public array) треба використати оператор Public у секції Declaration модуля; - Для створення масиву рівня модуля...
-
Широкое распространение в операционной системе Windows имеет множество стандартных программ обеспечивающих работу устройств компьютера и служащих для...
-
Відомі два підходи до організації інформаційних масивів: файлова організація та організація у вигляді бази даних. Файлова організація передбачає...
-
Сучасні вимоги до ІС "ГППР" надає адміністрації та співробітникам унікальну можливість отримувати повну і достовірну інформацію про наявне устаткування,...
-
Пересчет симплекс-таблицы. - Транспортная задача
Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 1,...
-
На рисунке 1 представлен фрагмент электронной таблицы, в которой содержаться исходные данные для решения задачи. Рисунок 1 - Фрагмент электронной...
-
Выполнения проекта монтажа охранной сигнализации состоит из множества операций, которые складываются в этапы работ проекта. Схематично структура этапов...
-
Базы данных (БД) составляют в настоящее время основу компьютерного обеспечения информационных процессов, входящих практически во все сферы человеческой...
-
Заключение - Сравнение моделей представления слов в задаче очистки текста от обесцененной лексики
В данной работе проводится сравнение эффективности 6 методов поиска по однословному запросу. В качестве запроса выступает слов из стоп-листа - списка...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Постановка задачи: Для заданных функций необходимо: 1. Построить электронную таблицу (одну для обеих функций) для вычисления значений функций в заданном...
-
Шестой метод - построение суффиксных деревьев. Среди большого количества методов анализа текста метод аннотированного суффиксного дерева выделяется тем,...
-
В качестве доступного инструментария были рассмотрены две открытые кроссплатформенные библиотеки для разработки C++ приложений WxWidgets и Boost ,...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Информационная система (ИС) ГИБДД должна обеспечивать хранение информации об автомобилях (марка, номер кузова, номер двигателя, цвет кузова, гос. номер),...
-
Построение аналитической модели АОУ затруднено из-за отсутствия или недостатка априорной информации об объекте управления, а также из-за ограниченности и...
-
Для того, чтобы разработать оптимальный метод интеграции сторонних систем в существующую ИТ-инфраструктуру систем компании, требуется точно поставить...
-
Составьте программу для реализации графического редактора линий, изображенного на рисунке 1.1.: Рисунок 1.1. - Пример работы Целью данной работы является...
-
Решение задачи средствами MS EXCEL - Расчет трудоемкости средствами Ms Excel
Деталь трудоемкость программа изготовление 1. Вызовите Excel: - нажмите кнопку "Пуск"; - выберите в главном меню команду "Программы"; - выберите MS...
-
Вычислить максимум функции F(x)=-L(x1)x2+3.1L(x2)x+5 на отрезке [a;b] с точностью е. L(x1), L(x2) - значения интерполяционного многочлена, построенного...
-
Загальні відомості Теплова електростанція (ТЕС) - це електростанція, що виробляє електричну енергію в результаті перетворення теплової енергії, що...
-
Аналитический способ решения задачи №3 представляет собой проверку вычислений: - для лица Лушников В. В. сумма налога на дарение составит 0, т. к. сумма...
-
Для решения задачи №3 необходимо ввести исходные данные в электронную таблицу, т. е. таблицы 1,2 (рисунок 16). Рисунок 16 - Ввод исходных данных в...
-
1. Провести обзор методов автоматического построения профиля нормального поведения веб-приложения. 2. Сформулировать требования к методу, провести...
-
Введение - Программные и аналитические решения финансовых и экономических задач
Табличные процессоры - одно из важнейших средств для решения задач широкого назначения. Табличные процессоры в силу своей наполненности включены в пакет...
-
Руководство оператора - Разработка электронного учебного пособия "VBA. Решение задач"
1.6.2.1 Назначение программы Назначение и функции Основным назначением электронного учебного пособия является помощь студентам БСК при изучении...
-
Вариант №1 1. Выбрать и обосновать наиболее эффективный метод решения задачи. 2. Разработать алгоритм и программу для решения задачи в общем виде. 3....
-
Постановка задачи - Расчет трудоемкости средствами Ms Excel
Необходимо рассчитать нормативную трудоемкость квартальной и месячной производственной программы цеха по деталям. Для этого необходимо перемножить...
-
VC++ - мова і середовище програмування, що відноситься до класу RAD - (Rapid Application Development _ "Засіб швидкої розробки додатків") засобів CASE -...
-
Возможность использования формул и функций является одним из важнейших свойств программы обработки электронных таблиц. Это, в частности, позволяет...
ДРУГИЙ ЕТАП ДВОХЕТАПНОГО СИМЛЕКС-МЕТОДУ - Рішення оптимізаційної задачі лінійного програмування