Решение задачи размещения оборудования методом Гомори

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

Введение

Курсовой проект реализован студентом группы ПВТ 9-09 Зуевом Евгением Евгеньевичем. Руководитель курсового проекта: Абеуова Меруерт Зарухановна. Целью курсового проекта является Решение задачи размещения оборудования методом Гомори.

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

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

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

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

"Аналогией" называют суждение о каком-либо частном сходстве двух объектов. При этом сходство может быть существенным и несущественным. Понятие существенности и не существенности сходства или различия зависит от уровня абстрагирования и в общем случае определяется конечной целью проводимого исследования. Гипотезы и аналогии, отражающие реальный, объективно существующий мир, должны обладать наглядностью или сводится к удобным для исследования логическим схемам. Такие логические схемы, упрощающие рассуждения и логические построения или позволяющие производить эксперименты, называются "моделями". Другими словами модель (лат.modulus-тера) - это объект-заместитель объекта оригинала, обеспечивающий изучение некоторых свойств оригинала.

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

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

Целью данной работы является рассмотрение задачи размещения оборудования и метода Гомори как метода ее решения.

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



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

1.1 Понятие модели и их разновидности

Модель (фр. modиle, от лат. modulus -- «мера, аналог, образец») -- некоторый материальный или мысленно представляемый объект или явление, являющийся упрощённой версией моделируемого объекта или явления (прототипа) и в достаточной степени повторяющий свойства, существенные для целей конкретного моделирования (опуская несущественные свойства, в которых он может отличаться от прототипа).

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

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

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

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

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

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

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

Постановка задачи, ее теоретическая и логическая формулировка.

Анализ структуры исследуемой экономической системы.

Построение модели отвечающей экономическим условиям задачи и математическим принципам.

Заполнение системы уравнений необходимыми статистическими данными.

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

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

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

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

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

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

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

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

1.2 Построение модели

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

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

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

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

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

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

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

- Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А1х1 + А2x2 + ... + АNxN = Ао, X 0, где С = (с1, с2, ..., сN); Х = (х1, х2, ..., хN); СХ - скалярное произведение; векторы A1, A2,..., AN, A0 состоят соответственно из коэффициентов при неизвестных и свободных членах.

- Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0, Х 0, где С = (с1, с2, ..., сN) - матрица-cтрока; А = (аij) - матрица системы; Х - матрица-столбец, А0 - матрица-столбец.

- Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = Сjхj при ограничениях:

Определение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х1, х2, ..., хN).

Определение 2. План Х = (х1, х2, ..., хN) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми. Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

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

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

Для решений уравнений линейного программирования применяют симплексный метод. Решение оформляется в виде таблицы. Переход к другой таблице называется итерацией.

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

- Правая часть системы ограничений состоит из неотрицательных чисел, т. е. P0 ? 0

- Канонический вид системы содержит полный набор базисных векторов.

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

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

Z = С1х1+С2х2+... +СNxN (1.2.1)



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

a11x1 + a22x2 + ... + a1NХN b1

a21x1 + a22x2 + ... + a2NХN b2

. . . . . . . . . . . . . . . (1.2.2)

aM1x1 + aM2x2 + ... + aMNХN bM

xj 0 (j = 1, 2, ... ,n) (1.2.3)

Совокупность чисел х1, х2, ..., хN, удовлетворяющих ограничениям (1.2.2) и (1.2.3), называется решением. Если система неравенств (1.2.2) при условии (1.2.3) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместной.

Рассмотрим на плоскости х1Ох2 совместную систему линейных неравенств

a11x1 + a22x2 b1

a21x1 + a22x2 b2

. . . . . . . .

aM1x1 + aM2x2 bM

x1 0, x2 0

Это все равно, что в системе (1.2.2) - (1.2.3) положить N=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой

ai1x1 + ai2x2 = bi ,(i = 1, 2, ..., m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы.

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

Если в системе ограничений (1.2.2) - (1.2.3) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого ai1x1 + ai2x2 + ai3x3 = bi ,(i = 1, 2, ..., n), а условия не отрицательности - полупространства с граничными плоскостями соответственно хj = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.2.2) - (1.2.3) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью ai1x1 + ai2x2 + aiNxN = bi (i = 1, 2, ..., m), а условия не отрицательности - полупространства с граничными гиперплоскостями хj 0 (j = 1, 2, ..., n).

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

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

1.3 Выбор метода реализации модели

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

