1. 
   Симплекс-метод
   

Определим максимальное значение целевой функции

F(X) = 126x₁+118x₂+108x₃ при следующих условиях-ограничений.

0.6x₁+0.5x₂+0.8x₃≤800

0.3x₁+0.4x₂+0.4x₃≤600

0.1x₁+0.1x₂≤108

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

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

0.6x₁+0.5x₂+0.8x₃+x₄ = 800

0.3x₁+0.4x₂+0.4x₃+x₅ = 600

0.1x₁+0.1x₂+x₆ = 108

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

A =	0,6 0,5 0,8 1 0 0 0,3 0,4 0,4 0 1 0 0,1 0,1 0 0 0 1

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

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

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

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

X0 = (0,0,0,800,600,108)

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	800	0.6	0.5	0.8	1	0	0
x5	600	0.3	0.4	0.4	0	1	0
x6	108	0.1	0.1	0	0	0	1
F(X0)	0	-126	-118	-108	0	0	0

---

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

min (800 : 0.6 , 600 : 0.3 , 108 : 0.1 ) = 1080

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	800	0.6	0.5	0.8	1	0	0	1333.33
x5	600	0.3	0.4	0.4	0	1	0	2000
x6	108	0.1	0.1	0	0	0	1	1080
F(X1)	0	-126	-118	-108	0	0	0

---

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

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	325	0.125	0	1	1.25	0	-6.25
x5	38	-0.15	0	0	-0.5	1	-1.5
x2	1080	1	1	0	0	0	10
F(X3)	162540	5.5	0	0	135	0	505

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

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	325	0.125	0	1	1.25	0	-6.25
x5	38	-0.15	0	0	-0.5	1	-1.5
x2	1080	1	1	0	0	0	10
F(X4)	162540	5.5	0	0	135	0	505

---

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

x₁ = 0, x₂ = 1080, x₃ = 325

F(X) = 126*0 + 118*1080 + 108*325 = 162540
Задание №2
Математическая модель транспортной задачи:

F = ∑∑cijxij, (1)

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

∑xij = ai, i = 1,2,…, m, (2)

∑xij = bj, j = 1,2,…, n, (3)

xij ≥ 0

Запишем экономико-математическую модель для нашей задачи.

Переменные:

x11 – количество груза из 1-го склада в 1-й магазин.

x12 – количество груза из 1-го склада в 2-й магазин.

x13 – количество груза из 1-го склада в 3-й магазин.

x21 – количество груза из 2-го склада в 1-й магазин.

x22 – количество груза из 2-го склада в 2-й магазин.

x23 – количество груза из 2-го склада в 3-й магазин.

x31 – количество груза из 3-го склада в 1-й магазин.

x32 – количество груза из 3-го склада в 2-й магазин.

x33 – количество груза из 3-го склада в 3-й магазин.

x41 – количество груза из 4-го склада в 1-й магазин.

x42 – количество груза из 4-го склада в 2-й магазин.

x43 – количество груза из 4-го склада в 3-й магазин.

x51 – количество груза из 5-го склада в 1-й магазин.

x52 – количество груза из 5-го склада в 2-й магазин.

x53 – количество груза из 5-го склада в 3-й магазин.

Ограничения по запасам:

x11 + x12 + x13 ≤ 280 (для 1 базы)

x21 + x22 + x23 ≤ 140 (для 2 базы)

x31 + x32 + x33 ≤ 80 (для 3 базы)

x41 + x42 + x43 ≤ 70 (для 4 базы)

x51 + x52 + x53 ≤ 210 (для 5 базы)

Ограничения по потребностям:

x11 + x21 + x31 + x41 + x51 = 300 (для 1-го магазина)

x12 + x22 + x32 + x42 + x52 = 150 (для 2-го магазина)

x13 + x23 + x33 + x43 + x53 = 330 (для 3-го магазина)

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

7x11 + 10x12 + 10x13 + 5x21 + 4x22 + 8x23 + 6x31 + 6x32 + 9x33 + 6x41 + 6x42 + 8x43 + 3x51 + 2x52 + 3x53 → min

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

∑a = 280 + 140 + 80 + 70 + 210 = 780

∑b = 300 + 150 + 330 = 780

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

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



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

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

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

---

либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.

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

Искомый элемент равен c52=2. Для этого элемента запасы равны 210, потребности 150. Поскольку минимальным является 150, то вычитаем его.

x52 = min(210,150) = 150.

7	x	10	280
5	x	8	140
6	x	9	80
6	x	8	70
3	2	3	210 - 150 = 60
300	150 - 150 = 0	330

Искомый элемент равен c51=3. Для этого элемента запасы равны 60, потребности 300. Поскольку минимальным является 60, то вычитаем его.

x51 = min(60,300) = 60.

7	x	10	280
5	x	8	140
6	x	9	80
6	x	8	70
3	2	x	60 - 60 = 0
300 - 60 = 240	0	330

---

Смотрите также файлы

• Назначение и состав средств усиления речи.docx

• 113 экономические науки.pdf

• Рудакова Ж.Н. Оловоносные граниты Юго-Западного Забайкалья.pdf

• Синяков Н.И. Технология изготовления фотомеханических печатных форм учебник.pdf

• Стесин С.П. Гидродинамические передачи учебник.pdf