Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
Краткое сожержание материала:

• СОДЕРЖАНИЕ
• ВВЕДЕНИЕ
• 1. Геометрический метод решения задач ЛП
• 2. Симплекс-метод
• 2.1 Идея симплекс-метода
• 2.2 Реализация симплекс-метода на примере
• 2.3 Табличная реализация простого симплекс-метода
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Тема моей работы касается решения задач, возникающих в экономике. При этом встает вопрос о выборе наилучшего в некотором смысле варианта решения. А на поиск возможного варианта часто влияют разного рода факторы, сужающие рамки выбора. Иначе говоря, требуется решить задачу оптимизации, которая состоит в необходимости выбора наилучшего варианта решений среди некоторого, как правило, ограниченного множества возможных вариантов.

Задача оптимизации может быть сформулирована на языке математики, если множество доступных вариантов удается описать с помощью математических соотношений (равенств, неравенств, уравнений), а каждое решение - оценить количественно с помощью некоторого показателя, называемого критерием оптимальности или целевой функцией. Тогда наилучшим решением будет то, которое доставляет целевой функции наибольшее или наименьшее значение, в зависимости от содержательного смысла задачи. Так, например, при инвестировании ограниченной суммы средств в несколько проектов естественной является задача выбора тех проектов, которые могут принести в будущем наибольшую прибыль. При доставке в магазины продукции от различных поставщиков возникает задача минимизации транспортных затрат.

Процесс формализации задачи называется построением ее математической модели. Он состоит из трех этапов.

1. Выбор параметров задачи, от которых зависит решение. Эти параметры называют управляющими переменными и обозначают , формируя из них вектор . Принять решение - это значит задать конкретные значения переменных.

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

3. Описание всего множества X допустимых значений переменных - ограничений, связанных с наличием материальных ресурсов, финансовых средств, технологическими возможностями и т.п..

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

.

1. Геометрический метод решения задач ЛП

Этот метод часто используется при решении задач, в которых только две неизвестных величины. Разберем его на следующих примерах:

Пример 1.1. (Задача о производстве красок).

Небольшая фабрика изготовляет два вида красок: INT - для внутренних работ и EXT - для наружных работ. В производстве красок используются два исходных продукта А и В. Из-за малой площади склада максимально возможные суточные запасы этих продуктов равны 6 т. и 8 т. соответственно. На производство 1 тонны краски INT расходуется 1 тонна продукта А и 2 тонны продукта В, а на изготовление 1 тонны краски EXT идет 2 тонны продукта А и 1 тонна продукта В. Фабрика продает краску по цене 3 тыс. долл. за тонну краски INT и 2 тыс. долл. за тонну краски EXT. Исходные данные удобно свести в таблицу:

Исходные продукты	Расход продукта на 1 т. краски	Запас продуктов
	INT	EXT
A	1	2	6
B	2	1	8
Цена 1т. краски	3 тыс. долл.	2 тыс. долл.

Изучение рынка сбыта показало, что суточный спрос на краску EXT никогда не превышает спрос на краску INT, более чем на 1 тонну. Какое количество краски каждого вида должна производить фабрика в сутки, чтобы доход от реализации продукции был максимален?

Построим математическую модель задачи. Для этого надо определить переменные задачи, целевую функцию и ограничения, которым удовлетворяют переменные. Обозначим через x₁ - планируемый суточный объем производства краски INT, а через x₂ - суточный объем производства краски EXT. Целевая функция f(x) будет выражать суточный доход от продажи краски, равный 3x₁ + 2x₂ (тыс. долл.). Этот доход подлежит максимизации

f(x)= 3x₁ + 2x₂ max.

Построим ограничения задачи, связанные с ограниченными запасами продуктов А и В. На производство краски INT в количестве x₁ (т) будет использовано 1x₁ (т) продукта А, а на производство краски EXT в объеме x₂ (т) будет затрачено 2x₂ (т) продукта А. Поскольку суточный запас продукта А равен 6 т., то расход продукта А на изготовление красок двух видов не может превышать в сутки этой величины: 1x₁+ 2x₂ 6. Аналогично получим ограничение, связанное с запасом продукта В: 2x₁+1x₂ 8. Ограничение по соотношению спроса на краски можно описать неравенством: x₂ - x₁ 1. Учитывая естественные условия неотрицательности объемов выпуска продукции, окончательно получим следующую задачу линейного программирования

f(x) = 3 x₁ + 2 x₂ max (1.1)

1 x₁ + 2 x₂ 6, (1.2)

2 x₁ + 1 x₂ 8, (1.3)

- x₁ + x₂ 1, (1.4)

x₁ 0, x₂ 0. (1.5)

Построим множество планов задачи, описываемое ограничениями (1.2)-(1.5). Рассмотрим первое неравенство. Оно задает некоторую полуплоскость, расположенную по одну сторону от граничной прямой

p₁: 1x₁+2x₂=6

Построим эту прямую на плоскости с координатными осями x₁ и x₂. Для проведения прямой достаточно знать две ее точки. Проще всего найти точки пересечения прямой с осями координат. Полагая x₁ = 0, из уравнения прямой получим x₂ = 3, а при x₂ = 0 найдем x₁ = 6. Таким образом прямая p₁ пройдет через точки (0,3) и (6,0). Чтобы определить, по какую сторону от прямой расположена искомая полуплоскость, достаточно подставить в неравенство (1.2) координаты любой точки плоскости. Если прямая не проходит через начало координат, то удобнее всего взять точку (0, 0). Очевидно, что в этой точке неравенство (1.2) строго выполняется (1* 0 + 2* 0 < 6), значит полуплоскость, определяемая этим неравенством, лежит ниже прямой p₁, включая в себя начало координат. Искомую полуплоскость отметим штриховкой (рис.1.1).

Аналогично построим полуплоскость, задаваемую неравенством (1.3). Для этого нанесем на координатную плоскость граничную прямую

p₂: 2x₁+x₂=8,

найдя ее точки пересечения с осями координат: (0,8) и (4,0).

Подставляя координаты точки (0,0) в неравенство (2.3), видим, что начало координат лежит в искомой полуплоскости (2* 0 + 1* 0 < 8), значит все точки, удовлетворяющие неравенству (2.3), расположены левее прямой p₂. Отметим эту область штриховкой (рис.1.1).

Точки, задаваемые ограничением (4), находятся ниже прямой

p₃: -x₁+x₂=1,

проходящей через точки (0, 1) и (-1, 0).

Наконец, условия неотрицате...