Заглавная страница
Избранные статьи
Случайная статья
Познавательные статьи
Новые добавления
Обратная связь

ТОП 10 на сайте

Приготовление дезинфицирующих растворов различной концентрации

Техника нижней прямой подачи мяча.

Франко-прусская война (причины и последствия)

Организация работы процедурного кабинета

Смысловое и механическое запоминание, их место и роль в усвоении знаний

Коммуникативные барьеры и пути их преодоления

Обработка изделий медицинского назначения многократного применения

Образцы текста публицистического стиля

Четыре типа изменения баланса

Задачи с ответами для Всероссийской олимпиады по праву

Мы поможем в написании ваших работ!

ЗНАЕТЕ ЛИ ВЫ?

Влияние общества на человека

Приготовление дезинфицирующих растворов различной концентрации

Практические работы по географии для 6 класса

Организация работы процедурного кабинета

Изменения в неживой природе осенью

Уборка процедурного кабинета

Сольфеджио. Все правила по сольфеджио

Балочные системы. Определение реакций опор и моментов защемления

Главная Избранные Случайная статья Познавательные Новые добавления Обратная связь FAQ

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

⇐ ПредыдущаяСтр 3 из 7Следующая ⇒

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

(1)

при наличии линейных ограничений в виде равенств или неравенств

(2)

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

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

Пример выполнения задания 1

Найти максимум целевой функции Z=5 х ₁+7 х ₂ при ограничениях х ₁+4 х ₂≤ 16,

5 х ₁+ х ₂≤ 23,

х ₁≥ 0, х ₂≥ 0.

Чтобы найти решениеграфически, сначала следует изобразить многоугольник допустимых решений. Для этого заменяем в ограничениях знак «≤» на «=» и строим прямые х ₁+4 х ₂=16 и 5 х ₁+ х ₂=23. Нетрудно заметить, что прямые х ₁=0 и х ₂=0 (третье и четвертое ограничения) являются осями координат х ₁ и х ₂.

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

Теперь построим график ЦФ, приравняв Z к нулю (можно взять любое число). Обозначим этот график символами Z₀.

Для максимизации ЦФ будем перемещать прямую линию в направлении градиента возрастания ЦФ до тех пор, пока прямая линия не достигнет границы полигона допустимых решений. Из рисунка 1 видно, что оптимум находится в точке A. Запишем приблизительные координаты этой точки: х ₁ = 4, х ₂ = 3.

Рис. 1 Полигон допустимых решений

На основании приближенного графического решения задачи ЛПР найдём точный ответ аналитически. Для этого используем метод подстановок. Из рисунка 1 видно, что точка оптимума находится на пересечении двух прямых:

х ₁+4 х ₂=16,

5 х ₁+ х ₂=23.

Решим систему уравнений и найдем координаты х ₁ и х ₂: х ₁=4, х ₂=3. Затем полученные значения х ₁ и х ₂ подставляем в ЦФ:

Z=5 х ₁+7 х ₂=5·4+7·3

Таким образом, максимальное значение ЦФ Z=41.

В ответ записываем значения х ₁= 4, х ₂= 3 и Z = 41.

Пример выполнения задания 2

Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется три исходных продукта S1, S2 и S3. Расходы продуктов и запасы этих продуктов на складе приведены в таблице:

Исходный продукт	Расход продуктов (в тоннах на 1 т. краски)		Запас продукта на складе (тонн)
Исходный продукт	краска для внутренних работ	краска для внешних работ	Запас продукта на складе (тонн)
S1	10	5	250
S2	20	20	500
S3	5	5	200

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

Задача состоит в том, чтобы найти максимум целевой функции

Z = 200 х ₁+ 200 х ₂ при ограничениях

Построение математической модели рассмотрено в практическом занятии №1.

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

10 х₁+ 5 х₂ = 250: (0; 50) и (25; 0),

20 х₁+ 20 х₂ = 500: (0; 25) и (25; 0),

