11773

Решение задачи целочисленного ЛП с помощью динамического программирования

Курсовая

Информатика, кибернетика и программирование

Курсовая работа по дисциплине МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ на тему Решение задачи целочисленного ЛП с помощью динамического программирования АННОТАЦИЯ Курсовая работа содержит 40 страниц 8 формул 17 таблиц 10 литературных источников. В ...

Русский

2013-04-11

481.5 KB

60 чел.

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

по дисциплине «МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ»

на тему

«Решение задачи целочисленного ЛП с помощью динамического программирования»

АННОТАЦИЯ

Курсовая работа содержит 40 страниц, 8 формул, 17 таблиц, 10 литературных источников.

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

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

В третьем разделе приведении программная реализация метода отсекающихся плоскостей для решения ЗЦЛП.

Целочисленное линейное программирование, метод Гомори, метод ветвей и границ, алгоритм, симплекс метод, оптимальное решение, допустимое решение.


СОДЕРЖАНИЕ

Введение ………………………………………………………………………….

4

   1. Общие понятия о целочисленном линейном программировании

6

1.1 Постановка линейной целочисленной задачи

6

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

7

2. Использование метода отсекающих плоскостей для решения задачи линейного целочисленного программирования

14

3. Программная  реализация метода отсекающихся плоскостей для решения ЗЦЛП

27

3.1 Описание программы

27

3.2 Тестовые задания для программы

28

Выводы ……………………………………………………………………………...

33

Литература…………………………………………………………………………

34

Приложение А

35


ВВЕДЕНИЕ

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

Целочисленное программирование – раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов решаться любые задачи целочисленного программирования. Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений. Цель решения задачи – найти наилучшую вершину симплекса. Дисциплины, в которых изучаются модели и методы оптимизации («Методы оптимизации и теория принятия решений», «Исследование операций», Математические модели исследования экономики и математическое программирование») присутствуют во многих образовательных программах высшего профессионального образования. Как правило, это программы по направлениям инженерного образования, и по направлениям, связанным с управлением (менеджментом) и экономикой.

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


1. ОБЩИЕ ПОНЯТИЯ О ЦЕЛОЧИСЛЕННОМ ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

1.1 Постановка линейной целочисленной задачи

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

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

Среди совокупности n неделимых предметов, каждый i-ый (i=1,2, ... , n) из которых обладает по j-ой характеристике показателем  и полезностью , найти такой набор, который позволяет максимизировать эффективность использования ресурсов величины .

Математическая модель этой задачи может быть представлена следующим образом:

в области, определенной условиями

     (1.1)

      (1.2)

- целые, . (1.3)

найти решение , при котором максимизируется (минимизируется) значение целевой функции

          (1.4)

Если , то (1.1-1.4) является моделью частично целочисленной задачи.

Но нас будет интересовать случай, когда , то есть когда (1.1-1.4) является моделью полностью целочисленной задачи.

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

Вектор , удовлетворяющий условиям (1.1-1.3), называется допустимым решением задачи (1.1—1.4). Допустимое решение, при котором функция (1.4) достигает наибольшего (наименьшего) значения, называется оптимальным решением.

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

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

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

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

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

Для иллюстрации основной идеи методов решения задач целочисленного программирования, известных как методы отсечений, рассмотрим полностью целочисленную задачу, множество допустимых решений которой изображено на рисунке 1.1. Допустимым решениям этой задачи соответствуют не все точки множества G допустимых решений, а лишь те, координаты которых удовлетворяют требованию целочисленности. Теоретически из множества G всегда можно выделить такое подмножество G*, что (см. рис. 1.1):

а) оно содержит все точки множества G, координаты которых удовлетворяют требованию целочисленности;

б) оно является выпуклым множеством;

в) координаты всех его крайних точек удовлетворяют требованию целочисленности.

Рисунок 1.1

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

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

Наиболее известным комбинаторным методом является метод ветвей и границ, использующий процедуру решения задачи линейного программирования с ослабленными ограничениями, соответствующей исходной задаче целочисленного программирования. Если оптимальное решение X* задачи линейного программирования с ослабленными ограничениями не удовлетворяет требованию целочисленности (на рисунке 1.2 этому решению соответствует точка В), то из множества G допустимых решений выделяют два непересекающихся выпуклых подмножества К1 и К2, содержащих все допустимые решения из G, удовлетворяющих требованию целочисленности и не содержащих X* (см. рис. 1.2). Это позволяет заменить рассматриваемую задачу целочисленного программирования совокупностью двух эквивалентных ей задач с множествами допустимых решений К1 и К2 соответственно, так как  или .

Рисунок 1.2

Комбинаторные методы широко используют для решения задач булева программирования, т.е. для решения полностью целочисленных задач, переменные которых принимают значения из множества {0, 1}. Эти переменные называют булевыми переменными. Свойства булевых переменных позволяют существенно упростить процедуры поиска оптимального решения.

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

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

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

Элемент 3. В результате анализа решения ослабленной задачи в зависимости от специфики метода, как правило, принимается решение, относящееся к задаче-истоку:

а) исключить ее из рассмотрения;

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

в) заменить системой порожденных задач.

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

                                 (1.5)

и находят решение задачи

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

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

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

                                     (1.6)

где определяются из следующих соотношений:

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

                             (1.7)

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

                    (1.8)

Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные этапы:

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

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

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

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

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


2. ИСПОЛЬЗОВАНИЕ МЕТОДА ОТСЕКАЮЩИХ ПЛОСКОСТЕЙ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

2.1 Сборка и подготовка исходных данных

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

  1.  машины типа «А» и «В»;
  2.  стоимостью 2 ден.ед. и 5 ден.ед.;
  3.  площадь не должно превышать 4 кв.м и 1 кв.м.

