Линейное программирование. Симплекс - метод. Решение задачи линейного программирования.

Симплексный метод в отличие от геометрического универсален. С его помощью можно решить любую задачу линейного программирования. Применение симплекс метода осуществляется в два этапа:

0. Нахождение исходного допустимого базисного решения

1. Последовательное улучшение полученного на первом этапе решения до оптимального.

Основные операции симплекс метода проведем с использованием индивидуального варианта задания.

Постановка задачи:

Найти х1, х2 доставляющий максимум целевой функции w=8x1+6х2. При ограничения:

∀x_i≥0

От ограничений неравенств перейдем к ограничением равенствам введя дополнительные переменные: х3, х4, х5.

Этап 1.

Нахождение допустимого базисного решения.

За основные переменные примем х3, х4, х5, тогда не основными переменными являются х1 и х2. Примечание: не основные переменные приравниваем к нулю.

x1, x2=0

Получено исходное допустимое базисное решение:

(x1,х2,х3,х4,х5)=(0,0,700,800,600)

Очевидно, что даже с точки зрения здравого смысла данное решение не может быть признано оптимальным, поскольку, w=8x1+6x2=0, однако решение допустимое, тем не менее воспользуемся формальным критерием оптимальности: если в выражение для целевой функции w имеется хотя бы 1 переменная с положительным коэффициентом, то полученное решение нельзя признать оптимальным, в нашем случае w=8x1+6x2, то есть обе переменные имеют коэффициент с положительным знаком, следовательно и по формальному критерию исходное допустимое базисное решение не является оптимальным а значит может быть улучшено.

Этап 2.

Улучшение допустимого исходного базисного решения до оптимального.

Этап представляет собой блок операций, который в общем случае используется многократно. Последовательность операций:

2.1 В выражении для целевой функции w=8x1+6x2 выбираем переменную с максимальным положительным коэффициентом (х1), ее, как обеспечивающую максимальное приращение w следует перевести в основные.

2.2. Определяем основную переменную, которая вместо х1 становится не основной. Для этого из условия не отрицательности переменных х3, х4, х5:

Поскольку значение х1 найдено с использованием третьего уравнения систему, то в неосновные переменные должна быть переведена переменная х5.

2.3. Запишем новое решение. С этой целью используя третье уравнение выразим х1 через другие переменные и полученное выражение для х1 подставим в остальные уравнения системы, а так же в целевую функцию.

Полученное решение оптимально.

Формализация логистических систем в использовании моделей систем массового обслуживания.

Модель этой системы в общем случае характеризуется множеством величин, описывающих функционирование реальной системы и образующих следующие подмножества:

1) Совокупность входных воздействий на систему

2) Совокупность внутренних (собственных) параметров системы

3) Совокупность воздействий внешней среды

4) Совокупность выходных характеристик системы

Входные воздействия, воздействия внешней среды и внутренние параметры системы обычно считают независимыми и называют экзогенными переменными. Выходные характеристики системы, являются зависимыми и называются эндогенными.

Процесс функционирования системы.

Описывается оператором Ф, который преобразует экзогенные переменные в эндогенные Y=Ф(X,D,V,T)

Данное соотношения является наиболее общим формальным описанием системы с учетом времени t.

Поскольку в модели учитываемая время, ее принято называть динамической системой. Множество векторов Z значений параметров динамической системы называют пространством состояний системы. Пусть Z=(Z1,Z2,Z3), введем пространства состояний системы:

при этом Z1=X, Z2=D, Z3=V

На рисунке показана траектория перехода системы из одного состояния в другое.

Если к пространству состояний системы добавить время то получим так называемое фазовое пространство. Динамическая система как математический объект содержит в своем описании модели:

1. Модель изменения состояний под воздействием внутренних причин

2. Модель приема входного сигнала и изменение состояния системы под воздействием этого сигнала

3. Модель формирования выходного сигнала как реакции динамической системы на внутренние и внешние причины изменения состояния

Простейшим примером динамической системы является одноканальная система массового обслуживания с отказами, например парковка с место. На один автомобиль.

Процесс функционирования данной системы описывается уравнениями Колмогорова. Построение каждого из уравнений производится по правилу:

В левой части каждого уравнения должна стоять производная вероятности состояний, а правая часть должна содержать столько членов сколько стрелок связано с данным состоянием.

Если стрелка направлена из состояния соответствующий член имеет знак -, если в состояние, знак +. Каждый член равен произведению интенсивности перехода соответствующей данной стрелки и вероятности того состояния из которого исходит стрелка.

Решение:

Лямбда- интенсивность перехода из Z0 в Z1, а ню интенсивность перехода из Z1 в Z0. Составим уравнение Колмогорова для состояния Z0. Вероятности нулевого состояния обозначим Р0 ;;;;. После интегрирования получаем;в зависимости от соотношения между лямбдой и ню возможно три случая:

≻ ≺

=

Как следует из рисунков значение вероятностей р0 и р1 при т стремящимся к бесконечности сходятся к константам, при этом . Рассмотренная модель является простейшим примером системы массового обслуживания.