5 х₁+ 5 х₂ = 200: (0; 40) и (40; 0).

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

Рис.2 Область допустимых решений

Оптимальное решение находится в одной из угловых точек ОДР. Найдем значение целевой функции в угловых точках:

Е(0; 0) = 200∙0 + 200∙0 = 0,

Е(0; 25) = 200∙0 + 200∙25 = 5000 ден.ед.,

Е(25; 0) = 200∙25 + 200∙0 = 5000 ден.ед.

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

Ответ: Для достижения максимальной прибыли в размере 5000 ден.ед. нужно выпустить 0 тонн краски для внутренних работ и 25 тонн краски для внешних работ или 25 тонн краски для внутренних работ и 0 тонн краски для внутренних работ.

Практическое занятие №3

Наименование занятия: Решение задач линейного программирования с помощью Excel и Mathcad

Цель занятия: Научиться решать задачи линейного программирования с помощью Excel и Mathcad. Формировать ОК 1 – ОК 9, овладеть знаниями и умениями, необходимыми для освоения ПК 1.1, ПК 1.2.

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

Литература:

Лобачева М.Е. Конспект лекций «Математические методы», 2015г.

Перечень необходимых приборов, инструментов, материалов: ПЭВМ

Задание на занятие:

Составить математическую модель задачи линейного программирования и решить ее с помощью Microsoft Excel и MathСad, сравнить полученные результаты.

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

Вариант

Виды питательных веществ

Количество единиц питательных веществ в единице продукта

Минимальная норма питательных веществ

Стоимость единицы продукта

1,2

1,4

0,8

1,6

280

240

200

100

26,5

7,8

14,4

12,8

10,5

45,7

72,5

500

0,18

0,24

1,2

1,1

7,5

200

100

1,5

450

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

Вариант	Виды ресурсов	Расход ресурсов на единицу продукции			Запасы ресурсов	Доходы от реализации единицы продукции
Вариант	Виды ресурсов				Запасы ресурсов
6		2	1	1	25	6	5	5
		1	1	1	14
		0	4	2	19
		3	0	1	24
7		2	5	-	300	5	8	-
		4	5	-	400
		3	0	-	100
		0	4	-	200
8		2	5	-	20	50	40	-
		8	5	-	40
		5	6	-	30
9		2	3	-	19	7	5	-
		2	1	-	13
		0	3	-	15
		3	0	-	18
10		2	5	7	60	32	13	61
		22	14	18	500
		10	14	8	328

Порядок проведения занятия:

1. Получить допуск к работе.

2. Решить задачу в соответствии со своим вариантом с помощью Microsoft Excel и MathСad.

3. Сравнить полученные результаты и сделать вывод.

4. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;

2. Выполненное задание;

3. Выводы по результатам выполненного задания;

4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

С помощью каких математических систем можно решать задачи ЛПР?
Каков порядок решения задач ЛПР с помощью электронных таблиц MS Excel?
Каковы недостатки решения задач ЛПР при помощи MS Excel?

ПРИЛОЖЕНИЕ

Пример выполнения задания

Для откорма животных на ферме в их ежедневный рацион необходимо включить не менее 33-х единиц питательного вещества , 23-х единиц вещества и 12-ти единиц вещества . Для откорма используется 3 вида кормов. Данные о содержании питательных веществ и стоимости весовой единицы каждого корма даны в таблице.

	(усл. ед.)	(усл. ед.)	(усл. ед.)	Стоимость (руб.)
Весовая единица корма I	4	3	1	20
Весовая единица корма II	3	2	1	20
Весовая единица корма III	2	1	2	10

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

Математическая постановка задачи. Пусть , , — количества кормов I, II, III видов, включаемые в ежедневный рацион (, ). Тогда должно быть:

(3)

При этом линейная функция (стоимость рациона)

(4)

Пример решения задачи в Microsoft Excel.

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