Требуется установить машины типа «А» и «В»стоимостью 2 ден.ед. и 5 ден.ед., занимающие площадь 4 кв.м и 1 кв.м и обеспечивающие производительность за смену 8 т и 6 т продукции. Для разработки данного плана рассматривается решение задачи с использованием симплекс таблиц. Для получения целочисленных результатов используется метод Гомори как метод уточнения симплекс таблицы.

Базис

С

базис

В

8

6

0

0

х1

х2

х3

х4

х3

0

16

4

2

1

0

х4

0

19

1

5

0

1

j

-8

-6

0

0

Таблица 2.1– Симплекс таблица

Для решения задачи методом Гомори обозначим через х1 – количество производственную площадь кв.м., через х2 – стоимость машин в ден.ед., через х3 – количество выделяемого предприятием ден.ед., х4 – количество не превышающей ден.ед..

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

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

1+ 2х2≤ 16

х1 + 5х1 ≤1 9

Цель задачи можно выразить в виде линейной функции

 Z= xmax

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

 Z= xmax

1+ 2х2≤ 16

х1 + 5х1 ≤1 9

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

Z= xmax

и ограничений вида:

1+ 2х2≤ 16

х1+ 5х1 ≤1 9

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

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

Определим максимальное значение целевой функции F(X) = 8x1 + 6x2 при следующих условиях-ограничений.

4x1 + 2x2≤16

x1 + 5x2≤19

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

4x1 + 2x2 + 1x3 + 0x4 = 16

1x1 + 5x2 + 0x3 + 1x4 = 19

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

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

x3, x4,

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

X1 = (0,0,16,19)

Базис

B

x1

x2

x3

x4

x3

16

4

2

1

0

x4

19

1

5

0

1

F(X0)

0

-8

-6

0

0

Таблица 2.2 - Получение первой симплекс таблицы

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

Итерация №0.

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

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

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

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

min (16 : 4 , 19 : 1 ) = 4

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

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

Базис

B

x1

x2

x3

x4

min

x3

16

4

2

1

0

4

x4

19

1

5

0

1

19

F(X1)

0

-8

-6

0

0

0

Таблица 2.3 – Нахождение разрешающего элемента

Базис

B

x1

x2

x3

x4

x1

4

1

1/2

1/4

0

x4

15

0

41/2

-1/4

1

F(X1)

32

0

-2

2

0

Таблица 2.4 -  Получение симплекс-таблицы

Итерация №1.

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

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

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

и из них выберем наименьшее:  min (4 :1/2 , 15 : 41/2 ) = 31/3

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

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

Базис

B

x1

x2

x3

x4

min

x1

4

1

1/2

1/4

0

8

x4

15

0

41/2

-1/4

1

31/3

F(X2)

32

0

-2

2

0

0

Таблица 2.5 – Нахождение разрешающего элемента

Базис

B

x1

x2

x3

x4

x1

21/3

1

0

5/18

-1/9

x2

31/3

0

1

-1/18

2/9

F(X2)

382/3

0

0

18/9

4/9

Таблица 2.6 -  Получение симплекс-таблицы

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

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

x1 = 21/3

x2 = 31/3

F(X) = 8•21/3 + 6•31/3 = 382/3

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

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

По 3-у уравнению с переменной x, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:

q3 - q31•x1 - q32•x2 - q33•x3 - q34•x4≤0

q3 = b3 - [b3] = 382/3 - 38 = 2/3

q31 = a31 - [a31] = 0 - 0 = 0

q32 = a32 - [a32] = 0 - 0 = 0

q33 = a33 - [a33] = 18/9 - 1 = 8/9

q34 = a34 - [a34] = 4/9 - 0 = 4/9

Дополнительное ограничение имеет вид:   2/3-8/9x3-4/9x4≤0

Преобразуем полученное неравенство в уравнение: 2/3-8/9x3-4/9x4 + x5 = 0, коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X).

Базис

B

x1

x2

x3

x4

x5

x1

21/3

1

0

5/18

-1/9

0

x2

31/3

0

1

-1/18

2/9

0

x5

-2/3

0

0

-8/9

-4/9

1

F(X0)

-382/3

0

0

-18/9

-4/9

0

Таблица 2.7 -  Составление нового ограничения

План 0 в симплексной таблице является псевдо планом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-4/9).

Базис

B

x1

x2

x3

x4

x5

x1

21/3

1

0

5/18

-1/9

0

x2

31/3

0

1

-1/18

2/9

0

x5

-2/3

0

0

-8/9

-4/9

1

F(X)

-382/3

0

0

-18/9

-4/9

0

Таблица 2.8 – Нахождение разрешающего элемента

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

По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 1/2, составляем дополнительное ограничение:

q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5≤0

q1 = b1 - [b1] = 21/2 - 2 = 1/2

q11 = a11 - [a11] = 1 - 1 = 0

q12 = a12 - [a12] = 0 - 0 = 0

q13 = a13 - [a13] = 1/2 - 0 = 1/2

q14 = a14 - [a14] = 0 - 0 = 0

q15 = a15 - [a15] = -1/4 + 1 = 3/4

Дополнительное ограничение имеет вид:  1/2-1/2x3-3/4x5≤0

Преобразуем полученное неравенство в уравнение: 1/2-1/2x3-3/4x5 + x6 = 0, коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис

B

x1

x2

x3

x4

x5

x6

x1

21/2

1

0

1/2

0

-1/4

0

x2

3

0

1

-1/2

0

1/2

0

x4

11/2

0

0

2

1

-21/4

0

x6

-1/2

0

0

-1/2

0

-3/4

1

F(X0)

-38

0

0

-1

0

-1

0

Таблица 2.9 -  Составление нового ограничения

