Министерство образования и науки Российской Федерации

ФГОУ СПО «Псковский колледж строительства и экономики»
Предмет «Математические методы»


Решение задач

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


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

студента группы 320-ПО

Хруцкого Максима Игоревича

Руководитель курсовой работы

Васильева Наталья Анатольевна

Псков, 2011

Содержание
Введение
Глава 1 Симплексный метод решения задач линейного программирования

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

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

1.3 Алгоритм решения задачи линейного программирования симплексным методом

1.4 Решение задачи симплексным методом

1.5 Вывод
Глава 2 Транспортная задача линейного программирования

2.1 Транспортная задача

2.2 Особенности транспортной задачи ограничениями на пропускную способность

2.3 Алгоритм решения транспортной задачи

2.4 Методы построения начального опорного решения

2.5 Метод потенциалов

2.6 Переход от первого опорного решения к другому

2.7 Решение транспортной задачи

2.8 Вывод
Заключение
Литература


Введение


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

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а

«линейное планирование», что более точно отражает содержание дисциплины.

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

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

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

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

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

Глава 1 Симплексный метод решения задач

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

Составление математической модели включает:

• 
  выбор переменных задачи;
  
• 
  составление системы ограничений;
  
• 
  выбор целевой функции.
  

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

Для изготовления n-видов продукции P₁;P₂;…;Pn используется m-видов сырья (ресурсов) S₁; S₂; …; S_m. Расход ресурсов на единицу каждого вида продукции известен a(i = 1, 2, …, m; j = 1, 2, …, n). Также известна прибыль от реализации продукции каждого вида C₁; C₂; …; C_n. Требуется составить план выпуска продукции обеспечивающий максимальную выгоду.

Составим математическую модель этой задачи:

1. 
   Выбираем переменные задачи: пусть х₁; х₂; …; x_n – это количество продукции каждого вида, причем х_j ≥ 0.
   
2. 
   Составляем систему ограничений задачи: ограничения задачи связаны с ресурсами имеющимся в наличии, поэтому система будет содержать m-ограничений по каждому ресурсу.
   

Ресурсы	Расход ресурсов на производство единицы продукции				Запас ресурсов
	P1	P2	…	Pn
S1	a11	a12	…	a1n	b1
S2	а21	a22	…	a2n	b2
…	…	…	…	…	…
Sm	a	a	…	a	b
Прибыль	c1	c2	…	cn	max

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

“≤” ставится, т.к мы не можем израсходовать ресурсов больше, чем имеется в наличии, следовательно, аналогично и для остальных ресурсов.

S₂:a₂₁x₁+a₂₂x₂+…+a_mnx_n≤b

S_m: a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m

3. 
   Целевая функция.
   

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

Z(x)=c1x₁+c₂x₂+…+c_nx_n max

Таким образом, математическая модель этой задачи имеет вид:

найти такой план  X=(х₁, х₂, ..., х_n) выпуска продукции удовлетворяющий системе ограничений :



и условию неотрицательности х_j ≥ 0, при котором целевая функция

Z(x)=c1x₁+c₂x₂+…+c_nx_n max

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

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

Таким образом, каноническая форма имеет вид:

Z(x)= c₁x₁+c₂x₂+…+c_nc_n extrem




a₁₁x₁+…+a_1nxn=b₁

- - - - - -

a_m1x₁+…+a_mnx_n=b_m


xj0 (j=1n)


Если система содержит неравенства, то от неравенства к уравнению переходят следующим образом:

Вводят дополнительные переменные в левые части неравенства;

• 
  если знак неравенства “≤”, то переменная берется с коэффициентом “+1”;
  
• 
  если знак “≥”, то дополнительная переменная “-1”.
  

В целевую функцию эти переменные записываются с нулевыми коэффициентами.

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


1.3. Алгоритм симплексного метода

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

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

Макет симплексной таблицы

Б	Zб	С0	С1	С2	…	Сп	ст+1	…	Сп+т
		А0	А1	А2	…	Ап	Ап+1	…	Ап+т
					…			…
					…			…
					…			…
					…			…