При решении задачи с помощью надстройки Поиск решения необходимо:

1. открыть окно Microsoft Excel;

2. заполнить ячейкиA1-А4 таблицы обозначениями , , и min соответственно:

3. в ячейку В4 записать формулу (4) через адреса соответствующих ячеек:

Рисунок 2

4. в диапазон ячеек А7-С9 записать систему (3) через адреса соответствующих ячеек, т. е. в А7 ввести формулу , в А8 ввести формулу , в А9 ввести формулу , в ячейки В7-В9 ввести слова не менее, в ячейки С7-С9 33, 23 и 12 соответственно:

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

6. в появившемся окне Поиск решения в поле Установить целевую ячейку надо щёлкнуть по кнопке , затем в ячейке B4 и снова по кнопке ; в поле Равной установить флажок минимальному значению, в поле Изменяя ячейки щёлкнуть по кнопке , выделить мышью диапазон ячеек В1¸В3 и снова щёлкнуть по кнопке :

7. нажать на копку Добавить: появится новое окно Добавление ограничения, в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек В1¸В3 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать знак >=, нажав , затем в поле Ограничение ввести 0;

8. в этом же окне Добавление ограничения нажать кнопку Добавить (появится новое окно Добавление ограничения) и ввести новое ограничение: в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек А7¸А9 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать знак >=, нажав , затем в поле Ограничение надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек C7¸C9 и снова щёлкнуть по кнопке :

9. все ограничения нами учтены: нажать кнопку ОК, после чего снова откроется диалоговое окно Поиск решения, и нажать кнопку Выполнить:

10. в появившемся диалоговом окне Результаты поиска решения нажать кнопку ОК и получим результат вычислений:

Замечание 1. Если в неравенствах (3) знаки разные (, , ), то ограничения в пункте 8 вносятся отдельно для каждой строки, а не через диапазон, как в примере.

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

Замечание 3. На практике часто требуется, чтобы на переменные , , налагалось условие целочисленности (например, если какой-то продукт нельзя разрезать на части, а можно добавлять в рацион только целыми порциями), в этом случае в окне Добавление ограничения, в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек В1¸В3 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать условие ЦЕЛ, нажав .

Пример решения задачи в MathСad.

1. задать начальное приближение:

2. записать все коэффициенты из (3) и (4) в матричном виде:

3. ввести целевую функцию (4) в виде:

4. записать функцию Given;

5. записать ограничения (3) в виде:

6. записать функцию минимизации, после чего получим оптимальный план

7. найти значение целевой функции в точке минимума:

ВЫВОД: Оптимальные планы при решении задачи в средах Microsoft Excel и MathСad получились различные, но целевая функция при этом имеет одинаковое значение, равное 165.

Практическое занятие №4

Наименование занятия: Решение задачи об оптимальном использовании ограниченных ресурсов

Цель занятия: Научиться решать задачи линейного программирования с учетом стоимости ресурсов. Формировать ОК 1 – ОК 9, овладеть знаниями и умениями, необходимыми для освоения ПК 1.1, ПК 1.2.

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

Литература:

Лобачева М.Е. Конспект лекций «Математические методы», 2015г.

Перечень необходимых приборов, инструментов, материалов: ПЭВМ

Задание на занятие:

1. Графически и аналитически решить задачу максимизации целевой функции Z. Найти оптимальное решение с учетом стоимости ресурсов. Исходные данные для каждого варианта приведены в таблице. Символами с₁, с₂ и с₃ обозначены стоимости соответственно первого, второго и третьего ресурсов b₁, b₂ и b₃.

2. Решить задачу, используя приложение MS Excel.

3. По полученным результатам сделать выводы.

