Размещено на http://www.allbest.ru/

3

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Смоленский гуманитарный университет

Курсовая работа

РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДАМИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Смоленск 2011

Содержание

Введение

1. Общая постановка задачи линейного программирования (ЛП)

2. Примеры экономических задач, приводящихся к задачам ЛП

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

4. Симплексный метод решения задач ЛП

5. Теоремы двойственности и их использование в задачах ЛП

6. Транспортная задача и её решение методом потенциалов

7. Решение задач ЛП с использованием программы (Simplex)

Заключение

Литература

Введение

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

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

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

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

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

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

задача решение линейное программирование симплекс

1. Общая постановка задачи линейного программирования (ЛП)

Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе принят ряд специальных форм записи задачи ЛП:

1. Форма общей задачи ЛП (задача ЛП со смешанными ограничениями) - найти максимум по переменным линейного функционала c1x1 + c2x2 > max при линейных ограничениях

A11x1 + A12x2 ? b1, A21x1 + A22x2 = b2,x1 ? 0.

Здесь, матрицы A11, A12, A21, A22 имеют соответственно размеры (m1 Ч n1), (m1 Ч n2), (m2 Ч n1), (m2 Ч n2).

2. Форма основной задачи ЛП: (c, x) > maxпри линейных ограничениях Ax ? b. Здесь - матрица размера (m Ч n).

3. Стандартная форма записи задачи ЛП: (c, x) > maxпри линейных ограничениях Ax ? b и x ? 0. Здесь - матрица размера (m Ч n).

4. Каноническая форма записи задачи ЛП: (c, x) > maxпри линейных ограничениях Ax = b и x ? 0.

Формально говоря, задачи 2-4 являются частными случаями общей задачи 1. Однако в свою очередь общая задача может быть представлена в форме любой из трех остальных. Так задача 1 принимает основную форму, если заменить в ней систему ограничений-равенств на эквивалентную систему ограничений-неравенств

A₂₁x₁ + A₂₂x₂ ? b₂

A₂₁x₁ - A₂₂x₂ ? -b₂

Если сделать замену переменных

x₂ = y₂ - z₂, y₂ ? 0, z₂ ? 0, то задача 1 примет стандартную форму. Если же ограничения неравенства в задаче 1 записать в виде A₁₁x₁ + A₁₂x₂ + u = b₁, где - дополнительная переменная(формально входящая в целевой функционал с нулевым коэффициентом) и вновь использовать замену переменных, то задача 1 будет иметь форму канонической задачи. Вообще, любую задачу ЛП, на минимум или максимум, с неравенствами, направленными в ту или иную сторону, можно представить в любой из указанных форм. Для этого, наряду с приемами, перечисленными выше, необходимо использовать умножение целевой функции или ограничений-неравенств на (-1), что позволяет переходить от максимизации к минимизации и менять знаки неравенств.

2. Примеры экономических задач, приводящихся к задачам ЛП

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

Рассмотрим некоторые из них.

Определение оптимального ассортимента. Имеются m видов ресурсов в количествах b1, b2,., b_i, b_m и n видов изделий. Задана матрица A=||a_ij||, i=1,.,m, j=1,.,n, где a_ij характеризует нормы расхода i-го ресурса на единицу j-го вида изделий. Эффективность производства j-го вида изделий характеризуется показателем C_j, удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.

Обозначим количество единиц k-го вида изделий, выпускаемых предприятием, через x_k, . Тогда математическая модель этой задачи будет иметь такой вид:

 (3.1)

при ограничениях

(3.2)

Кроме ограничений на ресурсы (3.2) в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции , x_i: x_j: x_k = b_i: b_j: b_k для всех i, j, k и т.д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются m видов взаимозаменяемых ресурсов а₁, а₂,., а_m, используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены, составляют b₁, b₂,., b_i, b_n единиц. Заданы числа , указывающие, сколько единиц j-й работы можно получить из единицы і-го ресурса, а также C_ij - затраты на производство j-й работы из единицы i-го ресурса.

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

Данная задача называется общей распределительной задачей. Количество единиц i-го ресурса, которое выделено на выполнение работ j-го вида, обозначим через x_ij.

Математическая модель рассматриваемой задачи такова:

(3.3)

при ограничениях

 (3.4)

(3.5)

Ограничение (3.4) означает, что план всех работ должен быть выполнен полностью, а (3.5) означает, что ресурсы должны быть израсходованы целиком.

Примером этой задачи может быть задача о распределении самолетов по авиалиниям.

