РІШЕННЯ ЗАДАЧІ ОПТИМІЗАЦІЇ НА ОСНОВІ СИМПЛЕКС-ТАБЛИЦ, ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ, ВИЗНАЧЕННЯ ПОЧАТКОВОГО ДОПУСТИМОГО РІШЕННЯ - Рішення оптимізаційної задачі лінійного програмування
ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ
Для приведення даного завдання до стандартної форми необхідно лише перейти від обмежень - нерівностей до рівності. Для цього введемо додаткові балансові ненегативні змінні. Також для спрощення подальших обчислень розділимо обидві частини обмежень на комплектацію деталей на 5:
X1 + X2 + X3 + X7 = 8;
X4 + X5 + X6 + X8 = 8;
- 2X1 - X2 + 6X4 - 3X5 = 0; 2X1 - 2X3 + 6X4 - 2X6 =0;
X1, X2, X3, X4, X5, X6, X7, X8 v 0.
E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 max
Де Х7, Х8 - залишкові змінні.
Отже, наше початкове завдання ми привели до стандартної форми основного завдання лінійного програмування.
ВИЗНАЧЕННЯ ПОЧАТКОВОГО ДОПУСТИМОГО РІШЕННЯ
Для завдання, представленого в стандартній формі, кількість змінних звичайна більше, ніж кількість обмежень. Тому для знаходження початкового рішення задачі потрібно виразити m змінних (тобто кількість змінних, рівна кількості рівнянь) через решту n-m змінних, прийняти ці n-m змінних рівними нулю і, таким чином, знайти значення m змінних (у заданому завданні m=4 і n=8). Змінні, значення яких приймаються рівними нулю, називаються небазисними, а решта m змінних - базисними. Значення базисних змінних ненегативні (деякі з них можуть виявитися рівними нулю). Кількість базисних змінних завжди рівна кількості обмежень. Знайдене таким чином рішення називається початковим допустимим базисним рішенням. Воно відповідає всім обмеженням.
Початкове рішення найпростіше знайти у разі, коли в кожному обмеженні є змінна, яка входить в нього з коефіцієнтом 1 і при цьому відсутній в інших обмеженнях. Такі змінні приймаються як базисні (вони утворюють початковий базис завдання). Решта (небазисні) змінних приймається рівними нулю. Таким чином, базисні змінні приймають значення, рівні правим частинам обмежень.
Отже, для знаходження початкового допустимого рішення необхідно, щоб в кожне з рівнянь входила змінна з коефіцієнтом 1 і не входила в інші рівняння (базисна змінна). У нашому випадку ми маємо тільки 2 базисних змінної (X7 і X8), не вистачає ще двох базисних змінних. Їх можна створити за допомогою спеціального способу, який називається побудовою штучного базису.
Похожие статьи
-
ПОБУДОВА ШТУЧНОГО БАЗИСУ - Рішення оптимізаційної задачі лінійного програмування
Методи штучного базису призначені для побудови початкового базису (тобто для отримання початкового рішення) у випадках, коли його побудова безпосередньо...
-
ПЕРШИЙ ЕТАП ДВОХЕТАПНОГО СИМПЛЕКС-МЕТОДА - Рішення оптимізаційної задачі лінійного програмування
Отже, на першому етапі двохетапного методу відшукується початкове допустиме рішення. Для цього виконаємо наступні дії: Будуємо штучну цільову функцію -...
-
Цінність ресурсу - це величина збільшення значення цільової функції при збільшенні запасів даного ресурсу на одиницю (або відповідно величина зменшення...
-
ДРУГИЙ ЕТАП ДВОХЕТАПНОГО СИМЛЕКС-МЕТОДУ - Рішення оптимізаційної задачі лінійного програмування
Отже, як видно з Таблиці 4, всі штучні змінні вийшли з базису, штучна цільова функція обнулилася - значить, перший етап двохетапного симплекс-метода...
-
Варіант 80. У цеху є токарний верстат і верстат-автомат. Цех випускає деталі 1,2 і 3 в комплекті: на кожну деталь 1 - по 2 деталі 2 і 3. Годинна...
-
ВВЕДЕННЯ - Рішення оптимізаційної задачі лінійного програмування
В даний час оптимізація знаходить застосування в науці, техніці і в будь-якій іншій області людської діяльності. Оптимізація - цілеспрямована діяльність,...
-
Етапи рішення прикладних задач з використанням комп'ютерів 1) Формулювання задачі в термінах певної предметної галузі знань (математика, фізика,...
-
Для розробки задається передавальна функція незмінною частини системи регулювання, задавальна дія, чисельне значення статичної помилки, часу регулювання...
-
Определение документооборота Для начала разберемся, что же означает термин "система электронного документооборота", что включается это понятие и в чем...
-
Постановка задачи Имеющаяся база данных SQL имеет недостаточное количество полей и таблиц, не имеет упорядоченной структуры пользователей для работы с...
-
Математична постановка задачі Для того, щоб розіграш лоту здійснився, необхідна одна з двох умов: кількість можливих білетів у розіграшу лоту набралась,...
-
Актуальность Сегодня всемирная популярность социальных информационных сетей продолжает набирать обороты, все большее пользователей не может отказать себе...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Широкое распространение в операционной системе Windows имеет множество стандартных программ обеспечивающих работу устройств компьютера и служащих для...
-
Пересчет симплекс-таблицы. - Транспортная задача
Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 1,...
-
Описание задачи, Моделирование бизнес-операций - Основы технологии программирования
Необходимо разработать клиент-серверную информационную систему для организации. Организация владеет сведениями о станциях грузоотправления,...
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Далее необходимо провести качественную характеристику ПО (табл. 4.1.) для покупки его в отдел продаж для работы Ревенью менеджера. Таблица 4.1 ....
-
Постановка задачи, выбор предметной области Предметная область: "Автомобиль". Создание автомобиля будет состоять из трех этапов: выбор кузова, выбор...
-
Несмотря на прогресс, привычные стойки регистрации, расположенные внутри в аэропортах, продолжают оставаться самым распространенным выбором для...
-
М. Х. Мескон посилається на дослідження, згідно з якими керівник від 50 до 90% усього часу витрачає на комунікації - він займається цим, щоб реалізувати...
-
Стандартные программы и приложения - Операционная система Windows
Стандартные программы входят в состав самой операционной системы Windows (текстовый редактор WordPad, графический редактор Paint, виртуальный калькулятор...
-
Методи вирішення задачі - Інформаційна система адміністратора готелю "Венеціанська ніч"
Дана система призначена, щоб полегшити оперування інформацією працівників готелю "Венеціанська ніч". З її допомогою вони зможуть швидко реєструвати...
-
Котроллеры на основе блока CPU BC9120, в принципе как и на основе любого другого блока CPU фирмы BECKHOFF, построены по модульному принципу. Что это...
-
Методы Рунге-- Кутты-- важное семейство численных алгоритмов решения обыкновенных дифференциальных уравнений и их систем. Данные итеративные методы...
-
№ пор. Об'єкт практики та види робіт Термін проходження практики Початок Закінчення 1. Інструктаж з техніки безпеки та виробничої санітарії. 20.01....
-
Excel программирование статистический Статистические функции Применение статистических функций облегчает пользователю статистический анализ данных. Целый...
-
Докладний опис мови - Гнучка система інформаційної підтримки підвищення кваліфікації персоналу ДП №9
З точки зору системи типізації, PHP є мовою програмування з динамічною типізацією. Немає необхідності явного визначення типу змінних, хоча така...
-
Кондиціювання - Розроблення модуля "Благодійний аукціон" на базі веб-технологій. Інтерфейс кампаній
Кондиціювання повітря - створення й автоматична підтримка в закритих приміщеннях і засобах транспорту параметрів повітряного середовища (температури,...
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
Постановка задачи Основная задача автоматизации документооборота в работе состоит в оптимизации бизнес-процесса на уровне обработки документов...
-
Формирование области многокритериального выбора вариантов Стоит задача о выборе марки автомобиля с их известными особенностями и характеристиками....
-
В этой главе представлено описание инструментов и методов, использованных при написании кода программы. Инструменты разработки серверной части Для...
-
Поскольку клиентская часть представляет собой приложение на базе операционной системы Android, то для ее разработки был выбран рекомендуемый...
-
Версионность базы данных - Программное обеспечение для пропускной системы на основе технологии NFC
С ростом приложения существует проблема обновления схемы базы данных с сохранением внесенных данных. Если информация в базе данных не может быть легко...
-
Особенностью архитектуры REST является отсутствия хранения состояния на сервере. Для того, чтобы не передавать пользовательские логин и пароль каждый...
-
Особенностью API для коммуникации с СКУД является то, что авторизация методов происходит не с помощью токена, а с помощью проверки IP адреса клиента на...
-
Анализ безопасности - Программное обеспечение для пропускной системы на основе технологии NFC
Для обеспечения безопасности системы было решено использовать протокол HTTPS для связи клиента и сервера. Использование протокола HTTPS для коммуникации...
-
Базы данных (БД) составляют в настоящее время основу компьютерного обеспечения информационных процессов, входящих практически во все сферы человеческой...
РІШЕННЯ ЗАДАЧІ ОПТИМІЗАЦІЇ НА ОСНОВІ СИМПЛЕКС-ТАБЛИЦ, ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ, ВИЗНАЧЕННЯ ПОЧАТКОВОГО ДОПУСТИМОГО РІШЕННЯ - Рішення оптимізаційної задачі лінійного програмування