Вариант	Целевая функция	Ограничения	Стоимость ресурсов
1	Z=2,4х₁+2х₂	2х₁+5х₂≤ 35 6х₁+х₂≤ 33 6х₁+5х₂≤ 45 х₁≥ 0, х₂≥ 0	c₁ = 7,2 c₂ = 5,5 c₃ = 8
2	Z=1,8х₁+х₂	х₁≥ 0, х₂≥ 0 5х₁+11х₂≤ 99 4х₁+х₂≤ 34 9х₁+5х₂≤ 82	c₁ = 2,5 c₂ = 24 c₃ = 8,7
3	Z=6х₁+8х₂	х₁≥ 0, х₂≥ 0 3х₁+8х₂≤ 80 14х₁+5х₂≤ 119 3х₁+4х₂≤ 46	c₁ = 19 c₂ = 7 c₃ = 6,1
4	Z=0,8х₁+х₂	х₁≥ 0, х₂≥ 0 х₁+3х₂≤ 19,5 4х₁+х₂≤ 20 4х₁+5х₂≤ 36	c₁ = 17 c₂ = 6,2 c₃ = 5
5	Z=9х₁+13,5х₂	х₁≥ 0, х₂≥ 0 х₁+7х₂≤ 52,5 2х₁+х₂≤ 20 2х₁+3х₂≤ 28	c₁ = 12 c₂ = 10,4 c₃ = 3
6	Z=36х₁+30х₂	х₁≥ 0, х₂≥ 0 5х₁+9х₂≤ 51 2х₁+х₂≤ 12 6х₁+5х₂≤ 38	c₁ = 3 c₂ = 28,5 c₃ = 11
7	Z=6х₁+9х₂	х₁≥ 0, х₂≥ 0 2х₁+9х₂≤ 68 7х₁+2х₂≤ 48,5 2х₁+3х₂≤ 26	c₁ = 7,5 c₂ = 4 c₃ = 5,8
8	Z=13,4х₁+6,7х₂	х₁≥ 0, х₂≥ 0 2х₁+3х₂≤ 27 8х₁+х₂≤ 59 2х₁+х₂≤ 17	c₁ = 22 c₂ = 14,5 c₃ = 10,2
9	Z=2х₁+6х₂	х₁≥ 0, х₂≥ 0 х₁+9х₂≤ 71 13х₁+6х₂≤ 123,5 х₁+3х₂≤ 26	c₁ = 8,8 c₂ = 9,5 c₃ = 6
10	Z=1,6х₁+2х₂	х₁≥ 0, х₂≥ 0 6х₁+13х₂≤ 91 3х₁+х₂≤ 29 4х₁+5х₂≤ 46	c₁ = 9,5 c₂ = 20 c₃ = 12

Порядок проведения занятия:

1. Получить допуск к работе.

2. Выполнить задание в соответствии со своим вариантом.

3. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;

2. Выполненное задание;

3. Выводы по результатам выполненного задания;

4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

1. В чем особенность решения задач с учетом стоимости ресурсов?

ПРИЛОЖЕНИЕ

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

Пусть в качестве исходных данных дана таблица:

ЦФ	Ограничения	Стоимость ресурсов
Z=1,8х₁+х₂	х₁≥ 0, х₂≥ 0 х₁+7х₂≤ 49 4х₁+х₂≤ 26 9х₁+5х₂≤ 64	c₁ = 11 c₂ = 60 c₃ = 22

Символами с₁, с₂ и с₃ обозначены стоимости соответственно первого, второго и третьего ресурсов b₁, b₂ и b₃. Требуется максимизировать ЦФ.

Область допустимых решений показана на рисунке. Из рисунка видно, что график ЦФ параллелен графику ограничения 9х₁+5х₂≤ 64, обозначенному цифрой 3. В этом случае решением задачи без учета экономии ресурсов является любая точка отрезка AB. На отрезке AB целевая функция максимальна: Z=12,8. Однако необходимо узнать, в какой точке отрезка AB достигается максимальная экономия ресурсов с учетом их стоимости (максимальная экономия денежных средств).