Для реализации поставленной задачи, была выбрана среда разработки Borland Delphi 7.

Borland Delphi 7 позволяет создавать самые различные программы: от простейших однооконных приложений до программ управления распределенными базами. В состав пакета включены разнообразные утилиты, обеспечивающие работу с базами данных, XML-документами, создание справочной системы, решение других задач.

Borland Delphi может работать в среде операционных систем Windows. Особых требований, по современным меркам, к ресурсам компьютера пакет не предъявляет: процессор должен быть типа Pentium или Celeron с тактовой частотой не ниже 166 МГц, оперативной памяти - 128 Мбайт, достаточное количество свободного дискового пространства.

Язык Delphi строго типизированный объектно-ориетированный язык в основе которого лежит Obgect Pascal.

Программа на Delphi состоит из набора модулей, в каждом из которых содержится описание логически независимой части программы (например, описание работы конкретного окна или описание алгоритма вычисления сложной математической функции). Расширение имени файлов содержащих модули - .PAS. Модули программы часто создаются системой Delphi автоматически, например, при добавлении новой формы. При этом происходит автоматическая генерация исходного кода соответствующего модуля, что избавляет программиста от рутинной работы.

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

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

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

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

Решение практически любой задачи можно запрограммировать от начала и до конца. Однако при составлении программ очень часто возникает потребность выполнить какое-либо действие, которое уже использовалось в различных программах. Поэтому в систему Delphi 7 входит обширный набор стандартных модулей, содержащих стандартные функции. Такие модули представляют собой готовый откомпилированный и оптимизированный код, предназначенный для решения самых разных задач.

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

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

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

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

моделирование программирование гомори



2. Расчет модели

2.1 Постановка задания

Решение задачи размещения оборудования методом Гомори.

Для приобретения нового оборудования предприятие выделяет 19 ден.ед. Оборудование должно быть размещено на площади, не превышающей 16 кв.м. Предприятие может заказать оборудование двух видов: машины типа “А” стоимостью 2 ден.ед., требующие производственную площадь 4 кв.м и обеспечивающие производительность за смену 8 т продукции, и машины типа “В” стоимостью 5 ден.ед., занимающие площадь 1 кв.м и обеспечивающие производительность за смену 6 т продукции.

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

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

Рисунок 1 Линейное программирование



2.1.1 Экономическая интерпретация задачи

Согласно полученному решению предприятию необходимо закупить 3 машины типа "А" и 2 машины ти-па "В". При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден.ед. можно будет направить на какие-либо иные цели, например, на премирование рабочих, которые будут заниматься отладкой полученного оборудования. На излишнюю площадь в 2 кв.м можно поставить ящик с цветами.

2.1.2 Построение математической модели и методы ее реализации

Обозначим через x1, x2 количество машин соответственно типа “А” и “В”, через L - их общую производительность. Тогда математическая модель задачи:

max L = 8x1 + 6x2

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

2x1 + 5x2 Ј 19

4x1 + x2 Ј 16

x1 і 0, x2 і 7

x1 , x2 - целые числа

Решаем задачу симплексным методом без учета целочисленности.

Таблица 1 Решение

Co	Бo	Хo	8	6	-	-
			X1	X2	X3	X4
- -	x3 x4	19 16	2 4	5 1	1 -	- 1
zj ?j	0	-	-	-	-
		-8	-6	-	-

Таблица 2 Решение

C1	B1	X1	8	6	-	-
			X1	X2	X3	X4
- 8	X3 X1	11 4	- 1	9/2 1/4	1 -	-1/2 1/4
zj ?j	32	80	2	-	2
		-	-4	-	-2

Таблица 3 Решение

C2	B2	X2	8	6	-	-	-
			X1	X2	X3	X4
6 8	X2 X1	22/9 61/18	- 1	1 -	2/9 -1/18	-1/9 5/18	- -
zj ?j	376/9	8	6	8/9	14/9	-
		-	-	8/9	14/9	-
	4/9	-	-	2/9	8/9	-1

Получен оптимальный нецелочисленный план Хопт= (61/18;22/9). Lmax = 376/9. Т.к. у компоненты плана х2 максимальная дробная часть: max(4/9;7/18) = 4/9, то дополнительное ограничение записываем по первой строке.

22/9 - [22/9] = (2/9 - [2/9])x3 + (-1/9 - [-1/9])x4 - S1, S1 і 0

