Тема 3 Целочисленное программирование 3 страница

Таблица 7 Симплекс-таблица №1

БП						СВ.Ч.
х3							20/2=10
х4							12/1=12
х5							12/2=2
П	-5	-6

мин(-5, -6,0,0,0)=-6

мин (10;12;2)=2

Таблица 8 Симплекс-таблица №1

БП						СВ.Ч.
х3
х4
х1	3/2	2/2	0/2	0/2	1/2	12/2
П

Заменяем оставшиеся элементы разрешающего столбца нулями

БП						СВ.Ч.
х3
х4
х1	3/2				1/2
П

Все остальные элементы находим по правилу прямоугольника

5?

	1?

r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">

	0?

r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">

	0?

r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">

	20?

4?

	0?

r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">

	1?

r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">

	0?

	12?

-5?	-6

-6	0?

-6	0?

-6	0?

-6	0?

Таблица 9

БП						СВ.Ч.
х3					-1
х4	5/2				-1/2
х1	3/2				1/2
П

Так как получили таблицу, в которой в последней строке все элементы- неотрицательные числа, то критерий оптимальности выполняется и получаем оптимальное решение

БП						СВ.Ч.
х3					-1
х4	5/2				-1/2
х1	3/2				1/2
П							Пмакс
	у4	у5	у1	у2	у3	Zmin

Таблица 10

	Прямая задача	Двойственная задача
Значения переменных
Значение целевой функции

Задача 2.

Записать симметричную двойственную пару ЗЛП. Привести к виду для составления общей симплекс-таблицы.

Вариант 3

Тогда математическая модель имеет вид

Задания для самостоятельного решения по теме №2

Задание

Предприятие выпускает два вида продукции: столы и стулья

На изготовление изделий расходуются три вида материалов:

древесина, клей и болты.

На каждый стол расходуется А1 дм2 древесины,

В1 мл клея

С1 болтов

На каждый стул расходуется А2 дм2 древесины,

В2 мл клея

С2 болтов

Запасы материалов на складе составляют Р1 древесины

Р2 клея

Р3 болтов

Прибыль от продажи одного стола составляет М1 рублей

Прибыль от продажи одного стула составляет М2 рублей

Предприятие должно получить максимальную прибыль

Решить задачу графически и симплекс-методом

Таблица 11

	Столы	Стулья	Запасы
Древесина	А1	А2	Р1
Клей	В1	В2	Р2
Болты	С1	С2	Р3
Прибыль	М1	М2

Задание

А1=3 А2=4 Р1=12

В1=5 В2=3 Р2=15

С1=3 С2=6 Р3=12

М1=4 М2=1

Задание

А1=6 А2=2 Р1=12

В1=1 В2=4 Р2=8

С1=7 С2=2 Р3=14

М1=1 М2=7

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

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

В общем виде задача ЦП формулируется следующим образом: найти

максимум или минимум функции

Методы решения задач целочисленного программирования.

Таблица 12

Целевая функция стремится к максимуму или к минимуму

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

Метод Гомори.

Задача решается симплекс- методом без учета целочосленности переменных.

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

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

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

Задача 4

Решить задачу целочисленного программирования методом Гомори.

Пусть дана целевая функция

Вводим искусственные переменные и . Приведем систему ограничений к виду:

Составим соответствующую таблицу

Таблица 13

БП СП				СЧ
	-3
		-3
	-3	-3	-13

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

Таблица 14

БП СП				СЧ
	-3
		-3
	-3	-3	-13

Свободные члены разделим на соответствующие элементы разрешающего столбца и выберем минимальное из отношений:

(8/7;8/7)

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

Таблица 15

БП СП				СЧ
	-3
		-3
	-3	-3	-13

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

Элементы разрешающей строки разделим на разрешающий элемент

Элементы разрешающего столбца(кроме разрешающего элемента), заменим нулями.

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

Таблица 16

БП СП				СЧ
	-3/7	6/7	7/7=1	8/7
		-9
	-60/7	57/7		104/7

Получим опорный план (0;0;8/7)

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

Этот элемент определяет выбор разрешающего столбца.

Таблица 17

БП СП				СЧ
	-3/7	6/7		8/7
		-9
	-60/7	57/7		104/7

Разделим свободные члены на элементы разрешающего столбца и выберем минимальное из отношений: ((8/7):(-3/7);0:9) Этот элемент определяет выбор разрешающего столбца.

Таблица 18

БП СП				СЧ
	-3/7	6/7		8/7
		-9
	-60/7	57/7		104/7

Преобразуем данную таблицу по указанным выше правилам:

Таблица 19

БП СП				СЧ
		3/7		8/7
	9/9=1	-9/9=-1	0/9=0	0/9=0
		3/7		104/7

Получим новый опорный план (0;0;8/7).

План является оптимальным, но не удовлетворяет условиям целочисленности. 8/7=1

Запишем значения в виде смешанных чисел:

Таблица 20

БП СП				СЧ
		-1

Отсекаем дробную часть

Составим соответствующую новую таблицу:

Таблица 21

БП СП				СЧ
		-1

Таблица 22

БП СП				СЧ

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

Таблица 23

БП СП				СЧ
	-1

Таблица 24

Дата добавления: 2017-02-01