Так как все функции линейны, оптимальное решение может находиться только на концах отрезка AB. Определим экономию ресурсов в точках A и B.

Подставим координаты точки A в каждое ограничение (кроме условий неотрицательности).

Определим расход ресурса b₁:

b₁=х₁+7х₂=3,5+7·6,5=49 единиц. Экономии этого ресурса в точке A нет.

Найдем расход ресурса b₂:

b₂=4х₁+х₂=4·3,5+6,5=20,5 единиц. Экономия составляет 26-20,5=5,5 единиц.

Оценим расход ресурса b₃:

b₃=9х₁+5х₂=9·3,5+5·6,5=64 единицы. Экономии ресурса нет.

Подсчитаем теперь расход ресурсов b₁, b₂ и b₃ в точке B.

b₁=х₁+7х₂=6+7·2=20 единиц. Экономия составляет 49-20=29 единиц.

b₂=4х₁+х₂=4·6+2=26 единиц. Экономии ресурса нет.

b₃=9х₁+5х₂=9·6+5·2=64 единицы. Экономии ресурса нет.

Как мы видим, в точке A можно сэкономить 5,5 единиц ресурса b₂. Его стоимость c₂ согласно условию задачи равна: c₂ = 60. Следовательно, экономия составит 5,5·60=330 ден.ед.

В точке B можно сэкономить 29 единиц ресурса b₁. Его стоимость c₁ равна: c₁ = 11. Экономия составит 29·11=319 ден.ед.

В точке A экономия больше.

ВЫВОД: расход на ресурсы минимален при х₁=3,5 и х₂=6,5. В этой точке можно сэкономить 330 ден.ед. При этом целевая функция Z=12,8.

Пример решения задачи с помощью приложения MS Excel.

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

Составим таблицу:

Окно Поиск решения заполним следующим образом:

В результате выполнения этой операции MS Excel найдет максимальное значение Z (Z=12,8), а также координаты х₁ и х₂ точки, принадлежащей отрезку AB. Как было отмечено выше, приложение MS Excel не учитывает экономию ресурсов при поиске решений.

После этого дополним нашу таблицу строкой «Расход денежных средств»:

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

Примечание. Перед выполнением следующей операции желательно «сбросить» значения х₁ и х₂ (например, записать нули) в ячейках B1 и B2.

Теперь в окне Поиск решения в качестве ЦФ укажем расход денежных средств, установим переключатель Равной в положение минимальному значению и добавим еще одно ограничение: целевая функция Z равна 12,8. Окно будет выглядеть следующим образом:

Найденные координаты точки оптимума, как видим, совпадают с аналитическими расчетами:

Практическое занятие № 5

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

Цель занятия: Научиться решать задачи линейного программирования симплекс-методом. Формировать ОК 1 – ОК 9, овладеть знаниями и умениями, необходимыми для освоения ПК 1.1, ПК 1.2.

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

Литература:

Лобачева М.Е. Конспект лекций «Математические методы», 2015г.

Перечень необходимых приборов, инструментов, материалов: ПЭВМ

Задание на занятие:

1. Решить задачу максимизации целевой функции Z симплекс-методом.