План 0 в симплексной таблице является псевдо планом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3/4).

Базис

B

x1

x2

x3

x4

x5

x6

x1

21/2

1

0

1/2

0

-1/4

0

x2

3

0

1

-1/2

0

1/2

0

x4

11/2

0

0

2

1

-21/4

0

x6

-1/2

0

0

-1/2

0

-3/4

1

F(X)

-38

0

0

-1

0

-1

0

Таблица 2.10 – Нахождение разрешающего элемента

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

По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:

q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5 - q16•x6≤0

q1 = b1 - [b1] = 22/3 - 2 = 2/3

q11 = a11 - [a11] = 1 - 1 = 0

q12 = a12 - [a12] = 0 - 0 = 0

q13 = a13 - [a13] = 2/3 - 0 = 2/3

q14 = a14 - [a14] = 0 - 0 = 0

q15 = a15 - [a15] = 0 - 0 = 0

q16 = a16 - [a16] = -1/3 + 1 = 2/3

Дополнительное ограничение имеет вид: 2/3-2/3x3-2/3x6≤0

Преобразуем полученное неравенство в уравнение:2/3-2/3x3-2/3x6 + x7 = 0, коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу

Базис

B

x1

x2

x3

x4

x5

x6

x7

x1

22/3

1

0

2/3

0

0

-1/3

0

x2

22/3

0

1

-5/6

0

0

2/3

0

x4

3

0

0

31/2

1

0

-3

0

x5

2/3

0

0

2/3

0

1

-11/3

0

x7

-2/3

0

0

-2/3

0

0

-2/3

1

F(X0)

-371/3

0

0

-1/3

0

0

-11/3

0

Таблица 2.11 -  Составление нового ограничения

План 0 в симплексной таблице является псевдо планом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/3).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x1

22/3

1

0

2/3

0

0

-1/3

0

x2

22/3

0

1

-5/6

0

0

2/3

0

x4

3

0

0

31/2

1

0

-3

0

x5

2/3

0

0

2/3

0

1

-11/3

0

x7

-2/3

0

0

-2/3

0

0

-2/3

1

F(X)

-371/3

0

0

-1/3

0

0

-11/3

0

Таблица 2.12 – Нахождение разрешающего элемента

План 1 в симплексной таблице является псевдо планом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-61/2).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x1

2

1

0

0

0

0

-1

1

x2

31/2

0

1

0

0

0

11/2

-11/4

x4

-1/2

0

0

0

1

0

-61/2

51/4

x5

0

0

0

0

0

1

-2

1

x3

1

0

0

1

0

0

1

-11/2

F(X)

-37

0

0

0

0

0

-1

-1/2

Таблица 2.13 – Нахождение разрешающего элемента

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

По 5-у уравнению с переменной x3, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 12/13, составляем дополнительное ограничение:

q5 - q51•x1 - q52•x2 - q53•x3 - q54•x4 - q55•x5 - q56•x6 - q57•x7≤0

q5 = b5 - [b5] = 12/13 - 0 = 12/13

q51 = a51 - [a51] = 0 - 0 = 0

q52 = a52 - [a52] = 0 - 0 = 0

q53 = a53 - [a53] = 1 - 1 = 0

q54 = a54 - [a54] = 2/13 - 0 = 2/13

q55 = a55 - [a55] = 0 - 0 = 0

q56 = a56 - [a56] = 0 - 0 = 0

q57 = a57 - [a57] = -9/13 + 1 = 4/13

Дополнительное ограничение имеет вид: 12/13-2/13x4-4/13x7≤0

Преобразуем полученное неравенство в уравнение: 12/13-2/13x4-4/13x7 + x8 = 0, коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x1

21/13

1

0

0

-2/13

0

0

5/26

0

x2

35/13

0

1

0

3/13

0

0

-1/26

0

x6

1/13

0

0

0

-2/13

0

1

-21/26

0

x5

2/13

0

0

0

-4/13

1

0

-8/13

0

x3

12/13

0

0

1

2/13

0

0

-9/13

0

x8

-12/13

0

0

0

-2/13

0

0

-4/13

1

F(X0)

-3612/13

0

0

0

-2/13

0

0

-14/13

0

Таблица 2.14 -  Составление нового ограничения

План 0 в симплексной таблице является псевдо планом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/13).

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x1

21/13

1

0

0

-2/13

0

0

5/26

0

x2

35/13

0

1

0

3/13

0

0

-1/26

0

x6

1/13

0

0

0

-2/13

0

1

-21/26

0

x5

2/13

0

0

0

-4/13

1

0

-8/13

0

x3

12/13

0

0

1

2/13

0

0

-9/13

0

x8

-12/13

0

0

0

-2/13

0

0

-4/13

1

F(X)

-3612/13

0

0

0

-2/13

0

0

-14/13

0

Таблица 2.15 – Нахождение разрешающего элемента

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x1

3

1

0

0

0

0

0

0

0

x2

2

0

1

0

0

0

0

0

0

x6

1

0

0

0

0

0

1

0

0

x5

2

0

0

0

0

1

0

0

-2

x3

0

0

0

1

0

0

0

-1

1

x4

6

0

0

0

1

0

0

2

0

F(X0)

36

0

0

0

0

0

0

1

1

Таблица 2.16Получение симплекс таблицы

Решение получилось целочисленным. Ответ: х1=3, х2=2, х3=0, х4=6, х5=2, х6=1, Хопт=(6;4;0;2), Zmax(Xопт)=36


3. ПРОГРАММНАЯ  РЕАЛИЗАЦИЯ МЕТОДА ОТСЕКАЮЩИХСЯ ПЛОСКОСТЕЙ ДЛЯ РЕШЕНИЯ ЗЦЛП

3.1 Описание программы