Δк					…			…

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

Проверяем начальное опорное решение на оптимальность. Индексная строка находится по формуле Δ_к =∑С_бА_j-с_j. При решении задачи возможны следующие случаи:

1) при решении задачи на максимум:

а) все оценки Δ _к > О, тогда найденное решение оптимальное;

б) хотя бы одна оценка Δк < 0, но при соответствующей переменной нет ни одного положительного коэффициента, тогда решение задачи прекращаем, т.к. тах Z(Х) = ∞, т.е. целевая функция не ограничена в области допустимых решений;

в) хотя бы одна оценка Δк < 0 и при соответствующей переменной есть хотя бы один

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

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

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

При решении задачи на максимум:

а) ключевым столбцом является столбец соответствующий наименьшей отрицательной оценке А_к в индексной строке;

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

столбца, т.е.

тiп Θ
= A₀

{положит.эл.кл.столбца}

в) ключевым элементом является число, расположенное на пересечении ключегого столбца и ключевой строки;

5.Заполняем следующую симплексную таблицу.

а) переписываем ключевую строку, разделив ее на ключевой элемент;

б) заполняем базисные столбцы;

в) остальные коэффициенты таблицы находим по правилу «прямоугольника».

Правило «прямоугольника» заключается в следующем:

соотв.эл.кл.столбца х соотв.эл.кл.строки

новы
й эл.=старый эл

ключевойэлемент

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

6.Возвращаемся к третьему шагу алгоритма.
1.4. Решение задачи симплексным методом

Предприятие изготавливает три вида станков I, II, III. При этом расходуются сырье, трудовые ресурсы и учитываются накладные расходы.

Известно, что для изготовления станка I-го вида требуется по1 ед. сырья, трудовых ресурсов и накладных расходов; для станка II-го вида – 2 ед. сырья, 1 ед. трудовых ресурсов и 2 ед. накладных расходов; для станка III-го вида – 3 ед. сырья, 1 ед. трудовых ресурсов и 6 ед. накладных расходов. Предприятие может обеспечить 15 ед. сырья, 12 ед. трудовых ресурсов и 14 ед. накладных расходов. Прибыль от реализации станка I вида 5 тыс. руб., II вида – 9 тыс. руб., III вида – 8 тыс.руб.

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

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

Запишем условие задачи в виде таблицы:

Ресурсы	Количество ресурсов затраченных на производство станка каждого вида			Запас сырья
	I	II	III
Сырье	1	2	3	15
Трудовые ресурсы	1	1	1	12
Накладные расходы	1	2	6	14
Прибыль(тыс.руб)	5	9	8	max

Составляем математическую модель задачи.

Вводим переменные:

Пусть x₁; x₂; x₃ – количество станков каждого вида, причем х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0.

Составляем систему ограничений:

S₁:1х₁+2х + 3х3≤15

Знак “≤” ставим потому, что мы не можем использовать ресурсов больше, чем имеется в наличии.

S₂:1х₁+1х₂+1х₃=12

Знак “=” ставим потому, что условие задачи требует, чтобы трудовые ресурсы были использованы полностью.

S₃:1х₁+2х₂+6х₃≥14

Знак “≥” ставим потому, что условие задачи требует, чтобы накладные расходы были не менее указанных.

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

Z(x)=5x₁+9x₂+8x₃ max

Таким образом, математическая модель этой задачи имеет вид: найти такой план X=(х₁, х₂, ...,х_n) производства станков, удовлетворяющий стстеме ограничений:



хj≥0 (j=1,2,3), при Z(x)=5x₁+9x₂+8x₃ max
Приводим задачу к канонической форме. Для этого в систему ограничений вводим дополнительные переменные, чтобы уравнять правые и левые части: +x₄; -x₅. В целевую функцию дополнительные переменные входят с нулевыми коэффициентами.

Таким образом, каноническая форма задачи:

