Задачи линейного программирования

Содержание

 

	Введение	3
1	Линейное программирование	4
1.1	Задачи линейного программирования	4
1.2	Решение задач линейного  программирования симплекс – методом	5
1.3	Решение задач линейного  программирования графическим методом	10
2	Реализация методов  линейного программирования на практическом применении	11
2.1	Пример решения задачи линейного программирования симплекс-методом	11
2.2	Пример решения задачи линейного программирования графическим способом	14
2.3	Пример решения задачи линейного программирования с помощью MS EXCEL	16
3	Решение задач линейного  программирования	20
3.1	Решение задачи линейного  программирования графическим методом	20
3.2	Решение задачи линейного  программирования симплекс-методом	27
3.3	Решение транспортной задачи	31
	Заключение	36
	Список использованной литературы	37

 

 

 

 

 

 

 

Введение

 

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

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

Задачи:

1) рассмотреть методы  решения задач линейного программирования

2) на конкретных примерах  экономического содержания показать  все этапы нахождения оптимального  решения и его постоптимального  анализа.

3) рассмотреть проблемы  построения электронных математических моделей линейного программирования и их оптимизации с помощью надстройки «Поиск решения»

Целью курсовой работы: является изучение и применение на практике симплекс-метода и графического способа, для решения задачи линейного программирования.

1 Линейное программирование

1.1 Задачи линейного  программирования

 

Линейное программирование – наука о методах исследования и отыскания экстремумов линейной функции, на неизвестные которой  наложены линейные ограничения.

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

Экономико-математическая модель – это математическое описание экономического процесса или объекта. Реализуя их обработку на ЭВМ, мы получаем выигрыш во времени и средствах, так как проведение опытов, как правило, более трудоёмкий и дорогостоящий процесс, кроме того, не всегда возможный. Не буду здесь вдаваться в теорию моделирования, скажу лишь, что именно реализация исследования экономических процессов с помощью ЭВМ для нас и представляет интерес, а проявляется это в машинном решении задач линейного программирования, которые в свою очередь и являются экономико-математическими моделями. [2]

Все задачи линейного  программирования можно разделить  на следующие группы:

• Задачи об использовании ресурсов, сырья, планирования производства
• Задачи составления рациона
• Задачи об использовании мощностей, загрузке оборудования
• Задачи о раскрое материалов
• Транспортные задачи

 

 

 

1.2 Решение задач линейного  программирования симплекс –  методом

 

Сущность линейного программирования состоит в нахождении точек наибольшего  или наименьшего значения некоторой  функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи. [3]

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

Общая форма задачи линейного программирования формулируют следующим образом:

a₁₁x₁+a₁₂x₂+ … +a_1nx_n {≤, ≥, =}

a₂₁x₁+a₂₂x₂+ … +a_2nx_n {≤, ≥, =}                                                                      (1)

………

a_m1x₁+a_m2x₂+ … +a_mnx_n {≤, ≥, =} 

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0                                                                                           (2)

F = c₁x₁ + c₂x₂ + … + c_nx_n → max                                                                    (3)

 

Коэффициенты ai, j, bi, cj, j = 1, 2,…, n, i =1, 2,…, m – любые действительные числа (возможно 0).

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

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

В канонической форме  задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит  только из равенств (уравнений). При  этом переменные задачи х1, х2,…, хn являются неотрицательными:

 

a₁₁x₁+a₁₂x₂+ … +a_1nx_n =b₁

a₂₁x₁+a₂₂x₂+ … +a_2nx_n =b₂

………                                                                                             (4)

a_m1x₁+a_m2x₂+ … +a_mnx_n =b_n

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0                                                                                  (5)

F = c₁x₁ + c₂x₂ + … + c_nx_n → max(min)                                                            (6)

 

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

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» – со знаком «–»

a₁₁x₁+a₁₂x₂+ … +a_1nx_n                                                                                                                                                   (7)

Вводим переменную x_n+1=b₁ – a₁₁x₁-a₁₂x₂+ … +a_1nx_n

Тогда неравенство  запишется в виде:

a₁₁x₁+a₁₂x₂+ … +a_1nx_n +x_n

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

2. Если в исходной  задаче некоторая переменная  не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных

 

xk = xk- xk ≥ 0, xl

l – свободный индекс

 

3. Если в ограничениях  правая часть отрицательна, то  следует умножить это ограничение  на (-1)

4. Наконец, если исходная  задача была задачей на минимум,  то введением новой целевой  функции F1 = – F мы преобразуем  нашу задачу на минимум функции  F в задачу на максимум функции  F1.

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

В стандартной форме  задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система  ограничений ее состоит из одних  линейных неравенств типа «<=» или  «>=». Все переменные задачи неотрицательны.[2]

a₁₁x₁+a₁₂x₂+ … +a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+ … +a_2nx_n ≤ b₂

………                                                                                                                     (8)

a_m1x₁+a_m2x₂+ … +a_mnx_n ≤ b_n

F = c₁x₁ + c₂x₂ + … + c_nx_n → max

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0

 

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

a_i1x₁+a_i2x₂+ … +a_inx_n =b_i =>

• a_i1x₁+a_i2x₂+ … +a_inx_n ≤ b_i,

          - a_i1x₁-a_i2x₂-… – a_inx_n ≤ b_i

 

Идея симплекс-метода заключается в последовательном улучшении первоначального плана путем упорядоченного перехода от одного опорного плана к другому и завершается нахождением оптимального плана. Симплекс-методом решаются только канонические задачи линейного программирования. Решение канонической задачи симплекс-методом существенно облегчается применением так называемых симплексных таблиц. Всякую каноническую задачу можно записать условно в виде таблицы. Таблица заполняется следующим образом: первые т строк содержат в условной форме уравнения системы ограничений, разрешенные относительно базисных переменных. В последней строке записана целевая функция, эта строка называется F – строкой. В столбцах записаны свободные переменные и свободные члены. [1]

Условие оптимальности  плана: если ЗЛП на максимум, то в F-строке не должно быть отрицательных элементов; если ЗЛП на минимум, то в F-строке не должно быть положительных элементов.

Алгоритм решения:

1. Исходную задачу линейного программирования приводим к каноническому виду путем введения базисных переменных.
2. Базисные переменные выражаем через свободные переменные.
3. Строим начальный план, полагая свободные переменные равными 
   нулю, тогда базисные переменные будут равны свободным членам.
4. Строим первую симплекс-таблицу.
5. Проверяем план на оптимальность. Если план не оптимален, то его улучшаем.
3. Улучшение плана.

а) выбор разрешающего столбца: для этого в F – строке выбираем максимальный по абсолютной величине из отрицательных элементов, если задача на максимум, или, максимальный из положительных элементов, если задача на минимум. Пусть это будет столбец с номером s;

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