При разработке программы использовались вещественный тип (real), целочисленный тип (byte, integer) и логический тип (Boolean). Некоторые данные представляют собой вектор или матрицу размерностью в 18 столбцов и 6 строк. Размерность взята максимальной, потому что в данной программе не используются динамические массивы. Поэтому количество ограничений в программе не может быть больше 6 и количество свободных переменных также не может превышать 6. Нумерация элементов начинается с единицы, но переменная коэффициентов целевой функции содержит нулевой элемент, предназначенный для числа, которое необходимо непосредственно прибавить к значению целевой функции без переменной x. Есть данные, которые имеют вещественный тип, так как в ходе решения симплексным методом возможны нецелые величины, пусть даже условие содержит только целые числа. Для хранения индексов целесообразно использовать целочисленный тип, потому что индексы могут быть только целыми значениями.

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

Имя

Тип

Назначение

tb

array[1..20] of real

коэффициенты системы ограничений

s,s1,s2,s3,s4,s5

real

Индексы базисных переменных

i, j

integer

Счетчики

A,b

real

Переменная для временного хранения значение

Таблица 3.1 – Идентификаторы программы

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

Запуская программу, начинается с вызова главной формы Form1 с исходными данными. В процедуре – обработчике кнопки TForm1. Button1Click ( Sender:TObject ) происходит формирования первой симплекс таблицы.

После вывода исходной таблицы, можно приступить к расчету, для этого служит кнопка «Решить задачу». Для этого вызывается процедура – обработчик TForm1.Button1Click ( Sender:TObject ).

При активизации формы Form1 вызывается процедура TForm1. FormActivate ( Sender:TObject ), автоматический заполняется исходные данные.

procedure TForm1.FormActivate(Sender: TObject);

begin

StringGrid1.Cells[0,0]:='8'; StringGrid1.Cells[1,0]:='6';

StringGrid2.Cells[0,0]:='4'; StringGrid2.Cells[1,0]:='2';

StringGrid2.Cells[0,1]:='1'; StringGrid2.Cells[1,1]:='5';

i:=0;

end;

3.2 Тестовые задания для программы

При запуске программы вводятся данные. Эти данные при нажатии кнопки

« Решить задачу» выводится на первую симплекс таблицу (рисунок 3.1).

Рисунок 3.1 – Ввод данных.

Первая симплексная таблица пересчитывается, и новые данные заполняются в следующую таблицу (рисунок 3.2).

Рисунок 3.2 – Результат расчета первой симплексной таблицы

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

Рисунок 3.3 – Получения результата

Получения результата симплекс методом, но решение не является целочисленным. Для этого составляем новое ограничения (рисунок 3.4).

Рисунок 3.4 – Составления нового ограничения


Решение не является целочисленным, добавляем еще ограничения (рисунок 3.5).

Рисунок 3.5 – Добавления ограничения

Решение не является целочисленным, добавляем еще ограничения (рисунок 3.6).

Рисунок 3.6 – Добавления ограничения

Решение не является целочисленным, добавляем еще ограничения (рисунок 3.7).

Рисунок 3.7 – Добавления ограничения

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

ЗАКЛЮЧЕНИЕ

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

Была разработана программа для решения задач целочисленного программирования методом Гомори. Задачи могут быть с любой размерностью (количество переменных и ограничений) от 2 до 6. В системе ограничений может быть любой знак, и задача может решаться как на максимум, так и на минимум. В программе также предусмотрен вывод итерации и ответа в понятном пользователю виде. А также программа представляет собой дополнительные возможности для удобства работы с ней, например, чтобы не пришлось очищать каждую ячейку вручную, существует команда для очистки введенных пользователем данных. Чтобы не пришлось выдумывать задачу для просмотра ее решения, предусмотрена возможность ввода заложенной по умолчанию задачи одной командой. Эта программа может применяться везде, где требуется решать ЗЦП.


СПИСОК ИССПОЛЬЗОВАНОЙ ЛИТЕРАТУРЫ

  1.  Абланская Л.В., Бабешко Л.О., Баусов Л.И. Экономико-математическое моделирование: М.: Экзамен, 2006г. – 800с.
  2.  Баканов М.И., Шеремет А.Д. Теория экономического анализа: Учебник. - М.: Финансы и статистика, 1997.
  3.  Дрогобыцкого И.Н Экономико-математическое моделирование: М.: Экзамен, 2004г. – 323с.
  4.  Замков О.О., Толстопятенко А.В. Математические методы в экономике. М.:ДИС, 1997
  5.  Казаков О.Л., Миненко С.Н., Смирнов Г.Б. Экономико-математическое моделирование: учебно-методическое пособие. – М.: МГИУ, 2006. - 136 с.
  6.  Конюховский П.В Математические методы исследования операций в экономике: С-Петербург: Питер 2003г. - 208 с.
  7.  Кремер Н.Ш., Путко Б.А. и др. Исследования операций в экономике. Учебное пособие .М.:Юнити, 1997
  8.  МалыхинВ.И. Математическое моделирование экономики. М., 1998
  9.  Нусупбеков С.И., Устенова О.Ж. Математические методы моделирования экономических систем. Алматы: Эваеро, 2002
  10.  Федосеев В.В., Гармаш А.Н. и др. Экономико-математические методы и прикладные модели. М.:Юнити, 2001

 


ПРИЛОЖЕНИЕ А

При нажатии на кнопку ‘Решить задачу’ вызывается процедура TForm1. Button1Click (Sender: TObject), где выполняется решения данного задания.

Структура программы

unit Unit1;

interface

uses

 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

 Dialogs, StdCtrls, Grids, XPMan;