Вариант	Целевая функция	Ограничения
1	Z=4х₁+1,5х₂	х₁≥ 0, х₂≥ 0 4х₁+5х₂≤ 30 8х₁+3х₂≤ 32
2	Z=1,5х₁+6х₂	х₁≥ 0, х₂≥ 0 х₁+4х₂≤ 18 8х₁+5х₂≤ 36
3	Z=2,5х₁+х₂	х₁≥ 0, х₂≥ 0 х₁+3х₂≤ 10,5 5х₁+2х₂≤ 33
4	Z=6х₁+2х₂	х₁≥ 0, х₂≥ 0 х₁+10х₂≤ 35 3х₁+х₂≤ 18
5	Z=6х₁+2х₂	х₁≥ 0, х₂≥ 0 5х₁+6х₂≤ 33 3х₁+х₂≤ 12
6	Z=0,5х₁+2х₂	х₁≥ 0, х₂≥ 0 х₁+4х₂≤ 12 6х₁+7х₂≤ 38
7	Z=2х₁+0,4х₂	х₁≥ 0, х₂≥ 0 5х₁+6х₂≤ 25 5х₁+х₂≤ 12,5
8	Z=3,5х₁+7х₂	х₁≥ 0, х₂≥ 0 х₁+2х₂≤ 12 8х₁+7х₂≤ 60
9	Z=5х₁+15х₂	х₁≥ 0, х₂≥ 0 х₁+3х₂≤ 10,5 8х₁+3х₂≤ 42
10	Z=1,5х₁+12х₂	х₁≥ 0, х₂≥ 0 х₁+8х₂≤ 56 3х₁+х₂≤ 18,5

Порядок проведения занятия:

Получить допуск к работе.
Выполнить задание в соответствии со своим вариантом.
Ответить на контрольные вопросы.

Содержание отчета:

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

Контрольные вопросы для зачета:

1. Каков геометрический смысл симплекс-метода?

2. Как определить разрешающий столбец? Разрешающую строку?

3. Перечислите основные этапы симплекс-метода.

ПРИЛОЖЕНИЕ

Пример выполнения задания

Найти максимум целевой функции Z=2x₁+x₂, при ограничениях:

x₁ + 2x₂ 3

3x₁ + x₂ 3

x₁, x₂ 0.

Областью допустимых решений является многоугольник ABCD. Точкой из многоугольника ABCD, в которой целевая функция Z имеет максимальное значение, будет вершина С. Эта точка и определяет решение задачи.

Решение задачи линейного программирования в симплекс-таблицах

1) Приведение задачи к стандартному виду.

Введем вспомогательные (балансовые) переменные x₃и x₄ в левые части неравенств и запишем ограничения в виде равенств:

x₁ + 2x₂ + x₃ = 3 (А)

3x₁ + x₂ + x₄ = 3 (В)

Целевая функция Z = 2x₁ + x₂ при приведении задачи к стандартному виду записывается так:

Z - 2x₁ - x₂ = 0 (С)

2) Составление первой симплекс-таблицы.

Симплекс-таблица составляется из коэффициентов при x₁, x₂, x₃, x₄ и чисел, стоящих в правых частях уравнений-ограничений задачи: в первой строке записываются элементы уравнения (А), во второй - (В). В последней строке симплекс-таблицы записываются коэффициенты и правая часть целевой функции (С). Таким образом, симплекс-таблица содержит две строки коэффициентов (по числу ограничений задачи) и строку коэффициентов целевой функции. Число столбцов в симплекс-таблице равно числу переменных задачи плюс один столбец правых частей (b):

X₁	X₂	X₃	X₄	b
1	2	1	0	3
3	1	0	1	3
-2	-1	0	0	0

Переменные, для которых столбцы коэффициентов состоят из одной единицы и нулей, называются базисными (В приведенном примере x₃ и x₄ - базисные переменные). Число базисных переменных равно числу ограничений задачи и не меняется при симплекс-преобразовании. Остальные переменные называются свободными (x₁ и x₂).

Симплекс-таблица определяет частное решение системы уравнений-ограничений

x₁ +2x₂ + x₃ = 3

3x₁ +x₂ + x₄ = 3,

при котором свободные переменные равны нулю (x₁=0, x₂=0), а базисные переменные равны правым частям соответствующих строк (x₃=3, x₄=3).

Значение целевой функции Z всегда равно числу, стоящему в правом нижнем углу таблицы (Z=2*0+1*0=0). Первая симплекс-таблица соответствует начальному решению задачи линейного программирования (х₁=0, х₂=0, x₃=3, x₄=3, Z=0). Это решение соответствует вершине А многоугольника допустимых решений ABCD.