Задача о смесях. Имеется р компонентов, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит q веществ. Количество k-го вещества k = 1, 2,., q, входящее в состав единицы і-го компонента и в состав единицы смеси, обозначим через а_ik и а_k соответственно.

Предположим, что а_k зависит от а_ik линейно, то есть если смесь состоит из x₁ единиц первого компонента, x₂ - единицу второго компонента и т.д., то

Задано р величин C_i, характеризующих стоимость, массу или калорийность единицы i-го компонента, и q величин b_k, указывающих минимально необходимое процентное содержание k-го вещества в смеси. Обозначим через x₁, x₂,.,x_р значение компонента р-го вида, входящего в состав смеси.

Математическая модель этой задачи имеет такой вид:

(3.6)



при ограничении

(3.7)

Ограничение (3.7) означает, что процентное содержание k-го вещества в единице смеси должно быть не меньше b_k.

К этой же модели принадлежит также задача определения оптимального рациона кормления скота.

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

Необходимо найти минимальное значение целевой функции F = 4x₁+18x₂ > min, при системе ограничений:

x₁+4x₂?14(1)

X₁+6x₂?15(2)

X₁+x₂?5(3)

X₁?0(4) X₂?0(5)

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

Границы области допустимых решений

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = 4x₁+18x₂ > min.

Построим прямую, отвечающую значению функции F = 0: F = 4x₁+18x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений представляет собой треугольник.

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

X₁+4x₂?14

X₁+6x₂?15

Решив систему уравнений, получим: x₁ = 12, x₂ = 0.5

Откуда найдем минимальное значение целевой функции:

F(X) = 4*12 + 18*0.5 = 57

4. Симплексный метод решения задач ЛП

Вид сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		P1	P2	P3	P4
S1	4	1	1	1	3
S2	18	2	4	6	1
Прибыль от единицы продукции	9	14	15	5

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

Определим максимальное значение целевой функции F(X) = 9x₁ + 14x₂ + 15x₃ + 5x₄ при следующих условиях ограничений.

x₁ + x₂ + x₃ + x₄?4

2x₁ + 4x₂ + 6x₃ + x₄?18

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x₅. В 2-м неравенстве смысла (?) вводим базисную переменную x₆.

1x₁ + 1x₂ + 1x₃ + 1x₄ + 1x₅ + 0x₆ = 4

2x₁ + 4x₂ + 6x₃ + 1x₄ + 0x₅ + 1x₆ = 18

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

Решим систему уравнений относительно базисных переменных:

x₅, x₆,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,4,18)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6
x5	4	1	1	1	1	1	0
x6	18	2	4	6	1	0	1
F(X0)	0	-9	-14	-15	-5	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:

min (4 : 1 , 18 : 6 ) = 3

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x5	4	1	1	1	1	1	0	4
x6	18	2	4	6	1	0	1	3
F(X1)	0	-9	-14	-15	-5	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 1 войдет переменная x₃ .

Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₆ плана 0 на разрешающий элемент РЭ=6

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₃ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃ .

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
4-(18 * 1):6	1-(2 * 1):6	1-(4 * 1):6	1-(6 * 1):6	1-(1 * 1):6	1-(0 * 1):6	0-(1 * 1):6
18 : 6	2 : 6	4 : 6	6 : 6	1 : 6	0 : 6	1 : 6
0-(18 * -15):6	-9-(2 * -15):6	-14-(4 * -15):6	-15-(6 * -15):6	-5-(1 * -15):6	0-(0 * -15):6	0-(1 * -15):6

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x5	1	2/3	1/3	0	5/6	1	-1/6
x3	3	1/3	2/3	1	1/6	0	1/6
F(X1)	45	-4	-4	0	-21/2	0	21/2

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (1 : ¹/₃ , 3 : ²/₃ ) = 3

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (¹/₃) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x5	1	2/3	1/3	0	5/6	1	-1/6	3
x3	3	1/3	2/3	1	1/6	0	1/6	41/2
F(X2)	45	-4	-4	0	-21/2	0	21/2	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x₂ .

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=¹/₃

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂ .

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

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
1 : 1/3	2/3 : 1/3	1/3 : 1/3	0 : 1/3	5/6 : 1/3	1 : 1/3	-1/6 : 1/3
3-(1 * 2/3):1/3	1/3-(2/3 * 2/3):1/3	2/3-(1/3 * 2/3):1/3	1-(0 * 2/3):1/3	1/6-(5/6 * 2/3):1/3	0-(1 * 2/3):1/3	1/6-(-1/6 * 2/3):1/3
45-(1 * -4):1/3	-4-(2/3 * -4):1/3	-4-(1/3 * -4):1/3	0-(0 * -4):1/3	-21/2-(5/6 * -4):1/3	0-(1 * -4):1/3	21/2-(-1/6 * -4):1/3

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x2	3	2	1	0	21/2	3	-1/2
x3	1	-1	0	1	-11/2	-2	1/2
F(X2)	57	4	0	0	71/2	12	1/2

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x2	3	2	1	0	21/2	3	-1/2
x3	1	-1	0	1	-11/2	-2	1/2
F(X3)	57	4	0	0	71/2	12	1/2