type

 TForm1 = class(TForm)

   StringGrid1: TStringGrid;

   StringGrid2: TStringGrid;

   StringGrid3: TStringGrid;

   Memo1: TMemo;

   Button1: TButton;

   XPManifest1: TXPManifest;

   Label3: TLabel;

procedure FormActivate(Sender: TObject);

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

 Form1: TForm1;

i:integer;

implementation

uses Unit2;

{$R *.dfm}

procedure TForm1.FormActivate(Sender: TObject);

begin

StringGrid1.Cells[0,0]:='8'; StringGrid1.Cells[1,0]:='6';

StringGrid2.Cells[0,0]:='4'; StringGrid2.Cells[1,0]:='2';

StringGrid2.Cells[0,1]:='1'; StringGrid2.Cells[1,1]:='5';

i:=0;

end;

unit Unit2;

interface

uses

 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

 Dialogs, StdCtrls, ArialLabel1, Buttons;

type

 TForm2 = class(TForm)

   BitBtn1: TBitBtn;

   BitBtn2: TBitBtn;

   ArialLabel11: TArialLabel1;

procedure BitBtn1Click(Sender: TObject);

procedure BitBtn2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

 Form2: TForm2;

implementation

uses Unit1;

{$R *.dfm}

procedure TForm2.BitBtn1Click(Sender: TObject);

begin

Form2.Close;

Form1.Close;

end;

procedure TForm2.BitBtn2Click(Sender: TObject);

begin

Form2.Close;

end;

end.

Листинг программы

procedureTForm1.Button1Click(Sender: TObject);

begin

StringGrid3.Cells[3,0]:='x1';StringGrid3.Cells[4,0]:='x2'; StringGrid3.Cells[5,0]:='x3'; StringGrid3.Cells[6,0]:='x4';

casei of

0:begin StringGrid3.Cells[0,1]:='Базис';    StringGrid3.Cells[1,1]:='С';

StringGrid3.Cells[0,2]:='х3'; StringGrid3.Cells[1,2]:='0';        StringGrid3.Cells[0,3]:='х4';       StringGrid3.Cells[1,3]:='0';

       StringGrid3.Cells[0,4]:='Дельтj';StringGrid3.Cells[2,1]:='B';StringGrid3.Cells[2,2]:='16';       StringGrid3.Cells[2,3]:='19';

StringGrid3.Cells[2,4]:='0'; StringGrid3.Cells[6,1]:='0';        StringGrid3.Cells[3,1]:='8';        StringGrid3.Cells[6,2]:='0';

StringGrid3.Cells[3,2]:='4'; StringGrid3.Cells[6,3]:='1';        StringGrid3.Cells[3,3]:='1';        StringGrid3.Cells[6,4]:='0';

StringGrid3.Cells[3,4]:='-8'; StringGrid3.Cells[5,4]:='1';        StringGrid3.Cells[4,1]:='6';        StringGrid3.Cells[5,3]:='0';

StringGrid3.Cells[4,2]:='2'; StringGrid3.Cells[5,2]:='1';        StringGrid3.Cells[4,3]:='5';        StringGrid3.Cells[5,1]:='0';

StringGrid3.Cells[4,4]:='-6';

memo1.Lines.Add('Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты');

i:=i+1;end;

1:begin StringGrid3.Cells[0,1]:='Базис';   StringGrid3.Cells[1,1]:='С';

StringGrid3.Cells[0,2]:='х1'; StringGrid3.Cells[1,2]:='8';        StringGrid3.Cells[0,3]:='х4';      StringGrid3.Cells[1,3]:='0';

StringGrid3.Cells[0,4]:='Дельта j';StringGrid3.Cells[5,1]:='0'; StringGrid3.Cells[2,1]:='B';       StringGrid3.Cells[5,2]:='1';

StringGrid3.Cells[2,2]:='4'; StringGrid3.Cells[5,3]:='-1/4'; StringGrid3.Cells[2,3]:='15';      StringGrid3.Cells[5,4]:='2';

StringGrid3.Cells[2,4]:='32'; StringGrid3.Cells[6,1]:='0';        StringGrid3.Cells[3,1]:='8';       StringGrid3.Cells[6,2]:='0';

StringGrid3.Cells[3,2]:='1'; StringGrid3.Cells[6,3]:='1';        StringGrid3.Cells[3,3]:='0';       StringGrid3.Cells[6,4]:='0';

StringGrid3.Cells[3,4]:='0'; StringGrid3.Cells[4,4]:='-2';        StringGrid3.Cells[4,1]:='6';       StringGrid3.Cells[4,3]:='9/2';

StringGrid3.Cells[4,2]:='1/2';     i:=i+1;

memo1.Lines.Add('Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты');

end;

2:begin StringGrid3.Cells[0,1]:='Базис';   StringGrid3.Cells[3,1]:='8';

StringGrid3.Cells[0,2]:='х1'; StringGrid3.Cells[3,2]:='1'; StringGrid3.Cells[0,3]:='х2'; StringGrid3.Cells[3,3]:='0';

StringGrid3.Cells[0,4]:='Дельта j';StringGrid3.Cells[3,4]:='0'; StringGrid3.Cells[1,1]:='С'; StringGrid3.Cells[4,1]:='6';

StringGrid3.Cells[1,2]:='8'; StringGrid3.Cells[4,2]:='0'; StringGrid3.Cells[1,3]:='6'; StringGrid3.Cells[4,3]:='1';

StringGrid3.Cells[2,1]:='B'; StringGrid3.Cells[4,4]:='0'; StringGrid3.Cells[2,2]:='7/3'; StringGrid3.Cells[5,1]:='0';

StringGrid3.Cells[2,3]:='10/3';StringGrid3.Cells[5,2]:='5/18';StringGrid3.Cells[2,4]:='116/3';