Z(x)=5x1+9x2+8x3+0x4+0x5 max



хj>=0 (j=1,2,3);

Z(x)=5x1+9x2+8x3+0x4+0x5 max

Строим начальное опорное решение методом Гаусса.



хj>=0 (j=1,2,3);

Z(x)=5x1+9x2+8x3+0x4+0x5 max




+
×(-1)

Домножим вторую строку матрицы на (-1) и сложим ее с первой, а потом с третьей. В результате получим:


×(-5)
+
Домножим вторую строку на (-5) и сложим ее со строкой под чертой. В результате получим :


×(-1)
+
Домножим третью строку на (-1) и сложим ее с первой, а потом со второй. В результате получим:


×(-4)
+
Домножим третью строку на -4 и сложим ее со строкой под чертой. В результате получим матрицу:

x1 x2 x3 x4 x5

0 0 -3 1 1 1

1 0 -4 0 1 10

0 1 5 0 -1 2

0 0 -17 0 4 -68

Составляем симплексную таблицу.

Б	Zб	-68	0	0	-17	0	4	Ɵ
		А0	А1	А2	А3	А4	А5
X4	0	1	0	0	-3	1	1	1
X1	0	10	1	0	-4	0	1	10
X2	0	2	0	1	5	0	-1
∆k		68	0	0	17	0	-4

Проверяем решение на оптимальность, для этого вычисляем ∆_k:
∆₀= × -(-68)=68

∆₁= ×-0=0

∆₂ = × -0=0

∆₃=×-(-17)=17

∆₄=×- 0 = 0

∆₅=×-4=-4

Решение не является оптимальным, потому что ∆5<0, следовательно, его можно улучшить.

Ключевым столбцом является столбец A5, т.к. min ∆_k =-4. Ключевой строкой является строка x4, т.к min Ɵ =1. Ключевой элемент равен 1.

Заполняем следующую симплексную таблицу.

а) переписываем ключевую строку, разделив ее на ключевой элемент;

б) заполняем базисные столбцы;

в) остальные коэффициенты таблицы находим по правилу «прямоугольника»

Правило «прямоугольника» заключается в следующем:

новыйэл.=старыйэл.- соотв.эл.кл.столбца×соответств.эл.кл.строки

ключевой элемент

Б	Zб	-68	0	0	-17	0	4	Ɵ
		А0	А1	А2	А3	А4	А5
X5	4	1	0	0	0	-3	1
X1	0	9	1	0	0	-1	0
X2	0	3	0	1	1	6	0
∆k		72	0	0	0	5	0

новыйэл.=10-=9
новыйэл.=2-=2-(-1)=3
новыйэл.=0-=-1
новыйэл.=-4-=-4-(-3)=-1
новыйэл.=5-=5+1=6

новыйэл.=0-=0+1=1
Считаем ∆_k:

∆₀=× -(-68)=4+68=72

∆₁= ×-0=0

∆₂ = × -0=0

∆₃= ×-(-17)= -12-(-17)=5

∆₄=×-0=4

∆₅= ×-0=0

Т.к все ∆_k ≥ 0, то решение является оптимальным.

Ответ: max Z(Х) = 72 при Х = (9; 3; 0).
1.5 Вывод
Максимальная прибыль в размере 72 тыс. руб. достигается, если производить 9 станков I вида, 3 станка II вида и не производить станки III вида. При этом трудовые ресурсы используются полностью, сырья расходуется 15 единиц, а накладные ресурсы требуются в размере 15 единиц.


Глава 2 Транспортная задача линейного программирования
2.1Транспортная задача
Задача в которой требуется спланировать перевозку однородного груза от поставщиков к потребителям называется транспортной задачей.

Имеется однородный груз у m-поставщиков в количестве m: a₁;a₂;…;a_m. Этот груз требуется n потребителям в размерах b₁;b₂;…;b_n. Известно С_ij(i=1,m;j=1,n) стоимость перевозки 1 единицы груза от i-го поставщика к j-му потребителю, либо время на перевозку 1 единицы груза.

