Формулировка задачи - Линейное программирование
Даны линейная функция
Z=С1 х1 +С2 х2 +...+СN xN (1.1)
И система линейных ограничений
A11 x1 + a22 x2 +... + a1N ХN = b1
A21 x1 + a22 x2 +... + a2N ХN = b2
...............
AI1 x1 + aI2 x2 +... + aIN ХN = bI (1.2) ...............
AM1 x1 + aM2 x2 +... + aMN ХN = bM
XJ 0 (j = 1, 2, ..., n) (1.3)
Где аIj, bJ и СJ - заданные постоянные величины.
Найти такие неотрицательные значения х1, х2, ..., хN, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение.
Общая задача имеет несколько форм записи.
Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях
А1 х1 + А2 x2 +... + АN xN = АО, X0 (1.4)
Где С = (с1, с2, ..., сN ); Х = (х1, х2, ..., хN ); СХ - скалярное произведение; векторы A1 = A2 =, ..., AN состоят соответственно из коэффициентов при неизвестных и свободных членах.
Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0 Х0, где С = (с1, с2, ..., сN ) - матрица-cтрока; А = (аIj ) - матрица системы; Х =(xIj )- матрица-столбец, А0 = (аI ) матрица-столбец
Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = СJ хJ при ограничениях
- 0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х1, х2, ..., хN ), удовлетворяющий условиям (1.2) и (1.3). 0пределение 2. План Х = (х1, х2, ..., хN ) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х, являются линейно независимыми.
Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.
- 0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным. 0пределение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.
В дальнейшем рассмотрено решение задач линейного программирования, связанных с нахождением минимального значения линейной функции. Там, где необходимо найти максимальное значение линейной функции, достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней функции. Заменяя на противоположный знак полученного минимального значения, определяем максимальное значение исходной линейной функции.
Похожие статьи
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Геометрический метод, Двойственная задача - Линейное программирование
Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...
-
Линейное программирование - Линейное программирование
Линейный программирование математический графический Что же такое линейное программирование? Это один из первых и наиболее подробно изученных разделов...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Введение - Линейное программирование
Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой...
-
Постановка задачи: Фирма приобрела технологическую линию за начальную стоимость Sn. Срок службы технологической линии составляет K лет. Остаточная...
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
1. Каковы основные этапы решения задач ЛП в MS Excel? 2. Каков вид и способы задания формул для целевой ячейки и ячеек левых частей ограничений? 3. В чем...
-
Заключение - Линейное программирование
В данной дипломной работе мною были освоены навыки решения задач линейного программирования геометрическим методом. Для этого я изучил теоретические...
-
Задачи и функции линейного отдела полиции Отдел возглавляет начальник, назначаемый на должность и освобождаемый от должности в установленном порядке....
-
Языки и системы программирования, их эволюция - Автоматизация решения задач пользователя
Язык программирования - это способ записи программ решения различных задач на ЭВМ в понятной для компьютера форме. Процессор компьютера непосредственно...
-
Таблица сопротивлений некоторых термометров сопротивления Температурав °C Pt100 Pt1000 Typ: 404 Typ: 501 -50 80, 31 803, 1 -40 84, 27 842, 7 -30 88, 22...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
-
Оргтехника, ПК, телефонные аппараты На данный момент начальник ДЧ ЛОП использует комплекс технических средств, который предназначен для обработки...
-
Варианты - Решение задач линейного программирования с использованием Microsoft Excel
Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл. 1.5). Таблица 1.5 Варианты задач к лабораторной работе № 1 №...
-
Датчики Pt1000 (TSQ* и TSH*) прекрасно подходят для любых климатических систем, где необходимо измерять температуры в диапазоне от -50 до 250 °C с...
-
Синтаксис объявления класса в языке С++ имеет следующий вид: Class<имя класса>: <спецификатор доступа><имя базового класса> { Элементы класса...
-
Описание задачи, Моделирование бизнес-операций - Основы технологии программирования
Необходимо разработать клиент-серверную информационную систему для организации. Организация владеет сведениями о станциях грузоотправления,...
-
На данный момент существует множество аналогов данного приложения, можно выделить такие как стандартный проводник Windows и Total Commander. Заказчику...
-
Протокол проверки программы - Программирование алгоритмов линейных и циклических структур
1. Введем размерность массива N = 6 2. Заполним элементы массива X(i) следующими значениями: 12, 1.34, 8, 10, 17.5, 30 3. Получим следующие результаты:...
-
FBD (Function Block Diagram) - является графическим языком программирования. Предназначенный для программирования микро контролеров с помощью блок...
-
Линейная замкнутая система Рассмотрим линейную стационарную непрерывную управляемую систему: (1.1) - вектор состояния системы, - управление, - выход...
-
Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...
-
Постановка задачи, Подход к реализации - Обьекто-ориентированное программирование
Создать класс Triangle для представления треугольника. Поля класса - длины сторон. Требуется реализовать операции: вычисления углов треугольника,...
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Пересчет симплекс-таблицы. - Транспортная задача
Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 1,...
-
Приведенный ниже программа позволяет работать с несколькими типами датчиков, так же в код встроен фильтр для более точного измерения на границе диапазона...
-
Сформулируем задачу поиска оптимального регулятора в общих понятиях: дан многомерный реальный объект управления с квадратной матричной передаточной...
-
Линейные блоковые коды - Кодек каскадного кода Хэмминга
Код называется групповым, если кодовые комбинации образуют некоторую подгруппу группы всех последовательностей длиной n Линейные коды задаются с помощью...
-
Физическое обоснование - Вокодеры с линейным предсказанием
Работа вокодера (voice coder) основана на анализе характерных особенностей человеческой речи. На рис. 2 показаны условно частотные характеристики речи...
-
Как уже отмечалось в разделе "Различимость входных данных" числовые сигналы рекомендуется масштабировать и сдвигать так, чтобы весь диапазон значений...
-
Системы счисления. Представление данных в ЭВМ - Основы программирования
В современном мире для записи числовой информации используют позиционные системы счисления, в которых числа записываются с помощью ограниченного...
-
Под критическим значением параметра регулятора (K или Т) понимается такое значение (Ккр или Ткр), при котором система оказывается на границе...
-
Линейная зависимость - Составление программы для решения системы уравнений
Рассмотрим подробнее аппроксимирующие зависимости Y(x)=f(x, B 0 ,B 1,..., B N ) с двумя параметрами: Y(x)=f(x, B 0 ,B 1 ) Используя соотношения (1) и...
-
Дана система линейных уравнений (СЛУ) с n неизвестными: В матричной форме записи система (1) имеет вид: (2) Где : n - порядок системы; - матрица...
-
Ранг системы ограничений T. З. равен (m + n - 1), следовательно, невырожденный опорный план Т-задачи содержит (m + n - 1) положительных компонент или...
Формулировка задачи - Линейное программирование