StringGrid3.Cells[5,3]:='-1/18';StringGrid3.Cells[5,4]:='17/9';StringGrid3.Cells[6,4]:='4/9';StringGrid3.Cells[6,1]:='0';       StringGrid3.Cells[6,3]:='2/9';  StringGrid3.Cells[6,2]:='-1/9';    memo1.Clear;

memo1.Lines.Add('Оптимальныйпланможнозаписатьтак:');memo1.Lines.Add('x1 = 7/3');memo1.Lines.Add('x2 = 10/3');

memo1.Lines.Add('F(X) = 8*7/3 + 6*10/3 = 116/3');i:=i+1;end;

3:begin StringGrid3.Cells[0,1]:='Базис';   StringGrid3.Cells[7,0]:='x5';

StringGrid3.Cells[0,2]:='х1'; StringGrid3.Cells[4,1]:='6'; StringGrid3.Cells[0,3]:='х2'; StringGrid3.Cells[4,2]:='0';

StringGrid3.Cells[0,4]:='х5'; StringGrid3.Cells[4,3]:='1'; StringGrid3.Cells[0,5]:='Дельта j';StringGrid3.Cells[4,4]:='0';

StringGrid3.Cells[1,1]:='С'; StringGrid3.Cells[4,5]:='0';        StringGrid3.Cells[1,2]:='8';       StringGrid3.Cells[6,1]:='0';

StringGrid3.Cells[1,3]:='6'; StringGrid3.Cells[6,2]:='-1/9'; StringGrid3.Cells[1,4]:='0';       StringGrid3.Cells[6,3]:='2/9';

StringGrid3.Cells[2,1]:='B'; StringGrid3.Cells[6,4]:='4/9'; StringGrid3.Cells[2,2]:='7/3';     StringGrid3.Cells[6,5]:='4/9';

StringGrid3.Cells[2,3]:='10/3'; StringGrid3.Cells[7,1]:='0'; StringGrid3.Cells[2,4]:='-2/3';    StringGrid3.Cells[7,2]:='0';

StringGrid3.Cells[2,5]:='116/3'; StringGrid3.Cells[7,3]:='0'; StringGrid3.Cells[3,1]:='8';       StringGrid3.Cells[7,4]:='1';

StringGrid3.Cells[3,2]:='1';StringGrid3.Cells[7,5]:='0';        StringGrid3.Cells[3,3]:='0';       StringGrid3.Cells[5,5]:='17/9';

StringGrid3.Cells[3,4]:='0'; StringGrid3.Cells[5,4]:='-1/18';       StringGrid3.Cells[3,5]:='0';       StringGrid3.Cells[5,3]:='-1/18';

StringGrid3.Cells[5,1]:='0';       StringGrid3.Cells[5,2]:='5/18';

memo1.Lines.Add('По 3-у уравнению с переменной x, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение');i:=i+1;end;

4:begin StringGrid3.Cells[0,1]:='Базис';   StringGrid3.Cells[8,0]:='x6';

StringGrid3.Cells[0,2]:='х1'; StringGrid3.Cells[5,1]:='0'; StringGrid3.Cells[0,3]:='х2';      StringGrid3.Cells[5,2]:='1/2';

StringGrid3.Cells[0,4]:='x4'; StringGrid3.Cells[5,3]:='-1/2'; StringGrid3.Cells[0,5]:='x6';      StringGrid3.Cells[5,4]:='2';

       StringGrid3.Cells[0,6]:='Дельтаj';StringGrid3.Cells[5,5]:='-1/2';StringGrid3.Cells[1,1]:='С';   StringGrid3.Cells[5,6]:='-1';

StringGrid3.Cells[1,2]:='8'; StringGrid3.Cells[6,1]:='0'; StringGrid3.Cells[1,3]:='6';       StringGrid3.Cells[6,2]:='0';

StringGrid3.Cells[1,4]:='1'; StringGrid3.Cells[6,3]:='0'; StringGrid3.Cells[1,5]:='0';       StringGrid3.Cells[6,4]:='1';

StringGrid3.Cells[2,1]:='B'; StringGrid3.Cells[6,5]:='0'; StringGrid3.Cells[2,2]:='5/2';     StringGrid3.Cells[6,6]:='0';

StringGrid3.Cells[2,3]:='2';       StringGrid3.Cells[7,1]:='0'; StringGrid3.Cells[2,4]:='3/2';     StringGrid3.Cells[7,2]:='-1/4';

StringGrid3.Cells[2,5]:='-1/2'; StringGrid3.Cells[7,3]:='1/2'; StringGrid3.Cells[2,6]:='-38';   StringGrid3.Cells[7,4]:='-9/4';

StringGrid3.Cells[3,1]:='8'; StringGrid3.Cells[7,5]:='-3/4';        StringGrid3.Cells[3,2]:='1';      StringGrid3.Cells[7,6]:='-1';

StringGrid3.Cells[3,3]:='0';       StringGrid3.Cells[8,1]:='0'; StringGrid3.Cells[3,4]:='0';       StringGrid3.Cells[8,2]:='0';

StringGrid3.Cells[3,5]:='0';       StringGrid3.Cells[8,3]:='0'; StringGrid3.Cells[3,6]:='0';       StringGrid3.Cells[8,4]:='0';

StringGrid3.Cells[4,1]:='6';       StringGrid3.Cells[8,5]:='1'; StringGrid3.Cells[4,2]:='0';       StringGrid3.Cells[8,6]:='0';

StringGrid3.Cells[4,3]:='1';       StringGrid3.Cells[4,6]:='0'; StringGrid3.Cells[4,4]:='0';       StringGrid3.Cells[4,5]:='0';

memo1.Lines.Add('В полученном оптимальном плане присутствуют дробные числа.');i:=i+1;end;