Требуется составить такой план перевозок, при котором:

1)все запасы поставщиков будут вывезены полностью;

2) все запросы потребителей удовлетворены полностью;

3) суммарные затраты на перевозку будут минимальными.
Условия транспортной задачи записываются в виде таблицы:

bj ai	b1	b2	….	bn
a1	c11	c12	….	c1n
a2	c21	c22	….	c2n
….	….	….	….	….
am	cm1	cm2	….	cmn

1) Выбираем переменные задачи:

Пусть x_ij- количество едениц груза перевозимого от каждого поставщика каждому потребителю. х_ij(i=;j= ) x_ij0

2) Составляем систему ограничений: система будет состоять из уравнений т.к:

а) все запасы должны быть вывезены полностью



б) все запросы должны быть удовлетворены полностью:



3) Задаем целевую функцию.

Цель задачи: перевести груз с минимальными затратами.

Z(x)=C₁₁x₁₁+C₁₂x₁₂+…+C_mnx_mnmin

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

Составить такой план перевоза Х= удовлетворяющий системе ограничений:



x_ij

Транспортные задачи делятся на две группы:

1) задачи закрытого типа или с правильным балансом:



2) задачи открытого типа или с неправильным балансом- 2 случая



а) для разрешимости задачи вводят фиктивного потребителя с запросами b_n+1=. Стоимости перевозок от каждого поставщика равна нулю.

б) общий запас меньше требуемой величины. Вводят фиктивного поставщика с запасами: a_m+1=

C_i(m+1)=0
2.2 Особенности транспортной задачи ограничениями на пропускную способность
Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l и потребителю с номером k. Возможны ограничения двух типов: 1)x_lk≥a; 2)x_lk≤b, где a и b- постоянные величины.

1. 
   Если x_lk≥ a, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы k-го потребителя на величину a (зарезервировать перевозку x_lk=а). В полученном оптимальном решении следует увеличить объем перевозки x_lk на величину а.
   
2. 
   Если x_lk≤b, то необходимо вместо k-го потребителя с запросами b_k ввести двух других потребителей. Один из них с номером k должен иметь запросы b^,_k=b, а другои с номером n+1- запросы b_n+!=b_k-b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c_l(n+1), которая принимается равной сколь угодно большому числу M (M<< 1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как c_l(n+1)=M- самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l,n+1) останется пустой (x_l(n+1)=0) и оббъем перевозки x_lk не превзойдет b.
   

2.3 Алгоритм решения транспортной задачи
1) Проверяют выполнение необходимого и достаточного условия разрешимости задачи: если задача с неправильным балансом, то вводится фиктивный поставщик или потребитель.

2) Строят начальное опорное решение. Либо методом «северо-западного угла» либо методом минимальной стоимости. Проверяют правильность заполнения клеток по количеству: их должно быть m+n-1. Проверяется линейная независимость с помощью метода вычеркивания.

3) Проверяют решение на оптимальность с помощью метода потенциалов: если решение оптимальное- записывают ответ.

4) Если решение не оптимальное, то переходят к новому опорному решению с помощью построения циклов и возвращаются к пункту 3.
2.4 Методы построения начального опорного решения
1) Метод «северо-западного угла»

Распределение груза начинается с верхней клетки таблицы. Выбирают минимальное из значений: x₁₁=min{a₁;b₁}. При этом из дальнейшего рассмотрения исключается либо поставщик, либо потребитель. Из оставшихся клеток таблицы выбирают клетку в которую записывают груз величиной:

и.т.д пока весь груз не будет распределен.

2) Метод минимальной стоимости

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


2.5. Метод потенциалов
Для каждого поставщика и потребителя находят потенциал. Для этого составляют систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы.

В системе будет (m+n-1) уравнений с (m+n) неизвестными т.е неизвестных на 1 больше, чем уравнений. Такая система имеет бесконечное множество решений, поэтому для ее решения одной из переменных дают конкретное значение (обычно U₁=0 – система будет иметь одно единственное решение).