22/9 - 2 = (2/9 - 0)x3 + (-1/9 - (-1))x4 - S1, S1 і 0

4/9 = 2/9x3 + 8/9x4 - S1, S1 і 0 - первое ограничение Гомори.

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



= Ю в базис вводим вектор х4.

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

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

Таблица 4 Решение

C3	B3	X3	8	6	-	-	-
			X1	X2	X3	X4	S1	S2
6 8	X2 X1 X4	5/2 13/4 1/2	- 1 -	1 - -	1/4 -1/8 1/4	- - -1	-1/8 5/16 -9/8	- - -
zj ?j	41	8	6	1/2	-	7/4	-
		-	-	1/2	-	7/4	-
	1/2	-	-	1/4	-	7/8	-1

Найденный план оптимален, но нецелочисленный. Строим новое ограничение Гомори.

Т.к. максимальная дробная часть среди компонент плана равна 1/2, записываем дополнительное ограничение по первой строке (можно и по третьей).

5/2 - [5/2] = (1/4 - [1/4])x3 + (-1/8 - [-1/8])S1 - S2, S2 і 0

1/2 = 1/4x3 + 7/8S1 - S2, S2 і 0 - второе ограничение Гомори

Это ограничение добавляем в последнюю симплексную таблицу.

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

Определяем вектор, вводимый в базис: Можно ввести либо x3, либо S1. Введем вектор S1. Ю соответствует дополнительному ограничению.

Таблица 5 Решение

C4	B4	X4	8	6	-	-	-	-	-
			X1	X2	X3	X4	S1	S2	S3
6 8 -	X2 X1 X4	5/2 13/4 1/2	- 1 -	1 - -	2/7 -3/14 4/7	- - 1	- - -	-1/7 5/14 -9/7	- - -
-	S1	4/7	-	-	2/7	-	1	-8/7	-
zj ?j	40	8	6	-	-	-	2	-
		-	-	-	-	-	2	-
	4/7	-	-	2/7	-	-	6/7	-1

Получаем новый оптимальный нецелочисленный план.

Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие переменной S1.

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

4/7 = 2/7х3 + 6/7S2 - S3, S3і 0 - третье ограничение Гомори.

Определяем вектор, вводимый в базис: Это вектор x3.

Минимальное значение q = 2, что соответствует дополнительной строке.

После проведения очередных симплексных преобразований получили:

Таблица 6 Решение

C5	B5	X5	8	6	-	-	-	-	-
			X1	X2	X3	X4	S2	S3	S4
6 8 - -	X2 X1 X4 X3	2 7/2 - 2	- 1 - -	1 - - -	- - - 1	- - 1 -	-1 1 -3 3	1 -3/4 2 -7/2
zj ?j	41	8	6	-	-	-	2	-
		-	-	-	-	-	2	-
	1/2	-	-	-	-	-1	1/4	-1

План Х5 - оптимальный нецелочисленный. Дополнительное ограничение запишем по второй строке: 1/2 = 1/4S3 - S4, S4 і 0 - четвертое ограничение Гомори. Т.к. базисной компонентой может быть S3, определяем величину. . Минимальное значение получилось по 3 строке, а не по строке Гомори, следовательно, переходим к М-задаче: введем дополнительную переменную X5 в ограничение Гомори.

Таблица 7 Решение

C5	B5	X5	8	6	-	-	-	-	-	-M
			X1	X2	X3	X4	S2	S3	S4	X5
6 8 - - -M	X2 X1 X4 X3 X5	2 7/2 - 2 1/2	- 1 - - -	1 - - - -	- - - 1 -	- - 1 - -	-1 1 -3 3 -	1 -3/4 2 -7/2 1/4	- - - - -1	- - - - 1
zj ?j	40-M/2	8	6	-	-	2	-M/4	M	-M
		-	-	-	-	2	-M/4	M	-

Таблица 8 Решение

C6	B6	X6	8	6	-	-	-	-	-	-M
			X1	X2	X3	X4	S2	S3	S4	X5
6 8	X1 X2	2 7/2	- 1	1 -	- -	-1/2 3/8	Ѕ -1/8	- -	- -	- -
-	S3	-	-	-	-	1/2	-3/2	1	-	-
- -M	X3 X4	2 1/2	- -	- -	1 -	7/4 -1/8	-9/4 3/8	- -	- -1	- 1
zj ?j	40-M/2	8	6	-	M/8	2-3M/8	-	M	M
		-	-	-	M/8	2-3M/8	-	M	-