5:begin StringGrid3.Cells[0,1]:='Базис';    StringGrid3.Cells[8,0]:='x6';

       StringGrid3.Cells[0,2]:='х1';       StringGrid3.Cells[9,0]:='x7';StringGrid3.Cells[0,3]:='х2';StringGrid3.Cells[2,1]:='B';

StringGrid3.Cells[0,4]:='x4'; StringGrid3.Cells[2,2]:='8/3'; StringGrid3.Cells[0,5]:='x5'; StringGrid3.Cells[2,3]:='8/3';

StringGrid3.Cells[0,6]:='x7'; StringGrid3.Cells[2,4]:='3'; StringGrid3.Cells[0,7]:='Дельта j'; StringGrid3.Cells[2,5]:='2/3';

       StringGrid3.Cells[7,1]:='0';StringGrid3.Cells[2,6]:='-2/3'; StringGrid3.Cells[1,1]:='С';StringGrid3.Cells[2,7]:='-112/3';

       StringGrid3.Cells[1,2]:='8';StringGrid3.Cells[1,5]:='-3/4'; StringGrid3.Cells[1,3]:='6';StringGrid3.Cells[1,6]:='0';

StringGrid3.Cells[1,4]:='1'; StringGrid3.Cells[4,6]:='0';        StringGrid3.Cells[3,1]:='8';        StringGrid3.Cells[4,7]:='0';

StringGrid3.Cells[3,2]:='1'; StringGrid3.Cells[6,7]:='0';        StringGrid3.Cells[3,3]:='0';        StringGrid3.Cells[4,1]:='6';

StringGrid3.Cells[3,4]:='0'; StringGrid3.Cells[4,2]:='0';        StringGrid3.Cells[3,5]:='0';        StringGrid3.Cells[4,3]:='1';

StringGrid3.Cells[3,6]:='0'; StringGrid3.Cells[4,4]:='0';        StringGrid3.Cells[3,7]:='0';        StringGrid3.Cells[4,5]:='0';

StringGrid3.Cells[6,1]:='0'; StringGrid3.Cells[6,6]:='0';        StringGrid3.Cells[5,1]:='0';        StringGrid3.Cells[6,2]:='0';

StringGrid3.Cells[5,2]:='2/3'; StringGrid3.Cells[6,3]:='0'; StringGrid3.Cells[5,3]:='-5/6';     StringGrid3.Cells[6,4]:='1';

StringGrid3.Cells[5,4]:='7/2'; StringGrid3.Cells[6,5]:='0'; StringGrid3.Cells[5,5]:='2/3';      StringGrid3.Cells[7,2]:='0';

       StringGrid3.Cells[5,6]:='-2/3'; StringGrid3.Cells[7,3]:='0'; StringGrid3.Cells[5,7]:='-1/3';     StringGrid3.Cells[7,4]:='0';        StringGrid3.Cells[7,5]:='1'; StringGrid3.Cells[7,6]:='0'; StringGrid3.Cells[7,7]:='0'; StringGrid3.Cells[8,1]:='0'; StringGrid3.Cells[8,2]:='-1/3';     StringGrid3.Cells[8,3]:='2/3';        StringGrid3.Cells[8,4]:='-3'; StringGrid3.Cells[8,5]:='-4/3'; StringGrid3.Cells[8,6]:='-2/3';     StringGrid3.Cells[8,7]:='-4/3';

StringGrid3.Cells[9,1]:='0'; StringGrid3.Cells[9,7]:='0';        StringGrid3.Cells[9,2]:='0';        StringGrid3.Cells[9,6]:='1';

StringGrid3.Cells[9,3]:='0';        StringGrid3.Cells[9,5]:='0';        StringGrid3.Cells[9,4]:='0';        i:=i+1;

memo1.Lines.Add('В полученном оптимальном плане присутствуют дробные числа.');  end;

6:begin StringGrid3.Cells[0,1]:='Базис';    StringGrid3.Cells[8,0]:='x6';

StringGrid3.Cells[0,2]:='х1'; StringGrid3.Cells[9,0]:='x7'; StringGrid3.Cells[0,3]:='х2';       StringGrid3.Cells[10,0]:='x8';

       StringGrid3.Cells[0,4]:='x6';StringGrid3.Cells[0,8]:='Дельтаj';StringGrid3.Cells[0,5]:='x5'; StringGrid3.Cells[0,7]:='x4';

StringGrid3.Cells[0,6]:='x3'; StringGrid3.Cells[1,1]:='С';        StringGrid3.Cells[1,2]:='8';        StringGrid3.Cells[1,3]:='6';

StringGrid3.Cells[1,4]:='1'; StringGrid3.Cells[3,1]:='8';        StringGrid3.Cells[1,5]:='1';        StringGrid3.Cells[3,2]:='1';

StringGrid3.Cells[1,6]:='1'; StringGrid3.Cells[3,3]:='0';        StringGrid3.Cells[1,7]:='0';        StringGrid3.Cells[3,4]:='0';

StringGrid3.Cells[2,1]:='B'; StringGrid3.Cells[3,5]:='0';        StringGrid3.Cells[2,2]:='3';        StringGrid3.Cells[3,6]:='0';

StringGrid3.Cells[2,3]:='2'StringGrid3.Cells[3,7]:='0';        StringGrid3.Cells[2,4]:='1';        StringGrid3.Cells[3,8]:='0';

StringGrid3.Cells[2,5]:='2'StringGrid3.Cells[5,1]:='0';        StringGrid3.Cells[2,6]:='0';        StringGrid3.Cells[5,2]:='0';

StringGrid3.Cells[2,7]:='6'StringGrid3.Cells[5,3]:='0';        StringGrid3.Cells[2,8]:='36';       StringGrid3.Cells[5,4]:='0';