Потенциалы записывают рядом с таблицей. Для всех не заполненных решением клеток таблицы вычисляют оценку ∆_ij=U_i+V_j-C_ij .

Если все ∆_ij≤0, то решение оптимальное. Если хотябы одна ∆_ij>0, то решение не оптимальное и его можно улучшить.
2.6. Переход от первого опорного решения к другому
Переход к новому опорному решению осуществляется с помощью цикла.

Определение: циклом называется такая последовательность клеток таблицы в которой две и только две соседних клетки расположены в первой строке или столбце, причем, первая и последняя клетки цикла также находятся в одной строке или столбце.

Цикл строится для клетки в которой наибольшая положительная оценка А_ij max{∆_ij}. В эту клетку ставится знак “+” и она добавляется к заполненным клеткам таблицы.(т.е заполненных клеток становится m+n). Затем методом вычеркивания строится цикл.

Метод вычеркивания:

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

Оставшиеся клетки таблицы после вычеркивания образуют цикл. В найденном цикле расставляются знаки “+;-“ , в нечетных клетках “+”; в четных “-“; начиная с уже поставленного знака “+”. По циклу перераспределяется груз величиной тетта Ɵ=min”-“ {x_ij}. При построении нового решения все вычеркнутые клетки переписываются без изменения. В клетках со знаком “+” величина перевозки увеличивается на Ɵ. Со знаком “-“ уменьшается на Ɵ, при этом одна из помеченных клеток останется пустой.

7. 
   Решение транспортной задачи
   

Фирма «Союз» обеспечивает доставку видео- и аудеокассет с четырех складов, расположенных в разныхточках города в четыре магазина.

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

Склады	Магазины				Запасы, тыс.шт.
	№1	№2	№3	№4
Склад №1	3	2	5	4	1000
Склад №2	4	3	5	3	1500
Склад №3	1	1	3	2	500
Склад №4	1	1	6	3	1500
	500	500	1000	1500

Однако имеются дополнительные условия : объем перевозки кассет со склада №2 магазину №3 должен быть не менее 500 тыс.шт (x₂₃≥500), а со склада №4 магазину №4 – не более 500 тыс.шт (x₄₄≤500).

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

bj ai	500	500	1000	1500	Ф 1000
1000	3	2	5	4	0
1500	4	3	5	3	0
500	1	1	3	2	0
1500	4	1	6	3	0

Проверяем баланс задачи:

∑_ai=1000+1500+500+1500=4500

∑_bj=500+500+1000+1500=3500

Т.к. ∑_ai>∑_bj, то вводим фиктивного потребителя b₅=4500-3500=1000
Требуется при решении транспортной задачи ограничить перевозки от поставщика с номером 2 и потребителю с номером 3.

Если x₂₃≥500, то необходимо прежде, чем решать задачу, сократить запасы 2-го поставщика и запросы 3-го потребителя на величину 500 (зарезервировать перевозку x₂₃=500). В полученном оптимальном решении следует увеличить объем перевозки x₂₃ на величину 500.

bj ai	500	500	500	1500	Ф 1000
1000	3	2	5	4	0
1000	4	3	5	3	0
500	1	1	3	2	0
1500	4	1	6	3	0

Если x₄₄≤500, то необходимо вместо 4-го потребителя с запросами b₄=1500 ввести двух других потребителей. Один из них с номером 4 должен иметь запросы b₄’ = 500, а другой с номером 6 с запросами b₆ = 1500-500=1000. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c₄₄, которая принимается равной сколь угодно большому числу M (M<< 1). После получения оптимального решения величины грузов, перевозимых к 6-му потребителю, прибавляются к величинам перевозок 4-го потребителя. Так как c₄₄ = M – самая большая стоимость перевозки, то в оптимальном решении клетка с номером (4,4) останется пустой (x₄₄=0) и объем перевозки x₄₄ не превзойдет 500.