Таблица 9 Решение

C7	B7	X7	8	6	-	-	-	-	-M
			X1	X2	X3	X4	S2	S4	S5
6 8	X2 X1 X3						- - -	4/3 -1/3 -6	- - -
-	S2						1	-8/3	-
zj ?j	112/3	8	6	-	2/3	-	16/3	-
		-	-	-	2/3	-	16/3	-
	2/3	-	-	-	1/3	-	2/3	-1

Дробная часть = max(1/3; 2/3) = 2/3 Ю дополнительное ограничение записываем по второй строке.

2/3 = 1/3х4 + 2/3S4 - S5 ,S5і 0 - пятое ограничение Гомори.

Вектор, вводимый в базис: вводим х4.

Ю соответствует строке Гомори.

Таблица 10 Решение

C8	B8	X8	8	6	-	-	-	-
			X1	X2	X3	X4	S4	X5
6 8 - -	X2 X1 X3 X4	2 3 3 2	- 1 - -	1 - - -	- - 1 -	- - - 1	2 -1 -8 2	-1 1 1 3 -3
zj ?j	36	8	6	-	-	4	2
		-	-	-	-	4	2

План Х8 = (3; 2; 3; 2) - оптимальный целочисленный. Lmax = 36.

Экономическая интерпретация: согласно полученному решению предприятию необходимо закупить 3 машины типа "А" и 2 машины ти-па "В". При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден.ед. можно будет направить на какие-либо иные цели, например, на премирование рабочих, которые будут заниматься отладкой полученного оборудования. На излишнюю площадь в 2 кв.м можно поставить ящик с цветами.

Геометрическая интерпретация метода Гомори: строим множество планов (см. рисунок). В точке 1 - оптимальный нецелочисленный план.

Рисунок 2 Геометрическая интерпретация метода Гомори

Первое ограничение Гомори: 2/9x3 + 8/9x4 - S1 = 4/9, S1 і 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2

Из второго ограничения задачи: х4 = 16 - 4х1 - х2

Подставляем х3 и х4 в первое ограничение Гомори и после преобразований получаем: 4х1 + 2х2 + S1 = 18, S1 і 0.

Отсюда имеем: 4х1 + 2х2 Ј 18. Это ограничение отсекает от множества планов область, содержащую точку 1. Новый оптимальный нецелочисленный план - точка 2.

Второе ограничение Гомори : 1/4x3 + 7/8S1 - S2 = 1/2, S2 і 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2

Из первого ограничения Гомори: S1 = 18 - 4х1 - 2х2

Получаем: 4х1 + 3х2 + S2 = 20, S2 і 0 или 4х1 + 3х2 Ј 20. Это ограничение отсекает от множества планов область, содержащую точку 2. Новый оптимальный нецелочисленный план - точка 3.

Третье ограничение Гомори : 2/7x3 + 6/7S2 - S3 = 4/7, S3 і 0

Из первого ограничения задачи: х3 = 19 - 2х1 - 5х2

Из второго ограничения Гомори: S2 = 20 - 4х1 - 3х2

После подстановки x3 и S2 в третье ограничение Гомори получаем: 4х1 + 4х2 Ј 22. Это ограничение отсекает от множества планов область, содержащую точку 3. Новый оптимальный нецелочисленный план - точка 4.

Четвертое ограничение Гомори : 1/4S3 - S4 = 1/2, S4 і 0

Из третьего ограничения Гомори: S3 = 22 - 4х1 - 4х2

Получаем: х1 + х2 + S4 = 5, S4 і 0. Отсюда имеем: х1 + х2 Ј 5. Это ограничение отсекает от множества планов область, содержащую точку 4. Новый оптимальный нецелочисленный план - точка 5.

Пятое ограничение Гомори : 1/3x4 + 2/3S4 - S5 = 2/3, S5 і 0

Из второго ограничения задачи: х4 = 16 - 4х1 - х2

Из четвертого ограничения Гомори: S4 = 5 - х1 - х2

Получаем: 2х1 + х2 + S5 = 8, S5 і 0. Отсюда: 2х1 + х2 Ј 8. Это ограничение отсекает от множества планов область, содержащую точку 5. Оптимальный целочисленный план - точка 6 с координатами (3;2).

Заштрихованная часть - целочисленное множество планов.

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

...