Оптимальный план можно записать так:

x₂ = 3

x₃ = 1

F(X) = 14*3 + 15*1 = 57

5. Теоремы двойственности и их использование в задачах ЛП

Исходная задача:

при ограничениях:

Двойственной является следующая задача:

при ограничениях:

Число неизвестных в двойственной задаче равно 2. Следовательно, решение двойственной задачи можно найти графическим методом.

Построим систему координат и проведём прямые, ограничивающие область допустимых решений (ОДР). Для этого в неравенствах системы ограничений и условиях неотрицательности переменных () знаки неравенств заменим на знаки равенств, и для каждой прямой зададим координаты двух точек:

Построим вектор целевой функции W.

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

Далее, среди всех точек области допустимых решений (ОДР) надо найти такую точку, в которой целевая функция W имеет минимальное значение.

Уравнение при фиксированном значении W определяет прямую, а при изменении значения W - семейство параллельных прямых, которые называются линиями уровня для функции W.

Будем перемещать линию уровня (например, ) по ОДР параллельно самой себе в направлении вектора до тех пор, пока она не пройдёт через первую общую точку с ОДР. Координаты этой точки и являются оптимальным решением данной задачи.

Для нахождения координат необходимо решить систему линейных уравнений соответствующих прямым, пересекающимся в данной точке. У нас 4 точки: А, В, С, Д .

Найдём координаты точки А. Для этого решим систему, составленную из уравнений (4) и (5):

А (0; 5)

Подставим координаты точки А в целевую функцию:

Найдём координаты точки В. Для этого надо решить систему, составленную из уравнений (3) и (4):

В (3; 2)

Подставим найденные значения в целевую функцию:

Найдём координаты точки С. Для этого решим систему, составленную из уравнений (3) и (2):



С (12; 1/2)

Подставим найденные координаты точки С в целевую функцию:

Найдём координаты точки Д. Для этого решим систему, составленную из уравнений (3) и (6):

Д (15; 0)

Подставим найденные координаты точки Е в целевую функцию:

Среди всех найденных значений целевых функций выбираем наименьшую.

Функция W принимает минимальное значение в точке Д; .

Решим данную задачу, используя теорему двойственности

т.к. y₁>0, то х₁+х₂+х₃+3х₄=4

т.к. y₂>0, то 2х₁+4х₂+6х₃+х₄=18

F(x)=G(y)= 57 - первая теорема двойственности выполнена, приведенный в условии план является оптимальным.

Проанализируем использование ресурсов:

Подставим y₁ и y₂ в систему ограничений двойственной задачи.



Оставим систему с x₃ и x₂:

F(x) = 9*0 + 14*3 + 15*1 + 5*0=57

Теорема двойственности.

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

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

6. Транспортная задача и её решение методом потенциалов

Математическая модель транспортной задачи:

F = ??c_ijx_ij, (1)

при условиях:

?x_ij = a_i, i = 1,2,…, m, (2)

?x_ij = b_j, j = 1,2,…, n, (3)

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

	1	2	3	4	Запасы
1	5	4	3	4	88
2	3	2	5	5	77
3	1	6	3	2	33
Потребности	44	44	33	44

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

?a = 88 + 77 + 33 = 198

?b = 44 + 44 + 33 + 44 = 165

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 33 (198--165). Тарифы перевозки единицы груза из базы во все магазины полагаем, равны нулю.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	5	4	3	4	0	88
2	3	2	5	5	0	77
3	1	6	3	2	0	33
Потребности	44	44	33	44	33

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

Искомый элемент равен 1

Для этого элемента запасы равны 33, потребности 44. Поскольку минимальным является 33, то вычитаем его.

x₃₁ = min(33,44) = 33.

5	4	3	4	0	88
3	2	5	5	0	77
1	x	x	x	x	33 - 33 = 0
44 - 33 = 11	44	33	44	33	0

Искомый элемент равен 2