bj ai	500	500	500	500*	1000Ф	1000*
1000	3 0	2 1	- 5 500	4 0	0 2 +	4 500	U1=0
1000	4 -	3 -	5 -	3 500	0 1	3 500	U2=-1
500	1 500	- 1 0	+ 3 0	2 0	0 0	2 0	U3=-2
1500	4 -	+ 1 500	6 -	3 -	- 0 1000	M -	U4=-2
V1=3	V2=3	V3=5	V4=4	V5=2	V6=4

Строим начальное решение методом минимальной стоимости.

С=

Находим значение целевой функции:

Z(x)= 2500+2000+1500+1500+500+500=8500

Для каждого поставщика и потребителя находим потенциал. Для этого составлем систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы:

U_i+V_j=C_ij;U₁=0

Пусть U₁=0, тогда:

U₁+V₃=5 => V₃=5

U₁+V₆=4 => V₆=4

U₂+V₄=3 => V₄=4

U₂+V₆=3 => U₂= -1

U₃+V₁=1 => V₁=3

U₃+V₂=1 => V₂=3

U₃+V₃=3 => U₃= -2

U₄+V₂=1 => U₄= -2

U₄+V₅= 0 => V₅=2

Для всех не заполненных решением клеток таблицы вычисляем оценку ∆_ij=U_i+V_j-C_ij .

∆₁₁=U₁+V₁-C₁₁=0+3-3=0 ≤0

∆₁₂=U₁+V₂-C₁₂=0+3-2=1 ≥0

∆₁₄=U₁+V₄-C₁₄=0+4-4=0 ≤0

∆₁₅=U₁+V₅-C₁₅=0+2-0=2 ≥0

∆₂₁=U₂+V₁-C₂₁=1+3-4=-2 ≤0

∆₂₂=U₂+V₂-C₂₂=-1+3-3=-1 ≤0

∆₂₃=U₂+V₃-C₂₃=-1+5-5=-1 ≤0

∆₂₅=U₂+V₅-C₂₅=-1+2-0=1 ≥0

∆₃₄=U₃+V₄-C₃₄=-2+4-2=0 ≤0

∆₃₅=U₃+V₅-C₃₅=-2+2-0=0 ≤0

∆₃₆=U₃+V₆-C₃₆=-2+4-2=0 ≤0

∆₄₁=U₄+V₁-C₄₁=-2+3-4=-3 ≤0

∆₄₃=U₄+V₃-C₄₃=-2+5-6=-3 ≤0

∆₄₄=U₄+V₄-C₄₄=-2+4-3=-1 ≤0

∆₄₆=U₄+V₆-C₄₆=-2+4-M=2-M ≤0

Так как ∆₂₅<0, ∆₁₂<0, ∆₁₅<0, то решение не оптимальное и его можно улучшить

Ɵ min {500;1000;0}=0

bj ai	500	500	500	500*	ф 1000	1000*
1000	3 0	2 -	5 500	4 0	0 0 +	4 - 500	U1=0 U2=-1
1000	4 -	3 -	5 -	3 500-	0 -	3 +500
500	1 500	1 -	3 0	2 0	0 -	2 0	U3=-2 U4=0
1500	4 -	1 500	6 -	3 1 +	- 0 1000	M -
	V1=3	V2=1	V3=5	V4=4	V5=0	V6=4

Z(x)=2500+2000+3000+500+500=8500

Для каждого поставщика и потребителя находим потенциал. Для этого составлем систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы:U₁=0

U₁+V₃ => V₃=5

U₁+V₅ => V₅=0

U₁+V₆ => V₆=4

U₂+V₄ => V₄=4

U₂+V₆ => U₂=-1

U₃+V₁ => V₁=3

U₃+V₃ => U₃=-2

U₄+V₂ => V₂=1

U₄+V₅ => U₄=0

Для всех не заполненных решением клеток таблицы вычисляем оценку ∆_ij=U_i+V_j-C_ij .