StringGrid3.Cells[4,1]:='6'StringGrid3.Cells[5,5]:='0';        StringGrid3.Cells[4,2]:='0';        StringGrid3.Cells[5,6]:='1';

StringGrid3.Cells[4,3]:='1'StringGrid3.Cells[5,7]:='0';        StringGrid3.Cells[4,4]:='0';        StringGrid3.Cells[5,8]:='0';

StringGrid3.Cells[4,5]:='0'StringGrid3.Cells[6,1]:='0';        StringGrid3.Cells[4,6]:='0';        StringGrid3.Cells[6,2]:='0';

StringGrid3.Cells[4,7]:='0'StringGrid3.Cells[6,3]:='0';        StringGrid3.Cells[4,8]:='0';        StringGrid3.Cells[6,4]:='0';

       StringGrid3.Cells[6,5]:='0'StringGrid3.Cells[7,1]:='0';        StringGrid3.Cells[6,6]:='0';        StringGrid3.Cells[7,2]:='0';        StringGrid3.Cells[6,7]:='1'StringGrid3.Cells[7,3]:='0'StringGrid3.Cells[6,8]:='0'StringGrid3.Cells[7,4]:='0';        StringGrid3.Cells[7,5]:='1'StringGrid3.Cells[7,6]:='0';        StringGrid3.Cells[7,7]:='0';        StringGrid3.Cells[7,8]:='0';

StringGrid3.Cells[8,1]:='0'StringGrid3.Cells[9,1]:='0';        StringGrid3.Cells[8,2]:='0';        StringGrid3.Cells[9,2]:='0';

StringGrid3.Cells[8,3]:='0'StringGrid3.Cells[9,3]:='0';        StringGrid3.Cells[8,4]:='1';        StringGrid3.Cells[9,4]:='0';

StringGrid3.Cells[8,5]:='0'StringGrid3.Cells[9,5]:='0';        StringGrid3.Cells[8,6]:='0';        StringGrid3.Cells[9,6]:='-1';

StringGrid3.Cells[8,7]:='0'StringGrid3.Cells[9,7]:='2';        StringGrid3.Cells[8,8]:='0';        StringGrid3.Cells[9,8]:='1';

StringGrid3.Cells[10,1]:='0'StringGrid3.Cells[10,8]:='1'StringGrid3.Cells[10,2]:='0';       StringGrid3.Cells[10,7]:='0';

StringGrid3.Cells[10,3]:='0'StringGrid3.Cells[10,6]:='1'StringGrid3.Cells[10,4]:='0';       StringGrid3.Cells[10,5]:='-2';

memo1.Lines.Add('Решениеполучилосьцелочисленным.');memo1.Lines.Add('Оптимальныйцелочисленныйпланможнозаписатьтак:');memo1.Lines.Add('х1=3');memo1.Lines.Add('х2=2');memo1.Lines.Add('х6=1');memo1.Lines.Add('х5=2');

memo1.Lines.Add('х3=0');memo1.Lines.Add('х4=6');memo1.Lines.Add('Z=36');i:=i+1;Button1.Caption:='Конец';

end;

7:form2.showmodal;end;end;


Блок - схема


 

А также другие работы, которые могут Вас заинтересовать

52226. Проблема мусора 22.5 KB
  Цель урока: выяснить какие существуют группы отходов откуда берётся мусор сроки разложения различных видов мусора рассмотреть состав мусорной корзины найти пути решения проблемы отходов; учить детей взаимодействию в группе развивать умения делать выводы; воспитывать экологическую культуру. Образовательные задачи: учащиеся должны знать виды и проблемы мусора и предлагать пути их решения; самостоятельно искать пути решения проблемы и добывать знания из дополнительных источников; пользоваться приобретёнными знаниями для решения...
52228. Україна в геополітичних планах країн Антанти і Троїстого союзу 72 KB
  Розкрити причини та привід до початку першої світової війни. Війна; привід до війни світова війна ринки збуту воєннополітичний блок причини війни ультиматум імперіалізм. – оформлення союзу Антанта; 28 червня 1914 року – вбивство в Сараєво ерцгерцога Франца Фердинандаспадкоємця австрійського престолу; 10серпня 1914 року – початок першої світової війни оголошення Німеччиною війни Росії. Після цього уроку учні зможуть: називати роки утворення...
52229. Географічне положення Антарктиди. Історія відкриття і дослідження 2.76 MB
  Мета уроку: сформувати e учнів систему знань про географічне положення Антарктиди; охарактеривувати своєрідність географічного положення материка; розповісти про історію відкриття і дослідження Антарктиди; удосконалювати вміння і навички роботи з картою; розвивати інтерес до предмету. Обладнання: карта Антарктиди контурні карти підручники портрети мандрівників презентація PowerPoint. Ми вирушаємо до Антарктиди слайд 1 Про цій материк полярник А.
52230. Антарктида – льодовий материк планети 93 KB
  Цілі: Виявити особливості унікальності і своєрідності географічного положення природи Антарктиди та Південного океану. Тип уроку: засвоєння нових знань Форма уроку: урок конференція Обладнання: фізична карта півкуль і Антарктиди атлас контурна карта мультимедійна презентація I. Майже в центрі материка розміщений Південний полюс тому всі береги Антарктиди дивляться на північ. Як бачимо географічне положення Антарктиди дуже відрізняється від географічного положення інших континентів.
52231. Античний світ: подорож у минуле 36 KB
  Перше завдання Візитки команд Домашнє завдання . Другим завданням нашої історичної подорожі є похід до керамічної майстерні. Завдання дітям: виконати малюнок на кольоровому папері чорним фломастером: Розпис амфор . Завдання: розіграти сценку давньогрецької комедії та трагедії з використанням масок.