Для этого элемента запасы равны 77, потребности 44. Поскольку минимальным является 44, то вычитаем его.

x₂₂ = min(77,44) = 44.

5	x	3	4	0	88
3	2	5	5	0	77 - 44 = 33
1	x	x	x	x	0
11	44 - 44 = 0	33	44	33	0

Искомый элемент равен 3

Для этого элемента запасы равны 88, потребности 33. Поскольку минимальным является 33, то вычитаем его. x₁₃ = min(88,33) = 33.

5	x	3	4	0	88 - 33 = 55
3	2	x	5	0	33
1	x	x	x	x	0
11	0	33 - 33 = 0	44	33	0

Искомый элемент равен 3

Для этого элемента запасы равны 33, потребности 11. Поскольку минимальным является 11, то вычитаем его.

x₂₁ = min(33,11) = 11.

x	x	3	4	0	55
3	2	x	5	0	33 - 11 = 22
1	x	x	x	x	0
11 - 11 = 0	0	0	44	33	0

Искомый элемент равен 4

Для этого элемента запасы равны 55, потребности 44. Поскольку минимальным является 44, то вычитаем его.

x₁₄ = min(55,44) = 44.

x	x	3	4	0	55 - 44 = 11
3	2	x	x	0	22
1	x	x	x	x	0
0	0	0	44 - 44 = 0	33	0

Искомый элемент равен 0

Для этого элемента запасы равны 11, потребности 33. Поскольку минимальным является 11, то вычитаем его.

x₁₅ = min(11,33) = 11.

x	x	3	4	0	11 - 11 = 0
3	2	x	x	0	22
1	x	x	x	x	0
0	0	0	0	33 - 11 = 22	0

Искомый элемент равен 0

Для этого элемента запасы равны 22, потребности 22. Поскольку минимальным является 22, то вычитаем его.

x₂₅ = min(22,22) = 22.

x	x	3	4	0	0
3	2	x	x	0	22 - 22 = 0
1	x	x	x	x	0
0	0	0	0	22 - 22 = 0	0

	1	2	3	4	5	Запасы
1	5	4	3[33]	4[44]	0[11]	88
2	3[11]	2[44]	5	5	0[22]	77
3	1[33]	6	3	2	0	33
Потребности	44	44	33	44	33

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*33 + 4*44 + 0*11 + 3*11 + 2*44 + 0*22 + 1*33 = 429

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3

u₁ + v₄ = 4; 0 + v₄ = 4; v₄ = 4

u₁ + v₅ = 0; 0 + v₅ = 0; v₅ = 0

u₂ + v₅ = 0; 0 + u₂ = 0; u₂ = 0

u₂ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₃ + v₁ = 1; 3 + u₃ = 1; u₃ = -2

u₂ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

	v1=3	v2=2	v3=3	v4=4	v5=0
u1=0	5	4	3[33]	4[44]	0[11]
u2=0	3[11]	2[44]	5	5	0[22]
u3=-2	1[33]	6	3	2	0

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 3*33 + 4*44 + 0*11 + 3*11 + 2*44 + 0*22 + 1*33 = 429

7. Решение задач ЛП с использованием программы (Simplex)

Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга задач и довольно таки прост в применении. Но у этого метода есть один недостаток - для решения задачи иногда следует выполнить множество итераций.

Решение задачи симплексным методом можно выполнить гораздо проще, если использовать для этого специальное программное обеспечение, например MS Excel. Но Excel решает задачи симплексным методом, показывая в качестве результата последнюю таблицу расчета, опуская промежуточные таблицы, анализировать которую приходится уже человеку, что не очень удобно.

Программа Simplex позволяет просматривать промежуточные результаты.

Решим при помощи этой программы симплексную таблицу.



Что соответствует найденному ранее решению.

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

Решим при по мощи этой программы транспортную задачу.



Что соответствует найденному ранее решению.

Заключение

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

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

Литература

1. Карпелович Ф.И., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. - М.: Физматгиз, 1963.

2. Коротков М., Гаврилов М. «Основы линейного программирования», 2003.

3. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980.

4. Нестеров Е.П. Транспортные задачи линейного программирования. - М.: Транспорт, 1971.

5. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998.

6. Теха Х. «Введение в исследование операций», Издательский дом «Вильямс», 2001.

7. Филькин Г.В., «Линейное программирование» (лекции), Шахты, 2007.

8. Экономико-математическое моделирование. Учеб. для ВУЗов / Под ред. А.Д. Дрогобыцкого. - М.: Экзамен, 2004.

Размещено на Allbest.ru