∆₁₁=U₁+V₁-C₁₁=0+3-3=0≤0

∆₁₂=U₁+V₂-C₁₂=0+1-2=-1≤0

∆₁₄=U₁+V₄-C₁₄=0+4-4=0≤0

∆₂₁=U₂+V₁-C₂₁=-1+3-4=-2≤0

∆₂₂=U₂+V₂-C₂₂=-1+1-3=-3≤0

∆₂₃=U₂+V₃-C₂₃=-1+5-5=-1≤0

∆₂₅=U₂+V₅-C₂₅=-1+0-0=-1≤0

∆₃₂=U₃+V₂-C₃₂=-2+1-1=-2≤0

∆₃₄=U₃+V₄-C₃₄=-2+4-2=0≤0

∆₃₅=U₃+V₅-C₃₅=-2+0-0=-2≤0

∆₃₆=U₃+V₆-C₃₆=-2+4-2=0≤0

∆₄₁=U₄+V₁-C₄₁=0+3-4=-1≤0

∆₄₃=U₄+V₃-C₄₃=0+5-6=-1≤0

∆₄₄=U₄+V₄-C₄₄=0+4-3=1≥0

∆₄₆=U₄+V₆-C₄₆=M≤0

Так как ∆₄₄<0, то решение не оптимальное и его можно улучшить

min {500;500;1000}= 500

bj ai	500	500	500	500*	ф 1000	1000*
1000	3 0	2 -	5 500	4 -	0 500	4 0	U1=0 U2=-1
1000	4 -	3 -	5 -	3 -	0 -	3 1000
500	1 500	1 -	3 0	2 -	0 -	2 0	U3=-2 U4=0
1500	4 -	1 500	6 -	3 500	0 500	M -
	V1=3	V2=1	V3=5	V4=3	V5=0	V6=4

Z(x)=2500+3000+1000+1500=8000

Для каждого поставщика и потребителя находим потенциал. Для этого составлем систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы:U₁=0

U₁+V₃=5 =>V₃=5

U₁+V₅=0 =>V₅=0

U₁+V₆=4 =>V₆=4

U₂+V₆=3 =>U₂=-1

U₃+V₁=1 =>V₁=3

U₃+V₃=3 =>U₃=-2

U₄+V₂=1 =>V₂=1

U₄+V₄=3 =>V₄=3

U₄+V₅=0 =>U₄=0

Для всех не заполненных решением клеток таблицы вычисляем оценку ∆_ij=U_i+V_j-C_ij

∆₁₁=U₁+V₁=0+3-3=0 ≤0

∆₁₂=U₁+V₂=0+1-2=-1 ≤0

∆₁₄=U₁+V₄=0+3-4=-1 ≤0

∆₂₁=U₂+V₁=-1+3-4=-2 ≤0

∆₂₂=U₂+V₂=-1+1-3=-3 ≤0

∆₂₃=U₂+V₃=-1+5-5=-1 ≤0

∆₂₄=U₂+V₄=-1+9-3=-1 ≤0

∆₂₅=U₂+V₅=-1+0-0=-1 ≤0

∆₃₂=U₃+V₂=-2+1-1=-2 ≤0

∆₃₄=U₃+V₄=-2+3-2=-1 ≤0

∆₃₅=U₃+V₅=-2+0-0=-2 ≤0

∆₃₆=U₃+V₆=-2+4-2=0 ≤0

∆₄₁=U₄+V₁=0+3-4=-1 ≤0

∆₄₃=U₄+V₃=0+5-6=-1 ≤0

В итоге получим таблицу с учетом сделанных выше ограничений:

bj ai	500	500	1000	1500	Ф 1000
1000	3	2	5 500	4 0	0 500
1000	4	3	5 500	3 1000	0
500	1 500	1	3 0	2	0
1500	4	1 500	6	3 500	0 500

Целевая функция:

Z(x)=500+500+500+5000+3000+1500=10500

Ответ: min Z(Х)= 10500 при Х =

7. 
   Вывод
   

Минимальные затраты в размере 10500 денежных единиц достигаются если обеспечить доставку видео- и аудиокассет:

1) со склада №1 в магазин №3 в количестве 500 тыс.шт.;

2) со склада №2 в магазин №3 в количестве 500 тыс.шт. и в магазин №4 в количестве 1000 тыс.шт.;

3) со склада №3 в магазин №1 500 тыс.шт.;

4) со склада №4 в магазины №2 и №4 в размере 500 тыс.шт.
Заключение
В ходе работы я решал задачу линейного программирования на составления плана производства станков с помощью построения начального решения методом Гаусса и транспортную задачу с ограничениями на пропускную способность на составление плана перевозок с минимальными затратами.

Во время решения задачи на составление плана производства станков линейного программирования симплексным методом, я выбирал переменные x₁,x₂,x₃ так как в задаче сказано о том, что в плане производства использовались станки трёх видов, причем данные переменные должны быть больше нуля. После этого я составлял систему ограничений. Следующим шагом я находил целевую функцию задачи, так как цель задачи составление плана обеспечивающий максимальную прибыль , то целевая функция должна стремится к максимальной прибыли. Следующий мой шаг заключался в приведении задачи к каноническому виду. После приведения задачи к каноническому виду, я строил начальное опорное решение методом Гаусса. Только после этого задачу можно начать решать симплексным методом. Для этого я составлял первую симплексную таблицу, после её составления я проверял решение на оптимальность. Так как ∆₅ получилось меньше нуля, то решение не оптимальное, следовательно, его можно улучшить. Для этого я находил новое опорное решение с помощью «правила прямоугольника», определял ключевой столбец и ключевую строку. После этого рассчитывал новые элементы таблицы, затем заполнял таблицу получив элементами и после этого проверял решение на оптимальность, и так как все ∆_k были больше нуля, то решение оптимальное, следовательно, наибольшее значение Z(Х) = 72, при Х = (9; 3; 0).

Во время же решения транспортной задачи с ограничениями на пропускную способность, я опирался на условие задачи и на её дополнительные условия. После этого я составлял план перевозок и проверял баланс задачи. В ходе этой проверки я выяснил, что необходимо ввести фиктивного потребителя, после этого я составлял таблицу перевозки товара. Следующим моим шагом было, выполнение дополнительных условий задачи, входе этого мне пришлось немного изменить таблицу перевозки товара. После этого я составил математическую модель транспортной задачи. После этого я задавал целевую функцию задачи, при условии того, что целью задачи является перевозка необходимой продукции с минимальными затратами. Проверял решение на оптимальность, то есть ∆_(ij ) должно было быть меньше нуля, но так как данное условие не выполнялось, то я строил цикл для клетки, в которой имеется наибольшее положительное число и в ее ставил знак плюс и добавлял его к заполненным клеткам. После этого снова задавал целевую функцию и проверял решение на оптимальность если данное условие не выполнялось, то вновь строил цикл, и так до тех пор пока ∆_k не стало меньше или равно нулю. Когда же это произошло, я возвращал таблицу в исходный вид и записывал ответ.

Литература

1. 
   Вентцель Е.С. «Исследование операций». - М.:Наука, 2000 г. 
   
2. 
   Кремер Н.Ш. «Исследование операций в экономике». - М.: ЮНИТИ, 2003 г.
   
3. 
   Ермаков В.И. «Общий курс высшей математики для экономистов». – М.: Инфра-М, 2005 г.
   
4. 
   Замков О.О., А.В. Толстопятенко, Ю.Н. Черемных «Математические методы в экономике» . - «Дело и Сервис», 2000 г.
   
5. 
   Солодовников А. С., Бабайцев В. А., Браилов А. В. «Математика в экономике». – М.: Финансы и статистика, 2000г.
   
6. 
   Кремер Н.Ш., Путко Б.А., Тришин И.М. «Высшая математика для экономических специальностей»- «Высшее образование»; «Юрайт- Издат», 2009 г.